第 40 章 排序¶
配套例题：BISHI21 【模板】排序、BISHI22 分数线划定、BISHI23 小红书推荐系统、 BISHI24 谐距下标对、BISHI25 最大 FST 距离、BISHI9 田忌赛马、BISHI12 元素方碑 来源：S2
useful algorithm/下的Bubble sort+.cpp、Selectionsort.cpp、Insert sort.cpp、Merge sort.cpp、Quick sort.cpp、heapsort.cpp；S4模板.docx排序章
C++ 选手学排序，是因为要写 cmp 传给 std::sort，偶尔还得手写归并求逆序对。
Python 选手学排序，理由只有一条半：
- 半条：面试和笔试选择题会问原理；
- 一条：归并排序的分治框架是求逆序对、CDQ 分治的基础，这个必须会。
至于「排序本身」，在 Python 里答案永远是 a.sort()。本章先把六种经典排序讲清楚，
再说明为什么它们在 Python 里只有教学价值，最后落到真正有用的那部分：分治与逆序对。
语法层面的 key／reverse／cmp_to_key 已在
12-自定义排序 讲透，本章不重复，只讲算法。
40.1 六种经典排序总览¶
| 算法 | 平均 | 最坏 | 最好 | 额外空间 | 稳定 | 思想 |
|---|---|---|---|---|---|---|
| 冒泡排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n)\) | \(O(1)\) | ✅ | 相邻交换 |
| 选择排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | ❌ | 每轮选最小 |
| 插入排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n)\) | \(O(1)\) | ✅ | 有序区扩张 |
| 归并排序 | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n)\) | ✅ | 分治 |
| 快速排序 | \(O(n\log n)\) | \(O(n^2)\) | \(O(n\log n)\) | \(O(\log n)\) 栈 | ❌ | 分治 + 划分 |
| 堆排序 | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n\log n)\) | \(O(1)\) | ❌ | 二叉堆 |
| Timsort（Python 内建） | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n)\) | \(O(n)\) | ✅ | 归并 + 插入 |
三条要背下来的结论：
- 只有归并和堆排的最坏情况也是 \(O(n\log n)\)；快排可以被构造数据卡到 \(O(n^2)\)。
- 稳定的只有冒泡、插入、归并（和 Timsort）；选择、快排、堆排都不稳定。
- \(O(n^2)\) 的三兄弟里，插入排序对「接近有序」的数据是 \(O(n)\)——这正是 Timsort 在小块上用插入排序的原因。
40.2 三种 \(O(n^2)\) 排序的 Python 实现¶
对照 S2 里的 C++ 源码逐一翻译。这些实现只用来理解原理，实战中一行都不要写。
冒泡排序¶
每一轮把最大的元素「冒」到末尾。S2 的 Bubble sort+.cpp 用了一个 bool p 提前退出，
这是必须保留的优化——它让已经有序的数组只扫一遍：
def bubble_sort(a):
n = len(a)
# 循环不变量：第 i 轮开始时，末尾 i 个元素已经是整个数组里最大的 i 个，且已排好
for i in range(n - 1): # 只需 n-1 轮，最后一个元素自动归位
swapped = False # 本轮是否发生过交换，用来提前退出
for j in range(n - 1 - i): # 末尾 i 个已归位，最后一次比较是 a[n-2-i] 与 a[n-1-i]
if a[j] > a[j + 1]: # 严格大于才交换：相等时不动，稳定性由此而来
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # 一整轮都没交换，说明相邻元素两两有序
break # 已有序的数组因此只扫一遍，退化成 O(n)
return a
选择排序¶
每轮在未排序区里找最小（S2 的 Selectionsort.cpp 找的是最大，效果一样）：
def selection_sort(a):
n = len(a)
# 循环不变量：进入第 i 轮时，a[0..i-1] 已是最终结果，且都不大于 a[i..n-1]
for i in range(n - 1): # i 是本轮要填好的位置
k = i # k 记录未排序区 a[i..n-1] 中最小值的下标
for j in range(i + 1, n):
if a[j] < a[k]: # 严格小于才更新，相等时保留更靠左的那个
k = j
if k != i:
a[i], a[k] = a[k], a[i] # 这次长距离交换正是它不稳定的原因
return a
选择排序为什么不稳定：
[2a, 2b, 1]第一轮把1和2a交换， 得到[1, 2b, 2a]——两个2的相对顺序被打乱了。 而冒泡只做相邻交换且严格用>，相等元素永远不换，所以稳定。
插入排序¶
把 a[i] 插进左边已排好的区间，S2 Insert sort.cpp 的写法是「边比较边右移」：
def insertion_sort(a):
# 循环不变量：每轮开始时 a[0..i-1] 已排好序（但未必是全局最终位置）
for i in range(1, len(a)): # 从 1 开始：单个元素天然有序
cur = a[i] # 先把待插入的值取出来，它原来的格子马上要被覆盖
j = i - 1 # 从有序区末尾往左找插入点
while j >= 0 and a[j] > cur: # 注意是 >，写成 >= 就不稳定了
a[j + 1] = a[j] # 元素右移，而不是两两交换
j -= 1
a[j + 1] = cur # 循环停在第一个不大于 cur 的位置，它右边就是空位
return a
三点值得记住：
- 移动代替交换：一次交换是三次赋值，一次移动只要一次，插入排序因此比冒泡快好几倍。
a[j] > cur里的严格大于保证了稳定性。- 数据接近有序时
while几乎不进入，退化成 \(O(n)\)。
40.3 归并排序：本章唯一必须掌握的手写排序¶
S2 的 Merge sort.cpp 是标准写法：递归分成两半，各自排好，再线性归并。
def merge_sort(a):
"""返回排好序的新列表。教学实现，实战请用 a.sort()。"""
if len(a) <= 1: # 递归出口：长度 0 或 1 的序列天然有序
return a
mid = len(a) // 2 # 下取整分割，保证两半都非空（len >= 2 时 1 <= mid < len）
left = merge_sort(a[:mid]) # 切片 a[:mid] 是下标 [0, mid) 这一段
right = merge_sort(a[mid:]) # 切片 a[mid:] 是下标 [mid, len) 这一段
return merge(left, right)
def merge(left, right):
res = []
i = j = 0 # i、j 分别指向 left、right 里下一个待取的元素
while i < len(left) and j < len(right): # 任一半取空就退出，剩下的整段搬运
if left[i] <= right[j]: # <= 保证稳定：相等时优先取左半
res.append(left[i]); i += 1
else:
res.append(right[j]); j += 1
res.extend(left[i:]) # 剩下的整段搬过去（两个切片必有一个是空的）
res.extend(right[j:])
return res
稳定性的关键在
<=。写成<时，相等元素会优先从右半取， 原本靠前的元素反而排到后面，稳定性就没了。这是面试高频追问点。
归并的真正用途：求逆序对¶
逆序对指满足 \(i < j\) 且 \(a_i > a_j\) 的下标对。它是归并排序的天然副产品：
归并时若从右半取走一个元素 right[j]，说明左半剩下的 len(left) - i 个元素
全都比它大且都在它前面，一次性贡献这么多逆序对。
def count_inversions(a):
"""归并排序求逆序对数量，O(n log n)。返回 (排好序的列表, 逆序对数)。"""
if len(a) <= 1:
return a, 0 # 单个元素构不成下标对
mid = len(a) // 2
left, c1 = count_inversions(a[:mid]) # c1：完全落在左半内部的逆序对
right, c2 = count_inversions(a[mid:]) # c2：完全落在右半内部的逆序对
res = []
i = j = 0
cnt = c1 + c2 # 还差「跨越两半」的那部分，正好在归并过程中数出来
nl = len(left)
while i < nl and j < len(right):
if left[i] <= right[j]:
res.append(left[i]); i += 1 # 取左半：它在前且不更大，不构成逆序对
else:
res.append(right[j]); j += 1
cnt += nl - i # 左半剩余的元素都与它构成逆序对
res.extend(left[i:])
res.extend(right[j:])
return res, cnt
| 求逆序对的三种做法 | 复杂度 | Python 现实性 |
|---|---|---|
| 暴力双重循环 | \(O(n^2)\) | \(n \le 3000\) |
| 归并分治 | \(O(n\log n)\) | 纯 Python 递归，\(n \le 10^5\) 勉强 |
| 树状数组 + 离散化 | \(O(n\log n)\) | 常数更小，Python 首选 |
树状数组写法见 39-树状数组与线段树， 离散化见 41-桶计数与离散化， 分治的进阶形态见 118-分治进阶-整体二分与CDQ。
40.4 快速排序与堆排序¶
快速排序¶
S2 的 Quick sort.cpp 用的是 Hoare 双指针划分 + 随机基准，这是防卡的标准姿势：
import random
def quick_sort(a, s, t):
"""就地快排，排序区间 [s, t]（闭区间）。教学实现。"""
if s >= t: # 区间里最多一个元素，无需排序
return
m = a[random.randint(s, t)] # 随机基准，防止被有序数据卡成 O(n²)
i, j = s, t # Hoare 划分：i 从左找不小于 m 的，j 从右找不大于 m 的
while i <= j:
while a[i] < m: # m 取自区间内部，天然是哨兵，指针不会越过区间
i += 1
while a[j] > m:
j -= 1
if i <= j: # 两端各找到一个「站错队」的元素
a[i], a[j] = a[j], a[i]
i += 1 # 换完必须各走一步，否则 a[i] == a[j] == m 时原地死循环
j -= 1
# 退出时 j < i：a[s..j] 全部不大于 m，a[i..t] 全部不小于 m，中间（若有）已在最终位置
if s < j:
quick_sort(a, s, j)
if i < t:
quick_sort(a, i, t)
不加随机化的快排必须视为错误做法。取
a[s]当基准时，一个已经排好序的数组 就能把它卡成 \(O(n^2)\) 加上 \(O(n)\) 的递归深度——在 Python 里直接RecursionError。这是 C++ 选手也会栽的经典坑。
堆排序¶
S2 的 heapsort.cpp 是「建大根堆 → 反复把堆顶换到末尾」。Python 里
heapq 是小根堆，所以标准的堆排序写法是：
import heapq
def heap_sort(a):
heapq.heapify(a) # 就地建小根堆，O(n) 而不是 O(n log n)
# range(len(a)) 在推导式开始前就求好了长度，循环中 a 变短不影响次数
return [heapq.heappop(a) for _ in range(len(a))] # 反复弹出当前最小值，共 n 次 O(log n)
堆的原理与 heapq 全 API 见
35-优先队列与堆。
堆排序在竞赛里几乎没有独立价值——需要全序就用 sort，需要动态取最值才用堆。
它唯一的优势是 \(O(1)\) 额外空间，而这在 Python 里毫无意义（heapify 就地做，
但 heappop 出来还是要新建列表）。
40.5 Timsort：Python 实际在跑的算法¶
list.sort() / sorted() 用的是 Timsort：
- 扫描一遍，把数组切成若干天然的单调段（run），降序段就地反转成升序；
- 太短的 run 用二分插入排序补长到 32–64；
- 用栈式归并把这些 run 两两合并，合并时用 galloping（跳跃）模式加速。
| 性质 | 值 | 竞赛含义 |
|---|---|---|
| 最坏复杂度 | \(O(n\log n)\) | 不存在卡快排式的构造数据 |
| 最好复杂度 | \(O(n)\) | 已经有序 / 分段有序时极快 |
| 稳定性 | 稳定 | 可以做多趟排序，见 12.7 |
| 实现层 | C（listsort.c） |
常数比纯 Python 循环小 50–100 倍 |
实测量级（\(n = 10^5\) 随机整数）：
| 写法 | 耗时 | 倍数 |
|---|---|---|
a.sort() |
约 0.02 s | 1× |
| 手写归并排序 | 约 1.2 s | 60× |
| 手写快排 | 约 1.5 s | 75× |
| 手写堆排（纯 Python） | 约 3 s | 150× |
结论：在 Python 里手写排序只有教学意义。 唯一的例外是题目明确要求「实现某种排序算法并输出中间过程」， 那属于模拟题，见 49-模拟。
40.6 排序在竞赛中的四种用途¶
排序本身很少是考点，它通常是别的算法的预处理步骤。识别用途比背算法重要：
| 用途 | 典型题型 | 关键点 |
|---|---|---|
| 让贪心成立 | 区间调度、任务调度、田忌赛马 | 排序键由交换论证推出，见 47-贪心 |
| 让双指针成立 | 两数之和、相差不超过 \(k\) | 有序后指针才单调，见 43-双指针与滑动窗口 |
| 让二分成立 | 区间元素计数、第 \(k\) 大 | bisect 要求有序，见 44-二分 |
| 离散化 | 值域大但个数少 | sorted(set(a)) + bisect，见 41-桶计数与离散化 |
反过来，三种「看起来要排序、其实不用」的情况（这是本章最容易失分的地方）：
| 需求 | 别排序 | 用什么 | 复杂度 |
|---|---|---|---|
| 只要最大 / 最小 | ❌ sorted(a)[0] |
min(a) / max(a) |
\(O(n)\) |
| 只要分组计数 | ❌ 排完扫连续段 | Counter(a) |
\(O(n)\) |
| 只要前 \(k\) 小（\(k \ll n\)） | ❌ sorted(a)[:k] |
heapq.nsmallest(k, a) |
\(O(n\log k)\) |
最危险的一种：题目里「下标」参与运算时排序会直接毁掉答案。 BISHI12、BISHI25 都是这个套路——排序前先问一句： 「我还需不需要原来的位置？」 需要就排
(值, 下标)元组，或者干脆别排。
40.7 例题¶
BISHI21 【模板】排序（入门）¶
给长度 \(n\ (1 \le n \le 10^5)\) 的整数数组（\(-10^9 \le a_i \le 10^9\)）， 按非递减顺序排序并在一行输出。 题面见 BISHI21 原题（牛客）。
模板题，考的就是「知不知道该用内建排序」：
import sys
data = sys.stdin.buffer.read().split() # 整块读入再切成 token，data[0] 是 n
n = int(data[0])
# 切片 [1, n+1) 恰好是 n 个数据 token；map 惰性产出，sorted 直接消费，不建中间列表
a = sorted(map(int, data[1:n + 1]))
sys.stdout.write(" ".join(map(str, a)) + "\n") # 一次写出，10^5 个数时远快于逐个 print
四个要点：
sorted(map(int, ...))：map是惰性的，sorted直接消费它， 比先建list再排少一次中间列表。- 值域是 \([-10^9, 10^9]\)，跨度 \(2\times10^9\)，不能用计数排序（桶开不下）。 这一条决定了本题必须是比较排序，见 41-桶计数与离散化。
- 别对
bytes直接排序。data[1:n+1]是bytes列表，sorted会按字典序排，"10" < "9"、负号更是灾难。必须先int。 - 输出用
" ".join，\(10^5\) 个数时比print(*a)明显快。
题解见 solutions/BISHI21.py。
BISHI22 / BISHI23 / BISHI24 / BISHI25：key 的四种典型形态¶
这四题的完整讲解在 12-自定义排序 §12.12， 这里只做算法层面的归纳，它们恰好覆盖了「排序题」的四个层次：
| 题 | 表面需求 | 真正考点 | 结论 |
|---|---|---|---|
| BISHI22 分数线划定 | 成绩降序 + 报名号升序 | 元组 + 负号 | key=lambda t: (-t[1], t[0]) |
| BISHI23 小红书推荐系统 | 频次降序 + 字典序升序 | 负号技巧的适用边界 | 降序字段是数字才能取负 |
| BISHI24 谐距下标对 | 统计满足关系的对数 | 根本不用排序 | 移项后 Counter 计数 \(O(n)\) |
| BISHI25 最大 FST 距离 | 求两两最大距离 | 排序解决不了 | 换坐标后取极差，\(O(n)\) |
BISHI24 的移项是最值得记的一步： \(a_j - a_i = j - i \iff a_j - j = a_i - i\)。 把「涉及两个下标的条件」改写成「每个下标各自算一个值，再比是否相等」， 问题就从排序/枚举掉到哈希计数。 这个变形在前缀和题里还会反复出现，见 42-前缀和与差分。
BISHI9 田忌赛马（中等）¶
三局两胜，速度严格大者胜；田忌可任意调整三匹马的出场顺序，问能否赢。 题面见 BISHI9 原题（牛客）。
这题挂着「田忌赛马」的名字，但 \(n = 3\) 固定，正解是全排列暴力而不是贪心。 完整代码与经典贪心策略的对照放在 47-贪心 §47.6，那里会讲 「\(n\) 一般时的双指针贪心」以及为什么在 \(n=3\) 时不该写贪心。
BISHI12 元素方碑（中等）¶
操作使 \(a_{i-1}\) 减 1、\(a_{i+1}\) 加 1，问能否让所有元素相等。 题面见 BISHI12 原题（牛客）。
这题排序就死：能量只在同奇偶性的下标之间流动，奇数位之和与偶数位之和是不变量，
一旦排序，位置的奇偶性信息全部丢失。完整推导见
12-自定义排序 §12.12，
题解见 solutions/BISHI12.py。
把它放在排序章的末尾，是为了强化那句话：排序是手段不是目的。
40.8 本章速查¶
| 场景 | 结论 |
|---|---|
| 实战排序 | 一律 a.sort() / sorted()，手写慢 50–100 倍 |
| 最坏 \(O(n\log n)\) 的排序 | 归并、堆排、Timsort（快排不是） |
| 稳定的排序 | 冒泡、插入、归并、Timsort |
| 手写快排 | 必须随机基准，否则有序数据卡成 \(O(n^2)\) + 爆栈 |
归并的 <= |
写成 < 就丢稳定性 |
| 求逆序对 | 归并分治 \(O(n\log n)\)；Python 更推荐树状数组 + 离散化 |
| 只要最值 | max / min，\(O(n)\) |
| 只要分组 | Counter，\(O(n)\) |
| 只要前 \(k\) 小 | heapq.nsmallest，\(k < n/10\) 时更快 |
| 值域大 | 不能计数排序，只能比较排序 |
| 下标参与运算 | 排序前先问「还要不要原下标」 |
bytes 排序 |
是字典序，数字必须先 int |
| 排序的四种用途 | 章节 |
|---|---|
| 让贪心成立 | 47-贪心 |
| 让双指针成立 | 43-双指针与滑动窗口 |
| 让二分成立 | 44-二分 |
| 离散化 | 41-桶计数与离散化 |