排序不仅用于写正解，也常用于验证结论：尝试某种贪心顺序、构造规范化结果，或者把两个无序答案转成可比较的形式。Python 的关键不是记住排序算法，而是掌握 sorted、list.sort 和 key。
sorted 与 list.sort
sorted 接受任意可迭代对象，返回一个新列表，不修改原数据：
1a = [5, 1, 4, 2]
2b = sorted(a)
3
4assert a == [5, 1, 4, 2]
5assert b == [1, 2, 4, 5]
list.sort 只用于列表，原地修改并返回 None：
1a = [5, 1, 4, 2]
2result = a.sort()
3
4assert a == [1, 2, 4, 5]
5assert result is None
不要写 a = a.sort()。执行后 a 会变成 None。需要新列表时用 sorted(a)，允许修改原列表时单独调用 a.sort()。
降序与翻转
1a = [5, 1, 4, 2]
2
3assert sorted(a, reverse=True) == [5, 4, 2, 1]
4assert list(reversed(a)) == [2, 4, 1, 5]
reverse=True 按排序规则降序排列；reversed(a) 只是把当前顺序反过来，两者含义不同。
使用 key 指定排序依据
key 接收一个函数。排序前，Python 对每个元素调用一次该函数，并按照返回值比较。
按绝对值排序：
1a = [-7, 2, -3, 5]
2
3assert sorted(a, key=abs) == [2, -3, 5, -7]
按第二个字段排序：
1items = [("apple", 3), ("banana", 1), ("pear", 2)]
2answer = sorted(items, key=lambda item: item[1])
3
4assert answer == [
5 ("banana", 1),
6 ("pear", 2),
7 ("apple", 3),
8]
lambda item: item[1] 是一个没有名字的短函数，相当于：
1def second(item):
2 return item[1]
3
4
5items = [("apple", 3), ("banana", 1), ("pear", 2)]
6assert sorted(items, key=second)[0] == ("banana", 1)
复杂逻辑应使用普通 def，不要为了少写一行把 lambda 变得难以阅读。
多关键字排序
Python 的元组按字典序比较：先比较第一项，相等时再比较第二项。
例如先按分数降序，再按名字升序：
1students = [
2 ("Bob", 90),
3 ("Alice", 95),
4 ("Carol", 90),
5]
6
7answer = sorted(students, key=lambda item: (-item[1], item[0]))
8
9assert answer == [
10 ("Alice", 95),
11 ("Bob", 90),
12 ("Carol", 90),
13]
数字字段前加负号，可以让这一项按降序排列，同时保留其他字段的升序规则。
也可以直接利用元组默认顺序：
1pairs = [(2, 3), (1, 9), (2, 1), (1, 4)]
2
3assert sorted(pairs) == [(1, 4), (1, 9), (2, 1), (2, 3)]
itemgetter
operator.itemgetter 可以代替简单的下标 lambda：
1from operator import itemgetter
2
3items = [("apple", 3), ("banana", 1), ("pear", 2)]
4
5assert sorted(items, key=itemgetter(1)) == [
6 ("banana", 1),
7 ("pear", 2),
8 ("apple", 3),
9]
它不是必须掌握的技巧。竞赛临时代码中，lambda item: item[1] 往往更容易立即看懂。
稳定排序
Python 排序是稳定的：如果两个元素的 key 相同，它们保持原来的相对顺序。
1items = [
2 ("first", 2),
3 ("second", 1),
4 ("third", 2),
5]
6
7answer = sorted(items, key=lambda item: item[1])
8
9assert answer == [
10 ("second", 1),
11 ("first", 2),
12 ("third", 2),
13]
这允许我们分两次排序，但通常一次返回元组键更加直接。
用全排列验证排序贪心
有 个任务，第 个任务耗时为 。依次执行任务，每个任务的完成时间是它结束的时刻。目标是让所有完成时间之和最小。
贪心结论是按照耗时从小到大执行。小规模时可以枚举所有顺序验证：
1from itertools import permutations
2
3
4def completion_cost(order):
5 elapsed = 0
6 total = 0
7
8 for duration in order:
9 elapsed += duration
10 total += elapsed
11
12 return total
13
14
15def brute_best(tasks):
16 return min(
17 (completion_cost(order), order)
18 for order in permutations(tasks)
19 )
20
21
22def greedy(tasks):
23 order = tuple(sorted(tasks))
24 return completion_cost(order), order
25
26
27tasks = [4, 1, 3]
28
29assert brute_best(tasks) == greedy(tasks) == (13, (1, 3, 4))
这里 min 比较 (代价, 顺序) 元组，先选择代价最小的方案；代价相同再按顺序打破平局。
自定义比较函数
Python 更推荐 key，因为每个元素的键只计算一次。确实只有“两元素比较规则”时，可以使用 cmp_to_key：
1from functools import cmp_to_key
2
3
4def compare_length_then_text(a, b):
5 if len(a) != len(b):
6 return len(a) - len(b)
7 return (a > b) - (a < b)
8
9
10words = ["bbb", "a", "cc", "aa"]
11answer = sorted(words, key=cmp_to_key(compare_length_then_text))
12
13assert answer == ["a", "aa", "cc", "bbb"]
这个例子用 key=lambda word: (len(word), word) 会更简单。只有比较规则难以转换成独立键时才考虑 cmp_to_key。
规范化后比较答案
题目不要求输出顺序时，可以先排序再比较：
1expected = [(1, 3), (2, 4), (5, 8)]
2actual = [(5, 8), (1, 3), (2, 4)]
3
4assert sorted(actual) == sorted(expected)
如果元素允许重复并且只关心出现次数，Counter 通常比集合更合适。