python - Python 的 sort()/sorted() 函数调用其可选的“关键”参数 O(n) 次还是 O(n log n) 次？

Question

假设apples是一个包含 n 个苹果的列表，我有一个函数apple_evaluator(apple)可以评估一个苹果的“好坏”。要按“善良”排序apples，我使用apples.sort(key = apple_evaluator)or sorted(apples, key=apple_evaluator)。

将apple_evaluator被调用 O(n) 次（例如 Python 预先计算apple_evaluator(apple) 每个appleinapples然后使用这些值进行排序apples）或 O(n log n) 次（例如 Python 计算在apple_evaluator每次排序进行比较时重新计算值）？

Answer 1

只需测试：

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)。

Answer 2

替换cmpwith的全部意义key在于对关键函数进行 O(n) 次调用。这被称为Schwartzian 变换或 decorate-sort-undecorate

在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