Python 排序的三个边界：key、稳定性与原地修改

一、key 提取比较依据，不是比较两个元素

key 接收一个输入元素，返回用于排序的键。例如数字字符串默认按字符串规则排序；用 key=int 可以按对应整数排序，但返回列表里的元素仍是原来的字符串，不是转换后的整数。

正常完成的一次排序中，每个输入位置对应的键计算一次，之后排序使用这些键进行比较。它不是每比较一对元素就重新执行一次，也不是按对象身份自动去重：同一对象在输入里出现两次，仍对应两次键提取。若计算键时已经抛出异常，不能据此期待所有位置都已被处理。

因此，适合放进 key 的是明确、可比较的排序依据。下面用整数分数排序自制记录，只读取当前元素，不修改记录或正在排序的列表，也不访问外部数据。

from operator import itemgetter

rows = [
    {"id": "r1", "score": 20},
    {"id": "r2", "score": 10},
    {"id": "r3", "score": 20},
    {"id": "r4", "score": 10},
]
ascending = sorted(rows, key=itemgetter("score"))
descending = sorted(rows, key=itemgetter("score"), reverse=True)
assert [row["id"] for row in ascending] == ["r2", "r4", "r1", "r3"]
assert [row["id"] for row in descending] == ["r1", "r3", "r2", "r4"]
assert [row["id"] for row in rows] == ["r1", "r2", "r3", "r4"]
work = rows.copy()
result = work.sort(key=itemgetter("score"))
assert result is None
assert [row["id"] for row in work] == ["r2", "r4", "r1", "r3"]
assert work[0] is rows[1]
print("排序键、稳定性与原地修改验证通过")

二、稳定性只约束排序键相同的记录

上例中，分数为10的 r2 始终排在 r4 前，分数为20的 r1 始终排在 r3 前。这就是稳定性：同键记录保留输入时的相对顺序，而不是额外按 id 排序。

reverse=True 同样保留这种并列顺序。它与“先升序排序，再把整个结果反转”不同，后者还会反转每个并列组内部的顺序。如果业务要求并列时按另一个字段排列，应把这个字段作为明确的次级条件。

稳定性也不会凭空创造确定的业务次序。如果上游没有约定同分记录的输入顺序，稳定排序只会保留拿到的那个顺序；需要固定的并列规则，就应主动提供可比较的次级键。

三、多轮排序先处理次要条件

稳定排序允许把多级条件拆开：先按次要条件排序，再按主要条件排序。第二轮在主要键相等的组里，会保留第一轮得到的次序。下面要求团队字母升序、同团队内分数降序；分数再相同时保留原输入顺序。

from operator import itemgetter

rows = [
    {"id": "r1", "team": "B", "score": 70},
    {"id": "r2", "team": "A", "score": 90},
    {"id": "r3", "team": "B", "score": 90},
    {"id": "r4", "team": "A", "score": 70},
    {"id": "r5", "team": "A", "score": 70},
]
secondary = sorted(rows, key=itemgetter("score"), reverse=True)
combined = sorted(secondary, key=itemgetter("team"))
single = sorted(rows, key=lambda row: (row["team"], -row["score"]))
assert [row["id"] for row in combined] == ["r2", "r4", "r5", "r3", "r1"]
assert [row["id"] for row in single] == [row["id"] for row in combined]
print("多轮排序与复合键验证通过")

对于同方向的多级条件，元组键也可以直接表达“先看第一个字段，相同再看第二个字段”。上例为整数分数，使用负号表达分数降序；这不是任意类型字段的通用降序写法。遇到不同类型或方向，先明确各字段的比较规则，再选择复合键或稳定的多轮排序。

多轮排序意味着每轮都会重新提取该轮的键，并不是整个多级流程只计算一次。也不要因为两种写法在这个小输入上结果相同，就据此断言它们在所有数据上具有相同性能。

四、新列表与原地修改影响不同的调用方

sorted() 从可迭代对象建立新的结果列表。对于正文这种读取型键函数，它没有重排原列表的槽位。list.sort() 则修改原列表，并返回 None；因此不要写 rows = rows.sort() 后再期待 rows 是排好序的列表。

若其他变量也引用同一个列表，原地排序后它们看到的顺序也会改变。需要同时保留原顺序和排序结果时，新结果列表往往更直接；如果调用方明确拥有列表、允许原地修改，则可以使用 sort()，而不把它的返回值当结果。

新列表不等于深拷贝。第一个代码块最后的身份断言表明，排序结果和输入仍引用同一个记录字典。以后修改结果中的这条记录，其他持有该对象的路径也可能看到变化。排序负责排列元素引用，不负责隔离元素内容。

sorted() 也会实际消费传入的迭代器，而不是保留一个可以无限次回放的视图。对无限输入不能直接期待完整排序结束；对已经消费过的迭代器，得到的只是余下内容的排序。若需要保留完整输入，应在消费之前确定所有权和保存策略。

五、key 和异常不提供事务式回滚

有了 key，仍要保证提取出的键能按期望比较。例如让一部分键为整数、另一部分为字符串，并不会因为传了键函数就自动获得业务排序规则；这种输入可能抛出 TypeError。缺失字段、转换失败和自定义比较中的异常也需要按接口处理。

list.sort() 遇到比较异常会失败，列表可能已经部分修改。捕获异常不能被当成回滚到原顺序；需要保留原顺序的流程，应事先另存顺序或先在独立列表上尝试，成功后再按业务约定采用结果。

不过，独立列表也只隔离外层顺序。用户提供的键函数和比较方法可以执行其他代码，如果它们修改了共享记录或外部状态，sorted() 并不替调用方撤销这些副作用。本文只使用读取型键函数和一个专门验证异常传播的内存对象，没有模拟业务事务。

官方3.9文档还把排序期间检查或修改同一个列表的未定义效果标为CPython实现细节。不要在键函数或比较方法里依赖该列表此时的内容，也不要修改它；所需排序依据应从当前记录或事先准备好的明确数据中取得。

六、验证结果，也验证修改边界

排序验证不宜只比较一串最终值。可以给记录添加易识别的标签，检查同键记录的相对顺序；记录键函数调用次数，区分每个输入位置与每个独立对象；保留原列表和别名，确认哪一份顺序发生了变化。

本文两个代码块已在独立CPython3.9.6进程运行，另有十二项标准库内存检查，覆盖新列表、原地返回值、共享元素、迭代器消费、键提取次数、数字字符串、升降序稳定性、多轮条件及异常传播。全部数据有限且为自制对象，未读取私人项目、访问网络服务或进行性能基准；也没有对异常后的具体排列作跨实现保证。

参考：Python Sorting HOW TO 的 Key Functions、Sort Stability and Complex Sorts、Odd and Ends；Built-in Functions 的 sorted；Built-in Types 的 list.sort。