17370845950

Python排序核心是sort()与sorted()，均基于Timsort算法：sort()是列表原地方法，返回None；sorted()是通用函数，返回新列表；Timsort为稳定混合算法，key参数用于预处理元素。

Python 的排序机制核心在于 sort() 和 sorted() 两个接口，它们底层共享同一套稳定排序算法（Timsort），但作用对象、返回值和是否修改原数据有本质区别。

sort() 是列表专属的原地排序方法

list.sort() 只能用于 list 对象，直接修改原列表，不创建新对象，返回值为 None。误写成 a = a.sort() 会导致变量变为 None，这是初学者常见错误。

• 只能调用在 list 实例上，如 [3,1,4].sort() 合法，(3,1,4).sort() 报错
• 支持 key 参数（函数）和 reverse 参数（布尔值），例如：names.sort(key=len, reverse=True)
• 不可用于字符串、元组、字典等不可变或无该方法的对象

sorted() 是通用内置函数，返回新序列

sorted() 接收任意可迭代对象（list、tuple、str、dict、生成器等），总是返回一个新列表，原对象完全不变。它更灵活，也更安全。

• 对字典排序时，默认迭代 key，sorted({'b':2, 'a':1}) 返回 ['a', 'b']
• 想按 value 排序？写 sorted(d.items(), key=lambda x: x[1])
• 字符串排序会拆成字符列表：sorted("hello") → ['e','h','l','l','o']

Timsort：Python 实际使用的混合稳定排序算法

Python 不用快排或归并排序，而是采用 Timsort——由 Tim Peters 为 Python 设计的自适应、稳定、高效排序算法。它结合了归并排序与插入排序的优点，在部分有序数据上表现极佳（时间复杂度接近 O(n)），最坏情况仍为 O(n log n)，且严格保持相等元素的相对位置。

• 自动检测升序/降序片段（“runs”），优先合并小段
• 对小数组（≤64 元素）直接用插入排序，减少开销
• 所有使用 sort() 或 sorted() 的场景，背后都是 Timsort 在工作

key 参数的本质：转换 + 稳定排序

key 不是“比较规则”，而是预处理函数：排序前先对每个元素调用 key(x)，再根据返回值排序；因 Timsort 稳定，原始顺序中 key 相同的元素不会乱序。

• sorted(['a1','a10','a2'], key=lambda x: int(x[1:])) → ['a1','a2','a10']
• sorted([(1,'c'),(2,'a'),(1,'b')], key=lambda x: x[0]) → [(1,'c'),(1,'b'),(2,'a')]（相同 key=1 的两项保持输入顺序）
• 避免在 key 中做耗时操作，否则显著拖慢排序速度