排序

结论先说

	`list.sort()`	`sorted()`
改谁	原地改接收者	不动原对象
返回	`None`	新的 list
收什么	只能 list	任意可迭代对象

list.sort() 返回 None 是 Python 的一条 API 约定：原地改对象的函数返回 None。这样调用方一眼就知道接收者被改了。代价是不能链式调用。

key 比比较函数好在哪

书里对 key 的评价是「brilliant」，理由有两条：

更简单。 你只要写一个单参数函数，返回排序依据。不用像 Python 2 的 cmp(a, b) 那样返回 -1 / 0 / 1。

更高效。 关键在这：

key 函数对每个元素只调用一次；两参数比较函数在排序算法每次要比较两个元素时都要调用。

也就是说，排 n 个元素，key 调用 n 次，比较函数调用 O(n log n) 次。而且拿到的键之间的比较是在优化的 C 代码里做的，不是在你写的 Python 函数里。

稳定性，以及它带来的实际差别

Python 的排序是稳定的：比较结果相等的元素保持原有相对顺序。

看这个例子就明白稳定性有什么用：

>>> fruits = ['grape', 'raspberry', 'apple', 'banana']
>>> sorted(fruits, key=len)
['grape', 'apple', 'banana', 'raspberry']
>>> sorted(fruits, key=len, reverse=True)
['raspberry', 'banana', 'grape', 'apple']

注意最后一行：它不是第一个结果的简单反转。

'grape' 和 'apple' 长度都是 5，在原始列表里 grape 在前。因为是稳定排序，升序时 grape 在前；降序时 grape 还是在前 —— 反转只作用于比较结果，不改变相等元素的相对位置。

这个性质的实际用处：多轮排序。想先按姓名排、再按年龄排，就先按姓名排一遍，再按年龄排一遍。第二轮不会打乱第一轮建立的顺序。

>>> sorted(fruits, key=str.lower)      # 大小写不敏感

混合类型：不指定 key 会失败

>>> l = [28, 14, '28', 5, '9', '1', 0, 6, '23', 19]
>>> sorted(l)
TypeError: unorderable types: str() < int()

Python 3 里 int 和 str 不可比较，直接排会抛异常。用 key 统一一下就行：

>>> sorted(l, key=int)
[0, '1', 5, 6, '9', 14, 19, '23', 28, '28']
>>> sorted(l, key=str)
[0, '1', 14, 19, '23', 28, '28', 5, 6, '9']

两种结果都合理，取决于你想把它们当数字还是当字符串。决定权在你，这正是不用自动转换的好处。

`key` 还能给别的函数用

min()、max()，以及标准库里的 itertools.groupby()、heapq.nlargest() 都接受 key。

>>> max(fruits, key=len)
'raspberry'

默认排序不是人类想要的排序

默认按字符码排

Python 默认按字符编码逐个字符比较。后果：

ASCII 大写字母排在小写字母前面（'Z' < 'a' 是 True）
非 ASCII 字符的排序结果通常没道理

>>> sorted(['Zebra', 'apple'])
['Zebra', 'apple']        # 不是人类期望的顺序
>>> sorted(['Zebra', 'apple'], key=str.lower)
['apple', 'Zebra']

按人类期望的方式排文本需要 locale.strxfrm 或 pyuca 这类工具。

书里的例子恰好全是小写 ASCII，所以看起来是对的 —— 这点容易被误读成「默认就能用」。

排完之后可以做二分查找

序列排好序之后，查找可以很快。标准库的 bisect 模块提供了二分查找，还有 bisect.insort，能在插入新元素后保持有序。

Timsort 的一点八卦

Python 用的排序算法叫 Timsort，2002 年进入 CPython。它是自适应的：根据数据的有序程度在插入排序和归并排序之间切换。真实数据往往已有局部有序的片段，所以这样很快。

书里的 Soapbox 讲到一段八卦：2009 年起 Java 和 Android 也用 Timsort，后来 Oracle 起诉 Google 时，把 Timsort 相关代码当成了证据之一。 2021 年美国最高法院判定 Google 对 Java 代码的使用属于「合理使用」。

Timsort 的作者 Tim Peters 是 CPython 的核心开发者，高产到有人开玩笑说他是 AI，外号「Timbot」。他还写了 Python 之禅（import this）。

我验证的

test_sort_in_place_returns_none —— list.sort() 确实返回 None
test_sorted_leaves_original_alone —— 原列表没变
test_sort_is_stable —— 断言降序结果不等于升序结果的反转
test_sort_mixed_bag_without_key_fails —— 不指定 key 抛 TypeError