Lesson 0407 · 排序算法：归并与快排

④ 数据结构与算法 — 第 7 课

1. 你用了一年 sort，它内部到底是什么

从 0002 课的 sort(a.begin(), a.end()) 开始，你已经用了几十次。但有两个问题一直没回答：

• 它为什么是 O(n log n)？
• 为什么有时候要写第三个参数 cmp，有时候又不用？

今天自己写两个 O(n log n) 的排序，你就知道了：没有任何排序能在 O(n log n) 以下完成比较排序（这是理论下界），而下面这两个算法正好达到它，只是用的「分治方式」不同。

2. 先回顾一下你已经会的三种排序

3. 分治：先拆小，再合起来

两个算法都基于同一个套路，叫分治（divide and conquer）：

1. 分：把大问题拆成两个更小的同类问题
2. 治：小到只剩 1 个元素时，它天然有序（这就是递归出口）
3. 合：把两个小答案合成大答案

区别只在第三步：归并是「先分到底，再合并有序段」；快排是「先按基准分好，再分别递归」。这也是很多人的第一个分治题（P1908 逆序对）的核心。

4. 归并排序

4.1 最关键的动作：合并两个有序数组

假设左半边和右半边各自已经有序，怎么合成一个有序的？——两个指针各指一边，每次取较小的那个。

左：1 4 7        右：2 3 9

比较 1 和 2 → 取 1
比较 4 和 2 → 取 2
比较 4 和 3 → 取 3
比较 4 和 9 → 取 4
比较 7 和 9 → 取 7
右边还剩 9  → 取 9
结果：1 2 3 4 7 9

void merge(vector<int>& a, int l, int mid, int r, vector<int>& tmp) {
    int i = l, j = mid + 1;
    int 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 t = l; t <= r; t++) a[t] = tmp[t];   // 拷回原数组
}

4.2 递归：分成两半，各自排好

void mergeSort(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (l >= r) return;            // 只剩 0 或 1 个元素，天然有序，递归出口

    int mid = (l + r) / 2;
    mergeSort(a, l, mid, tmp);         // 左半边排好
    mergeSort(a, mid + 1, r, tmp);     // 右半边排好
    merge(a, l, mid, r, tmp);          // 再把两半合并
}

int main() {
    vector<int> a = {7, 3, 9, 1, 4, 2, 8};
    vector<int> tmp(a.size());
    mergeSort(a, 0, a.size() - 1, tmp);
    for (int x : a) cout << x << " ";   // 1 2 3 4 7 8 9
}

4.3 为什么是 O(n log n)

• 每次把区间一分为二，最多分 log n 层（8 个元素分成 8→4→2→1，共 3 层）
• 每一层里，所有区间的合并加起来正好把每个元素处理一次，是 O(n)
• 所以总复杂度 O(n log n)，而且最好最坏都一样

第 1 层：7 3 9 1 4 2 8                    （1 段，8 个元素）
第 2 层：7 3 9 1 | 4 2 8                  （2 段）
第 3 层：7 3 | 9 1 | 4 2 | 8              （4 段）
第 4 层：7 | 3 | 9 | 1 | 4 | 2 | 8        （8 段，每段只剩 1 个，到底了）

然后一路合并回去：
3 7 | 1 9 | 2 4 | 8   →   1 3 7 9 | 2 4 8   →   1 2 3 4 7 8 9

5. 手推：同一组数，两种排序各走一遍

就用 4.2 节 main 里那组数：7 3 9 1 4 2 8。下面两张表里每一行，都是你可以拿纸笔自己划出来的状态。

5.1 冒泡：每轮把当前最大的「冒」到末尾

规则只有一句：从左到右两两比，前面比后面大就交换。一轮下来，剩下部分里最大的那个一定停在了最右边。

盯着第 3 轮和第 4 轮：第 3 轮结束时是 1 3 2 4 7 8 9，只有 3 和 2 还是反的；第 4 轮只交换了这一次，数组就有序了。
第 5 轮一次交换都没有——这就是「冒泡可以提前收工」的信号（本课的写法没有加这个优化，所以代码里仍然会跑满 n−1 轮）。

5.2 归并：先把段分到 1 个元素，再一段段并回来

4.3 节画的是「层」，这里换成「第几轮合并」，看数组每一轮长什么样。

看出区别了吗？冒泡一轮只让一个元素归位，一共要走 4 轮多；归并的每一轮都在合并很多小段，所以 3 轮就到头。这就是 O(n²) 和 O(n log n) 的差别在「表上的行数」里的样子。

5.3 五种排序放一起对照

「最好」这一列，原文只写明了归并（「最好最坏都一样」）。其余几格是按本课讲的写法推的：冒泡、选择每一轮都要把剩下的部分扫完，最好也省不掉，仍是 O(n²)；插入在数组已经有序时，每个元素只跟前面比一次就停，是 O(n)；快排每次都能均匀划分时是 O(n log n)。平均和最坏两列，和原文完全一致。

6. 快速排序

6.1 最关键的动作：partition（分区）

选一个元素当基准（pivot），把区间整理成三部分：[小于等于基准] [基准] [大于基准]。整理完，基准就已经在它最终该在的位置上了，不用再动。

int partition(int a[], int l, int r) {
    int pivot = a[r];              // 简单起见，拿最右边那个当基准
    int i = l;                     // i 是"小于等于区"的下一个空位

    for (int j = l; j < r; j++) {
        if (a[j] <= pivot) {
            swap(a[i], a[j]);
            i++;
        }
    }
    swap(a[i], a[r]);              // 基准放到分界点上
    return i;                      // 返回基准的最终下标
}

以 3 7 1 9 4 2 8、基准 = 8（最右）为例：i 一开始在 0

j=0  3 <=8  换到 i=0 位置：3 7 1 9 4 2 8     i=1
j=1  7 <=8  换到 i=1 位置：3 7 1 9 4 2 8     i=2
j=2  1 <=8  换到 i=2 位置：3 7 1 9 4 2 8     i=3
j=3  9  >8  跳过                         i=3
j=4  4 <=8  换到 i=3 位置：3 7 1 4 9 2 8     i=4
j=5  2 <=8  换到 i=4 位置：3 7 1 4 2 9 8     i=5

最后 swap(a[i], a[r])：3 7 1 4 2 8 9
基准 8 落在下标 5，左边全 <=8，右边全 >8，它已经归位

6.2 递归：基准两边分别再排

void quickSort(int a[], int l, int r) {
    if (l >= r) return;            // 0/1 个元素，出口

    int p = partition(a, l, r);    // 基准归位
    quickSort(a, l, p - 1);        // 左边自己排
    quickSort(a, p + 1, r);        // 右边自己排
}

注意它和归并的顺序相反：归并是「先递归到底，再合并」；快排是「先分区，再递归」。快排不需要 tmp 数组，所以额外空间只有递归栈的 O(log n)。

6.3 最坏情况：它真的会退化

如果每次选的基准都是当前区间的最大值或最小值，那么每次只能分出一个元素，递归 n 层，退化成 O(n²)。什么时候会发生？数据已经有序，而你固定取端点做基准——最典型的情况。

实测（n = 20000，数据已经升序）：

固定取末尾做基准：  103 ms 且递归深度 20000 层（再大就会爆栈）
改成随机基准：      0.0 ms

6.4 怎么修：随机基准 / 三数取中

最省事的改法：分区前随机挑一个位置，先和末尾交换，后面的逻辑一字不改。

int partitionRand(int a[], int l, int r) {
    int k = l + rand() % (r - l + 1);   // [l, r] 里随机取一个
    swap(a[k], a[r]);                   // 换到末尾，复用上面的 partition
    return partition(a, l, r);
}

工程上还有「三数取中」（取 l、mid、r 三个里的中位数当基准）等优化。不过平时写题，直接用 std::sort 就是最优解——自己写快排主要是为了理解思想。

7. 归并 vs 快排，和 std::sort 是什么关系

那 std::sort 用的是哪个？都不是纯粹的一个——它是 introsort（内省排序）：

• 主体用快排，但递归太深时自动切换成堆排序（上节课那个！）保证最坏 O(n log n)
• 区间很小时（十几个元素）改用插入排序，因为小数组上它更快

所以 std::sort 是「平均快 + 最坏也不退化」的组合拳。需要稳定就用 stable_sort（内部是归并，代价是额外空间）。

8. 两个升级用法

8.1 逆序对（归并排序的经典应用）

逆序对 = 满足 i < j 且 a[i] > a[j] 的数对个数（P1908）。暴力是 O(n²)，用归并在合并时顺手数出来：

什么时候产生逆序对？合并时，如果要去右边数组的元素，说明它比左边剩下的所有元素都小——这些全是逆序对。

long long invCnt = 0;                 // 逆序对可能很多，必须 long long

void mergeInv(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeInv(a, l, mid, tmp);
    mergeInv(a, mid + 1, r, tmp);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            invCnt += mid - i + 1;    // 右边这个比左边剩下的全都小
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int t = l; t <= r; t++) a[t] = tmp[t];
}

样例 6 / 5 4 2 6 3 1 的答案是 11。

8.2 第 k 小（快排的 partition 变体）

快排每次分区后，基准的位置是最终位置。所以只要看基准下标和 k 谁大：

• 基准下标 == k-1 → 它就是第 k 小，直接返回
• 基准下标 > k-1 → 答案在左半边，只递归左边
• 基准下标 < k-1 → 答案在右半边，只递归右边

每层只走一边，总工作量是 n + n/2 + n/4 + ... ≈ 2n，所以期望复杂度是 O(n)。STL 里现成的工具是 nth_element（P1923 可以用它快速通过）：

nth_element(a.begin(), a.begin() + k - 1, a.end());
cout << a[k - 1] << endl;      // 第 k 小的数已经就位

9. 坑点清单

• 归并必须用 tmp：直接往 a[l..r] 里写会覆盖还没读的元素；最后拷回也只拷 l..r，别从 0 开始。
• 稳定性的开关是 <=：a[i] <= a[j] 里那个等号去掉，相等的元素就会换位置，归并就不再稳定。
• 快排固定取端点 + 数据有序：每次只切掉一个元素，退化成 O(n²)，递归 n 层还可能爆栈。改随机基准或三数取中。
• partition 的 i 从 l 开始：最后那句 swap(a[i], a[r]) 不能漏，漏了基准就没归位，递归区间也会错。
• 逆序对必须 long long：个数可能非常多；样例 6 / 5 4 2 6 3 1 的答案是 11，先拿它对答案。
• nth_element 的下标是 k - 1：它是「第 k 小（从 1 数）」，写 k 会差一位。

10. 小测

11. 动手练习

卡住时的自查顺序

1. 先用 7 3 9 1 4 2 8 对着第 5 节的两张表手推一遍，看轮数和数组对不上的是哪一步。
2. 归并：下标是闭区间 [l, r] 吗？k 从 l 开始、最后只拷 l..r 吗？
3. 归并：tmp 开够了吗？用的是 vector<int> tmp(a.size()) 吗？
4. 稳定吗？比较写的是 <= 还是不小心写成了 <？
5. 快排 TLE 了？先把基准改成随机的交一次，再看递归边界 l >= r。
6. 逆序对用 long long 了吗？样例 6 / 5 4 2 6 3 1 能得 11 吗？

本课小结

• 比较排序的理论下界是 O(n log n)，归并和快排都达到了
• 归并：先递归到底，再合并两个有序段（需要 tmp，稳定，最坏也 O(n log n)）
• 快排：先按基准分区，再递归两边（原地，不稳定，最坏 O(n²)）
• 快排退化的条件是「基准总是极值」，最典型的触发场景就是「数据已有序 + 固定取端点」，后果不只是慢，还可能爆栈
• 修复方式：随机基准 / 三数取中；实战直接用 std::sort
• std::sort = 快排 + 堆排 + 插入排序（introsort）；要稳定用 stable_sort
• 两个升级应用：归并数逆序对（P1908）、partition 求第 k 小（P1923）