第 41 章 分治排序——归并排序与快速排序
🏗️ 前情回顾：上一章你学会了
sort()，知道它背靠快速排序，平均 O(n log n)。但光会调用还不够——当题目说"请用归并排序求逆序对"或"实现快排的 partition 过程"时，你必须懂原理。这一章，我们深入两种经典的分治排序：归并排序和快速排序，手写实现，彻底搞懂 O(n log n) 是怎么来的。
🎯 本章目标
学完这一章，你能：
- 理解分治思想：把大问题拆成小问题，分别解决后合并
- 手写归并排序（Merge Sort），理解它永远是 O(n log n) 且稳定
- 手写快速排序（Quick Sort），理解选基准和分区过程
- 知道快排最坏 O(n²) 的原因以及随机化避免方法
- 对比归并排序和快速排序的优缺点
- 为接下来用归并排序求逆序对打好基础
📖 故事引入
假设你是班长，老师让你把全班 40 份试卷按学号从小到大排好。你一个人面对 40 份乱糟糟的卷子，怎么排最快？
你可能会这样做：把 40 份试卷分成两堆，每堆 20 份，分别让两个小组长去排。两个小组长又各分一半给四个副组长……直到每人手里只有 1 份（天然有序）。然后一层一层往上传：左右两堆都是有序的，合并起来就行。
这就是归并排序——典型的"分而治之"：分一半 → 分别排 → 合并。
换一种思路：你不分给人，而是随手抽一份试卷当"标杆"（比如学号 25），然后把学号小于 25 的放左边，大于 25 的放右边。左右两堆再分别用同样的方法排……
这就是快速排序——选基准 → 分左右 → 递归。
🧱 知识讲解
41.1 分治思想回顾
分治法（Divide and Conquer） 的三部曲：
- 分（Divide）：把原问题拆成若干个规模更小的同类子问题
- 治（Conquer）：递归地解决每个子问题。如果子问题足够小（比如只剩 1 个元素），直接解决
- 合（Combine）：把子问题的解合并成原问题的解
你已经在第 26 章学过递归了，分治其实就是"先递归，再合并"。
41.2 归并排序（Merge Sort）
核心思想：把数组从中间切成两半，递归排序左右两半，然后把两个有序的子数组合并成一个有序数组。
过程图解（[38, 27, 43, 3, 9, 82, 10]）：
[38,27,43,3,9,82,10]
/ \
[38,27,43,3] [9,82,10]
/ \ / \
[38,27] [43,3] [9,82] [10]
/ \ / \ / \ |
[38] [27] [43] [3] [9] [82] [10]
\ / \ / \ / |
[27,38] [3,43] [9,82] [10]
\ / \ /
[3,27,38,43] [9,10,82]
\ /
[3,9,10,27,38,43,82]C++ 实现：
const int MAXN = 100005;
int a[MAXN], tmp[MAXN]; // tmp 是合并用的临时数组
// 合并两个有序子数组 a[l..mid] 和 a[mid+1..r]
void merge(int l, int mid, int r) {
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++]; // 左边有剩余
while (j <= r) tmp[k++] = a[j++]; // 右边有剩余
for (int p = l; p <= r; p++) // 拷贝回原数组
a[p] = tmp[p];
}
// 归并排序主函数
void mergeSort(int l, int r) {
if (l >= r) return; // 只剩 1 个元素，天然有序
int mid = l + (r - l) / 2; // 防止 (l+r) 溢出
mergeSort(l, mid); // 递归排序左半
mergeSort(mid + 1, r); // 递归排序右半
merge(l, mid, r); // 合并
}🎯 复杂度：无论什么数据，总是 O(n log n)。空间 O(n)（需要临时数组）。稳定。
为什么是 O(n log n)？
- 递归树有 log₂n 层（每次对半分）
- 每层合并的开销是 O(n)（扫描所有元素）
- 总复杂度 = O(n) × O(log n) = O(n log n)
41.3 快速排序（Quick Sort）
核心思想：选一个"基准值"（pivot），把所有小于基准的移到左边，大于基准的移到右边。然后对左右两部分递归地做同样的事。
过程图解（[38, 27, 43, 3, 9, 82, 10]，选 10 为基准）：
第1轮 partition(选10):
[38,27,43,3,9,82,10]
→ 10放中间 → 左边[3,9] 右边[38,27,43,82]
结果：[3,9] 10 [38,27,43,82]
递归左[3,9], 选9:
[3] 9 []
递归右[38,27,43,82], 选82:
[38,27,43] 82 []
递归继续...C++ 实现（随机化版本）：
#include <cstdlib> // rand()
#include <ctime> // time()
int partition(int l, int r) {
// 随机选基准，与最右元素交换（避免最坏情况）
int pivotIdx = l + rand() % (r - l + 1);
swap(a[pivotIdx], a[r]);
int pivot = a[r]; // 基准值
int i = l - 1; // i 指向"小于区"的末尾
for (int j = l; j < r; j++) {
if (a[j] <= pivot) { // 比基准小的
i++;
swap(a[i], a[j]); // 交换到小于区
}
}
swap(a[i + 1], a[r]); // 基准放在正确位置
return i + 1; // 返回基准的最终位置
}
void quickSort(int l, int r) {
if (l >= r) return;
int p = partition(l, r); // 分区，p 是基准位置
quickSort(l, p - 1); // 递归左半
quickSort(p + 1, r); // 递归右半
}🎯 复杂度：平均 O(n log n)，最坏 O(n²)（每次基准恰好是最大/最小值）。空间 O(log n)（递归栈）。不稳定。
41.4 快速排序的最坏情况与应对
快排什么时候最慢？当每次选的基准都是最大或最小值时——比如对已排序数组 [1,2,3,4,5] 选最右边元素当基准，每次只能排除一个元素，退化为 O(n²)。
应对方法：
- 随机化：随机选基准（代码如上），最坏概率极低
- 三数取中：取
a[l]、a[mid]、a[r]的中位数作为基准 - 直接用
sort()：STL 的sort()已经做了这些优化，普通竞赛选手无需操心
41.5 归并 vs 快排：选谁？
| 归并排序 | 快速排序 | |
|---|---|---|
| 时间复杂度 | 总是 O(n log n) | 平均 O(n log n)，最坏 O(n²) |
| 空间复杂度 | O(n)（需临时数组） | O(log n)（递归栈） |
| 稳定性 | ✅ 稳定 | ❌ 不稳定 |
| 适合场景 | 求逆序对、外部排序 | 通用排序（sort 的基础） |
| 缓存友好 | 一般 | ✅ 好（原地操作） |
📊 关键用途：归并排序最大的价值不在排序本身，而在合并过程中可以顺便做很多事——比如求逆序对、求区间问题。第 43 章你会学到逆序对的两种求法，归并排序就是其中一种。
✋ 动手试试
试试 1：用归并排序对 {5, 2, 4, 7, 1, 3, 2, 6} 排序，在纸上画出递归树，写出每次 merge 后的结果。
试试 2：实现快排的 partition，用 rand() 随机选基准。测试：分别对升序数组、降序数组和随机数组跑一遍，记录运行时间。
试试 3：对比归并排序和快排的执行过程——把两种排序都加上打印语句，输出每步的数组状态，观察它们"做事顺序"的差异。
⚠️ 容易犯的错
错 1：归并排序忘记把 tmp 拷回 a
❌ 归并排序执行完了，数组 a 没变化——忘了 for (int p = l; p <= r; p++) a[p] = tmp[p];
✅ 合并完成后必须拷回去，否则递归上层用的还是旧数据
错 2：快排 partition 用 a[j] < pivot 而非 <=
❌ 用 < 的话，等于 pivot 的元素全部被分到右边，在某些情况下会导致分区极不均匀
✅ 用 <= 把等于 pivot 的元素平均分到两边，分区更均衡
错 3：递归忘了写终止条件
❌ mergeSort(l, r) 或 quickSort(l, r) 里没有 if (l >= r) return;
✅ 必须有终止条件，否则无限递归 → 爆栈（Stack Overflow）
错 4：快排基准始终选最右元素
❌ 对已排序数组会退化到 O(n²)
✅ 至少用随机化 rand()，或者直接用 sort() 不操心
📝 练习
基础题
1. 选择题
（1）归并排序的时间复杂度是：
A. O(n) B. O(n log n) C. O(n²) D. O(log n)
（2）快速排序最坏情况出现在：
A. 数组已经排好序 B. 数组随机 C. 数组所有元素相同 D. 取决于选的基准
（3）归并排序和快排的共同特点是：
A. 都是稳定排序 B. 都需要额外 O(n) 空间 C. 都用了分治思想 D. 最坏都是 O(n²)
2. 填空题
（1）分治法的三部曲是：_____ → _____ → _____。
（2）归并排序需要 O(_____) 的额外空间（用大 O 表示）。
（3）快排中，随机选基准的目的是 ____________。
提高题
3. 编程题 — 手写归并排序
输入 n 和 n 个整数，用归并排序将它们升序排列并输出。要求：完整实现 mergeSort() 和 merge() 函数，不允许使用 sort()。
4. 编程题 — 手写快速排序
同上题，但用快速排序实现。要求实现 partition() 和 quickSort()，使用随机化基准。
挑战题
5. 编程题 — 前 k 小的数
输入 n 个数和一个整数 k（1 ≤ k ≤ n ≤ 10⁵），输出最小的 k 个数（升序排列）。
提示：利用快排的 partition 思想——如果基准位置恰好是 k，那它左边的就都是最小的 k-1 个数。不需要完整排序！
（这其实就是"快速选择"算法 QuickSelect，平均 O(n)）
🧠 本章小结
分治法 = 分 → 治 → 合
归并排序：
分：从中间切开
合：合并两个有序数组
总是 O(n log n)，稳定，需要 O(n) 临时空间
快速排序：
分：选基准，小的放左，大的放右
合：不需要！（左右递归完就排好了）
平均 O(n log n)，最坏 O(n²)，随机化可避免最坏情况
手写它们的意义：理解分治、求逆序对、快速选择等变种
竞赛中推荐：直接用 sort() 除非题目有特殊要求📝 配套练习
共4题。归并1题(核心)+快排1题+分治视角2题。。★核心（课堂必做） ◆拓展（课后练习）
| 级别 | 题号 | 链接 | 覆盖知识点 |
|---|---|---|---|
| ★ 核心 | luogu-P1908 | https://hydro.ac/p/luogu-P1908 | 归并排序、逆序对、mid-i+1 |
| ◆ 拓展 | luogu-P1177 | https://hydro.ac/p/luogu-P1177 | 手写快排、划分过程 |
| ◆ 拓展 | luogu-P1115 | https://hydro.ac/p/luogu-P1115 | 分治视角最大子段和 |
| ◆ 拓展 | luogu-P1010 | https://hydro.ac/p/luogu-P1010 | 递归输出、分治表达 |
💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 3 道◆拓展题，覆盖不同变式和细节。
配套练习
共4题。归并1题(核心)+快排1题+分治视角2题。★核心（课堂必做） · ◆拓展（课后练习）
| 级别 | 题号 | 链接 | 覆盖知识点 |
|---|---|---|---|
| ★ 核心 | luogu-P1908 | https://hydro.ac/p/luogu-P1908 | 归并排序、逆序对、mid-i+1 |
| ◆ 拓展 | luogu-P1177 | https://hydro.ac/p/luogu-P1177 | 手写快排、划分过程 |
| ◆ 拓展 | luogu-P1115 | https://hydro.ac/p/luogu-P1115 | 分治视角最大子段和 |
| ◆ 拓展 | luogu-P1010 | https://hydro.ac/p/luogu-P1010 | 递归输出、分治表达 |
练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 3 道◆拓展题，覆盖不同变式和细节。
自查清单：
- [ ] 我能解释分治思想并应用于排序
- [ ] 我能手写归并排序（含 merge 函数）
- [ ] 我能手写快速排序（含 partition 函数）
- [ ] 我知道快排最坏 O(n²) 的原因和随机化避免方法
- [ ] 我能对比归并和快排的时间/空间/稳定性
- [ ] 我理解什么时候竞赛中选
sort()、什么时候要手写
🚀 下章预告：前面四种排序（冒泡、选择、插入、归并、快排）都是靠"比较"来排序的。有没有不比较也能排序的算法？有——计数排序和基数排序，它们在特定条件下能达到惊人的 O(n)！下一章，我们见识一下这些"不走寻常路"的排序方式。