Python 3中sort函数时间复杂度：已排序列表追加元素后重排耗时分析

好问题！咱们来一步步拆解这个场景：

首先，Python里的list.sort()用的是Timsort算法——这是一种结合了归并排序和插入排序的高效排序算法，它的平均和最坏时间复杂度都是O(n log n)，其中n是列表的长度。

回到你的例子：

list1 = [1, 2, 3, 5]
list1.append(4)
list1.sort()

虽然list1在追加元素后只有最后两个元素是无序的，但sort()函数并不会检测列表的“部分有序”状态来做特殊优化——它会从头开始对整个列表执行完整的Timsort流程，所以这个操作的时间复杂度依然是O(n log n)（这里n=5，实际计算量很小，但复杂度级别不变）。

如果想优化这种“几乎有序”列表的排序效率，你可以用bisect模块的insort()方法，它会找到新元素应该插入的位置，然后移动元素完成插入，这个操作的时间复杂度是O(n)（因为只需要移动部分元素，不需要完整排序），示例代码：

import bisect
list1 = [1, 2, 3, 5]
bisect.insort(list1, 4)

这样得到的列表直接就是有序的，比调用sort()更高效，尤其是当列表长度很大的时候。

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