Python的sort（）/ sorted（）函數是否調用其可選的'key'參數O（n）次或O（n log n）次？

假設是一個n個蘋果的列表，我有一個功能apple_evaluator(apple)評估一個蘋果的'善良'。按'善良'分類我使用apples.sort(key = apple_evaluator)或sorted(apples, key=apple_evaluator)。Python的sort（）/ sorted（）函數是否調用其可選的'key'參數O（n）次或O（n log n）次？

將apple_evaluator得到所謂O（n）的時間（如Python的預先計算apple_evaluator(apple)每個apple在然後使用這些值排序）或爲O（n log n）的時間（如Python的計算每個時間重新計算apple_evaluator值排序做一個比較）？

來源

2013-10-14 D G

只是測試：

count = [0] 

def _sort_key(x): 
    count[0] += 1 
    return x 


a = list(np.random.rand(12)) 

print count 
a.sort(key=_sort_key) 
print count, len(a)

答案是O（n）。

來源

2013-10-14 02:08:31 tacaswell

不能'計數'只是一個變數？ – thefourtheye

@thefourtheye，是的，只需要在'_sort_key'函數中加入'全局計數'以允許它在那裏被反彈 –

@gnibbler'count'是這種情況下的一個列表。這有點矯枉過正，對吧？這可能只是一個全局變量'count'。 – thefourtheye

將cmp替換爲key的整點是對鍵功能進行O（n）調用。這就是所謂的Schwartzian transform或裝飾排序，去除裝飾

的key參數出現之前，人們發現，cmp幾乎無用的，因爲它是更有效地做這個程序。 f是關鍵功能

L = [(f(i), i) for i in L]       ## decorate 
L.sort() # there was no "sorted()" at the time ## sort 
L = [i[1] for in L]         ## undecorate

來源

2013-10-14 02:49:06

Python的sort（）/ sorted（）函數是否調用其可選的'key'參數O（n）次或O（n log n）次？

回答

相關問題