Python排序中比较器的调用时机判定及时间复杂度咨询

测试代码 #

from functools import cmp_to_key

def compare(a, b):
    print('comparator called')
    return a - b
  
mylist = [5, 1, 2, 4, 3]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)


mylist = [1, 2, 3, 4, 5]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)


mylist = [5, 4, 3, 2, 1]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)


mylist = [5, 1, 2, 3, 4]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)

输出结果 #

comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]

问题解答 #

1. 比较器的调用逻辑 #

Python内置的sorted()函数使用Timsort排序算法，这是一种自适应的混合排序算法，它的调用逻辑完全基于输入列表的已有有序特征：

• 第一步，算法会扫描列表，识别出天然存在的升序/降序子序列（称为run，降序子序列会被反转成升序）；
• 第二步，按照预设规则合并这些run，合并时会根据run的长度、有序性选择最优策略，比如用“galloping模式”快速匹配元素，减少不必要的比较。

不同输入的run数量、长度差异直接导致比较次数不同：

• 完全升序的列表本身就是一个完整run，无需合并，所以比较次数极少；
• 完全降序的列表会被反转成一个升序run，同样不需要复杂合并，比较次数也少；
• 乱序程度高的列表会被拆分成多个短run，合并这些片段需要更多比较操作，因此比较器调用次数更多。

2. 时间复杂度 #

Timsort的时间复杂度表现稳定：

• 最好情况：O(n)。当输入完全有序时，仅需一次线性扫描确认即可，无需额外排序操作；
• 平均情况：O(n log n)。绝大多数常见输入场景下都能维持这个效率；
• 最坏情况：O(n log n)。无论输入如何混乱，算法都不会退化为O(n²)的复杂度，稳定性有保障。

内容的提问来源于stack exchange，提问作者Saif