017、list 从入门到精通三sort 与 sorted 的 Timsort 算法原理上周五晚上十一点我盯着监控面板上一条诡异的性能曲线发呆——一个排序操作在数据量从10万条涨到50万条时耗时从0.3秒直接飙到8秒完全不是线性增长。排查了半天发现是某位同事在循环里反复调用list.sort()对同一个列表做增量排序每次排序都重新触发完整的Timsort流程。这个坑让我决定把Timsort的底裤扒干净免得大家再踩。先搞清楚 sort 和 sorted 的区别这两个东西长得像双胞胎但性格完全不同。list.sort()是列表的专属方法它会直接修改原列表返回None。sorted()是内置函数接受任何可迭代对象返回一个新的排序后的列表。# 这里踩过坑以为 sort 返回新列表data[3,1,4,1,5]resultdata.sort()# result 是 Nonedata 已经被改了print(result)# Noneprint(data)# [1, 1, 3, 4, 5]# 想要新列表就用 sorteddata[3,1,4,1,5]new_datasorted(data)# data 不变new_data 是排序后的print(data)# [3, 1, 4, 1, 5]print(new_data)# [1, 1, 3, 4, 5]别这样写data data.sort()这会把列表变成 None然后你的程序就炸了。我见过有人因为这个 bug 排查了三个小时。Timsort 到底是什么鬼Python 从 2.3 版本开始就用 Timsort 作为默认排序算法发明者是 Tim Peters就是写《Python之禅》那位大佬。它不是从零发明的算法而是融合了归并排序和插入排序的混血儿。Timsort 的核心思想现实世界中的数据往往不是完全随机的很多数据已经部分有序。比如用户注册时间列表、日志文件的时间戳、甚至你从数据库查出来的记录经常是“大致有序”的。Timsort 就是专门吃这种“软柿子”的。算法骨架分而治之的归并思路Timsort 的整体流程可以概括为三步扫描数据识别自然有序的片段run用插入排序把短 run 扩展到最小长度用归并排序合并相邻的 run直到只剩一个听起来像归并排序没错但 Timsort 在细节上做了大量优化。第一步找 run别小看这个动作Timsort 从左到右扫描列表找到所有“自然有序”的连续子序列。这里的“有序”包括严格递增和严格递减两种情况。如果遇到递减序列Timsort 会直接反转它变成递增序列。# 假设我们有这个列表data[1,3,5,4,2,6,8,7,9]# Timsort 会找到这些 run# [1, 3, 5] 递增# [4, 2] 递减反转成 [2, 4]# [6, 8] 递增# [7, 9] 递增这里有个细节Timsort 对递减序列的处理非常聪明。它不会傻乎乎地先反转再处理而是在扫描时就识别出递减趋势然后直接按逆序处理省掉一次反转操作。第二步插入排序的妙用如果某个 run 的长度小于一个阈值通常是 32 或 64具体取决于数据量Timsort 会用二分插入排序把它扩展到最小长度。为什么用插入排序因为插入排序在处理小规模数据时效率极高而且它是稳定排序。# 别这样写自己实现插入排序defmy_insertion_sort(arr):foriinrange(1,len(arr)):keyarr[i]ji-1whilej0andarr[j]key:arr[j1]arr[j]j-1arr[j1]key# 这个实现没问题但 Timsort 用的是二分插入排序# 二分插入排序用二分查找找到插入位置减少比较次数Timsort 的插入排序优化点在于它用二分查找代替线性查找来确定插入位置。对于小数组比较次数从 O(n) 降到 O(log n)虽然移动次数不变但整体性能提升明显。第三步归并的平衡艺术Timsort 维护一个栈每次生成一个新的 run 就压入栈中。但有个关键约束栈中任意三个相邻的 run 的长度必须满足某种平衡条件类似斐波那契数列的性质。如果不满足就合并中间的两个 run。这个约束的目的是保证归并操作的时间复杂度接近 O(n log n)避免出现极端情况。具体来说Timsort 维护了这样一个不变量A B C 且 B C其中 A、B、C 是栈顶的三个 run 的长度。如果不满足就合并 B 和 C或者 A 和 B取决于具体情况。稳定性Timsort 的隐藏技能Timsort 是稳定排序这意味着相等元素的相对顺序在排序后保持不变。这个特性在实际开发中非常有用。# 场景先按年龄排序再按姓名排序students[(Alice,23),(Bob,21),(Charlie,23),(David,21)]# 先按姓名排序students.sort(keylambdax:x[0])# 再按年龄排序稳定排序保证同年龄的人按姓名顺序排列students.sort(keylambdax:x[1])print(students)# [(Bob, 21), (David, 21), (Alice, 23), (Charlie, 23)]这里踩过坑如果你用快速排序不稳定第二次排序可能会打乱第一次排序的结果。Timsort 的稳定性让你可以安全地链式排序。性能分析什么时候快什么时候慢Timsort 的最好时间复杂度是 O(n)发生在数据已经有序的情况下。它只需要扫描一遍数据识别出一个大 run然后直接结束。最坏时间复杂度是 O(n log n)发生在数据完全随机的情况下。这时候每个 run 都很短需要大量归并操作。空间复杂度是 O(n)因为归并操作需要额外的临时数组。但 Timsort 做了优化它只分配一次临时数组大小不超过原数组的一半。# 性能对比不同数据分布下的排序时间importtimeimportrandom# 已经有序的数据data_sortedlist(range(1000000))starttime.time()data_sorted.sort()print(f有序数据:{time.time()-start:.4f}秒)# 极快接近 O(n)# 完全随机数据data_random[random.randint(0,1000000)for_inrange(1000000)]starttime.time()data_random.sort()print(f随机数据:{time.time()-start:.4f}秒)# 正常 O(n log n)# 部分有序数据比如数据库分页查询的结果data_partiallist(range(0,1000000,2))list(range(1,1000000,2))starttime.time()data_partial.sort()print(f部分有序:{time.time()-start:.4f}秒)# 介于两者之间实战中的坑与优化坑一key 函数的性能陷阱# 别这样写每次比较都执行昂贵的 key 函数data[apple,banana,cherry,...]data.sort(keylambdax:expensive_function(x))# 每次比较都调用 expensive_function# 应该这样写用装饰-排序-去装饰模式decorated[(expensive_function(x),x)forxindata]decorated.sort()data[xfor_,xindecorated]Timsort 在内部会缓存 key 函数的计算结果但如果你用key参数它会在排序前计算所有元素的 key 值并缓存。如果 key 函数很昂贵这个缓存过程本身就有开销。坑二自定义比较函数的性能Python 2 支持cmp参数Python 3 移除了这个功能。如果你需要自定义比较逻辑用functools.cmp_to_key转换但性能会下降。fromfunctoolsimportcmp_to_keydefcustom_cmp(a,b):# 自定义比较逻辑ifa[priority]!b[priority]:returna[priority]-b[priority]returna[timestamp]-b[timestamp]data.sort(keycmp_to_key(custom_cmp))# 性能比直接用 key 差坑三排序稳定性与多键排序前面提到过Timsort 是稳定的。利用这个特性你可以实现多键排序# 先按年龄降序再按姓名升序students.sort(keylambdax:x[0])# 先按姓名升序students.sort(keylambdax:x[1],reverseTrue)# 再按年龄降序注意顺序先排次要键再排主要键。因为稳定排序会保留前一次排序的结果。个人经验性建议能用sort就别用sorted如果你不需要保留原列表list.sort()更省内存因为它不需要创建新列表。大数据量排序前先考虑数据分布如果数据已经部分有序比如日志文件按时间戳追加Timsort 会表现得非常好。如果数据完全随机考虑用numpy的排序底层是 C 实现的快速排序。key 函数要轻量不要在 key 函数里做复杂计算。如果必须做考虑预处理数据把计算结果缓存起来。避免在循环里排序回到开头的那个坑如果你需要维护一个有序列表考虑用bisect模块插入新元素而不是每次重新排序。理解 Timsort 的稳定性这个特性在很多场景下能简化代码比如排行榜、多条件排序等。Timsort 不是银弹但它确实是一个工程上极其优秀的排序算法。理解它的原理能让你在遇到排序性能问题时快速定位瓶颈并找到优化方向。下次你的排序代码变慢了先想想数据是不是完全随机的再想想是不是在循环里反复排序了。