17370845950

Python 的 sorted() 和 list.sort() 使用 Timsort 算法，一种结合插入排序与归并排序的稳定混合算法，专为部分有序数据优化，两者底层实现相同，仅在是否原地排序上不同。

Python 的 sorted() 和 list.sort() 用的是什么算法

Python 标准库的排序不是手写的快排或归并，而是 Timsort —— 一种为真实数据（尤其部分有序）优化的混合稳定排序算法，由 Tim Peters 为 Python 设计。它结合了归并排序和插入排序，在小数组或局部有序段上切片使用插入排序，再用归并合并。这意味着：

• sorted() 返回新列表，list.sort() 原地修改，两者底层都调用同一套 Timsort 实现
• 最坏时间复杂度仍是 O(n log n)，但现实中多数场景（如已排序、逆序、含重复块）性能远优于纯快排
• 稳定：相等元素的相对位置不会改变，这对多级排序（比如先按年龄、再按姓名）很关键

什么时候该用 key 参数而不是自己写比较逻辑

直接传 key 函数比写 cmp_to_key 或自定义 __lt__ 更安全、更高效。Timsort 内部只调用 key 一次/元素，而旧式 cmp 方式（Python 2 风格）在每次比较时都执行函数，开销大且易出错。

• 升序按字符串长度：sorted(words, key=len)
• 降序按绝对值：sorted(nums, key=abs, reverse=True)
• 多字段：先按姓氏再按名字，key=lambda x: (x.last, x.first)
• 避免踩坑：不要在 key 中做副作用操作（如修改全局状态），它可能被多次调用（尽管 Timsort 会缓存结果，但行为不保证）

sorted() 在字典和生成器上的行为差异

字典本身不可排序，但 sorted() 可对它的键、值或项视图排序；生成器则必须转成序列才能排序，否则会报 TypeError: 'generator' object is not subscriptable。

• 按字典键排序：sorted(d.keys()) 或直接 sorted(d)
• 按键排序并保留键值对：sorted(d.items(), key=lambda kv: kv[0])
• 生成器必须先收集：sor

  

  ted((x*2 for x in range(10))) 是合法的，因为 sorted() 内部会先转成列表；但 sorted(range(10**7)) 会吃掉大量内存，此时应考虑是否真需要全量排序
• 注意：空生成器没问题，sorted(()) 或 sorted([]) 都返回空列表，类型一致

自定义对象排序时 __lt__ 和 key 的取舍

如果类设计之初就明确“天然有序”（比如 Point 按欧氏距离、Date 按时间先后），实现 __lt__ 更自然；如果只是临时按某字段排序（比如调试时按 obj.debug_id 查看），用 key 更轻量、不侵入类定义。

• 只实现 __lt__ 就够了：sorted() 能自动推导其他比较关系（通过 @total_ordering 装饰器可补全）
• 若同时支持多种排序逻辑，硬编码 __lt__ 反而僵化；这时 key 是唯一合理选择
• 性能上无实质差别，但 key 更易测试、更易组合（比如 key=lambda x: (x.status, -x.priority)）
• 容易忽略的一点：如果对象有 __lt__ 但逻辑有 bug（比如未处理 None），排序过程可能抛 TypeError 且堆栈不直观；key 的错误更容易定位