八大排序算法图解（上）

11.1 排序的地基：概念、稳定性与评价指标

11.1.1 什么是排序

排序（sorting）的形式化定义是：给定含有 n 个记录的序列 {R1, R2, …, Rn}，它们对应的关键字为 {K1, K2, …, Kn}，排序就是要确定一种排列 p1, p2, …, pn，使得这些关键字满足 Kp1 ≤ Kp2 ≤ … ≤ Kpn（升序）或 ≥（降序）。

这里有一个初学者常常忽略的细节：被排序的是「记录」，被比较的是「关键字」。一个学生记录可能同时有 学号、姓名、成绩三个字段，我们可以按学号排，也可以按成绩排。所以讨论排序时，永远要问一句： 「按哪个关键字排？」而一旦关键字相等，麻烦就来了——这就引出了本讲第一个、也是最容易被考倒的概念： 稳定性。

另一个必须分清的分类是内部排序（internal sorting）与外部排序（external sorting）。 如果待排序的记录全部能装进内存，排序过程不需要访问外存，就叫内部排序；如果记录多到内存一次装不下， 排序过程中必须反复在内存与外存之间搬运数据块，就叫外部排序。本讲讲的八种全是内部排序， 但归并排序的思想可以直接升级成外排序的主力（11.7.5 会讲），这也是它虽然「额外空间 O(n)」却依然不可替代的原因。

11.1.2 稳定性：一个必须掰开揉碎的定义

稳定性（stability）的定义：假设待排序序列中有两个记录 Ri 与 Rj，它们的关键字相等（Ki = Kj）， 且在排序之前 Ri 排在 Rj 之前（即 i < j）。 如果排序之后 Ri 仍然排在 Rj 之前， 则称这个排序算法是稳定的；否则称它不稳定。

请把这句话读三遍。它的关键在「关键字相等的两个记录，排序前后相对次序是否改变」—— 只有相等的时候才谈稳定性，关键字不相等时谁前谁后是排序本身决定的，谈不上稳不稳定。

为什么要在乎这个？看一个真实场景：

11.1.3 评价排序算法的四个维度

同一批数据，用不同的排序算法处理，代价可能差好几个数量级。我们主要看四个维度：

这里要特别强调一句话：「时间复杂度相同」不等于「性能相同」。冒泡、选择、插入都是 O(n²)， 但插入排序在基本有序的数据上接近 O(n)，而选择排序无论数据长什么样都要做 n(n−1)/2 次比较。 堆排序、归并排序、快速排序都是 O(n log n)，但快排的实测速度通常是堆排序的两三倍—— 因为常数不同、对 CPU 缓存的友好程度不同。所以「复杂度」是下限，不是全部。

11.1.4 本章统一约定

升序

所有演示与代码一律按从小到大排列。降序只需把比较符号反过来，不重复讲。

0 基下标

数组下标从 0 开始，长度为 n 的数组下标范围是 [0, n−1]。 注意与国内教材常见的 1 基伪代码（A[1..n]）换算。

就地排序

除特别说明外，算法直接修改传入的数组，额外空间尽量 O(1)。

区间写法

[l, r] 表示闭区间，两端都包含，长度为 r − l + 1； A[l..r] 表示这一段子数组。

「一趟」

指算法外层循环执行一次所做的事。冒泡的一趟 = 从左到右扫一遍；选择的一趟 = 选出并安放一个最小值； 插入的一趟 = 安放一个元素。

逆序对

下标 i < j 但 A[i] > A[j] 的一对元素。 逆序对的总数就是「这个序列离有序有多远」的度量，也是插入排序移动次数的下界（11.7.6 详解）。

11.2 冒泡排序：最直观，也最容易被低估

11.2.1 一句话本质与手推示例

冒泡排序（bubble sort）是所有排序里最容易讲明白的一个。它的动作只有两个：比较相邻元素、 逆序就交换。由于每一轮从左到右扫描时，较大的元素总会被一路向右换过去， 所以一轮结束时，未排序区间里最大的那个元素一定站在了区间的最右端——就像水里的气泡浮到水面。

下面拿 A = [5, 2, 9, 1, 7, 3] 手工推第 1 轮（n = 6，未排序区间 [0, 5]）：

1. 比较 A[0]=5 与 A[1]=2：5 > 2，交换 → [2, 5, 9, 1, 7, 3]。
2. 比较 A[1]=5 与 A[2]=9：5 ≤ 9，不动 → [2, 5, 9, 1, 7, 3]。
3. 比较 A[2]=9 与 A[3]=1：9 > 1，交换 → [2, 5, 1, 9, 7, 3]。
4. 比较 A[3]=9 与 A[4]=7：9 > 7，交换 → [2, 5, 1, 7, 9, 3]。
5. 比较 A[4]=9 与 A[5]=3：9 > 3，交换 → [2, 5, 1, 7, 3, 9]。

第 1 轮结束，最大值 9 停在 A[5]，它的位置再也不会变了。第 2 轮只在 [0, 4] 里扫描，把 7 送到 A[4]……如此重复 n−1 轮即可全部有序。 注意一个细节：每一轮只需要扫描到 n−1−轮数 为止， 因为后面那些位置已经是就位的最大值了，再比就是浪费。

11.2.2 交互动画：看清每一次比较与交换

下面的动画用 A = [5, 2, 9, 1, 7, 3, 8, 4, 6, 0] 演示全过程。请重点盯住画面左上的 轮次 / 比较次数 / 交换次数 / swapped 标志四个数字，以及格子下方的 已就位区间标记——它是冒泡排序「每一轮确定一个最终位置」的直接证据。 观察一下 0 这个最小值：它一开始躺在最后一个位置，每一轮只能往前挪一格，这恰好说明了冒泡排序最坏情况下的「慢」。

看完动画后请回答两个问题：① 第 1 轮做了多少次比较？② 整个过程中 swapped 标志有没有变成过 false？ 答案分别是 9 次和「没有」——因为 0 需要 9 轮才能挪到最前面，每一轮都至少发生了一次交换。 这也解释了为什么动画里没能演示出「提前结束」：想看到那个效果，得换成几乎有序的数据。

11.2.3 完整 C++ 实现（基础版 + 优化版 + 变体）

下面的代码给出了三个版本：bubbleBasic 是原始版本，bubbleSort 加了 swapped 标志，bubbleBackward 是从后往前扫描的变体 （它每轮把最小值送到最前面，效果等价）。三个版本都输出比较与交换次数，方便你对照动画里的数字。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   冒泡排序（升序）
   核心：反复扫描未排序区间，相邻两两比较，逆序就交换
   ============================================================ */

/* 版本 1：原始冒泡。无论数据是否有序，都要老老实实跑满 n-1 轮，
   比较次数恒为 n(n-1)/2，最好情况也是 O(n^2)。 */
void bubbleBasic(vector<int>& a, long long& cmp, long long& swp) {
    int n = a.size();
    cmp = swp = 0;
    for (int i = 0; i < n - 1; ++i) {          // 一共 n-1 轮
        for (int j = 0; j < n - 1 - i; ++j) {  // 后面 i 个已经就位，不用再比
            ++cmp;
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                ++swp;
            }
        }
    }
}

/* 版本 2：带 swapped 标志的优化版。
   某一趟从头到尾没有发生交换 → 说明序列已经有序，立即结束。
   于是「已经有序」的输入只需 1 趟 n-1 次比较，最好情况降为 O(n)。 */
void bubbleSort(vector<int>& a, long long& cmp, long long& swp) {
    int n = a.size();
    cmp = swp = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;                  // 本趟是否发生过交换
        for (int j = 0; j < n - 1 - i; ++j) {
            ++cmp;
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                ++swp;
                swapped = true;
            }
        }
        if (!swapped) break;                   // 本趟无交换 → 提前收工
    }
}

/* 版本 3：从后往前扫描的变体。
   每轮把「未排序区间的最小值」冒到区间最前面，效果与版本 2 等价。
   有些教材用它来配合「正向 + 反向交替」的鸡尾酒排序（cocktail sort）。 */
void bubbleBackward(vector<int>& a, long long& cmp, long long& swp) {
    int n = a.size();
    cmp = swp = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = n - 1; j > i; --j) {      // 从右往左
            ++cmp;
            if (a[j - 1] > a[j]) {
                swap(a[j - 1], a[j]);
                ++swp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

/* 顺带记录一个「本趟是否有序」的更强优化：
   记录最后发生交换的位置 lastSwap，下一趟只需扫到 lastSwap 即可，
   因为 lastSwap 之后的元素本趟已经确认有序。 */
void bubbleWithLastSwap(vector<int>& a, long long& cmp, long long& swp) {
    int n = a.size();
    cmp = swp = 0;
    int bound = n - 1;                         // 本趟需要扫描的右边界
    while (bound > 0) {
        int lastSwap = 0;
        for (int j = 0; j < bound; ++j) {
            ++cmp;
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                ++swp;
                lastSwap = j;                  // 记住最后一次交换的位置
            }
        }
        bound = lastSwap;                      // 后面都排好了，缩小边界
    }
}

static void printArr(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); ++i) cout << (i ? ", " : "") << a[i];
    cout << "]";
}

int main() {
    vector<int> raw = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0};
    long long cmp = 0, swp = 0;

    vector<int> a = raw;
    bubbleSort(a, cmp, swp);
    cout << "优化版冒泡   : "; printArr(a);
    cout << "  比较 " << cmp << " 次，交换 " << swp << " 次\n";   // 45 次比较、25 次交换

    a = raw;
    bubbleBasic(a, cmp, swp);
    cout << "原始版冒泡   : "; printArr(a);
    cout << "  比较 " << cmp << " 次，交换 " << swp << " 次\n";   // 恒为 45 次比较

    /* 最好情况对比：已经有序的输入 */
    vector<int> sorted = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    a = sorted; bubbleSort(a, cmp, swp);
    cout << "有序数据·优化版：比较 " << cmp << " 次，交换 " << swp << " 次\n"; // 9 次比较、0 次交换
    a = sorted; bubbleBasic(a, cmp, swp);
    cout << "有序数据·原始版：比较 " << cmp << " 次，交换 " << swp << " 次\n"; // 45 次比较

    /* 最坏情况：完全逆序 */
    vector<int> rev = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    a = rev; bubbleSort(a, cmp, swp);
    cout << "逆序数据·优化版：比较 " << cmp << " 次，交换 " << swp << " 次\n"; // 45 次比较、45 次交换

    a = raw; bubbleBackward(a, cmp, swp);
    cout << "从后往前变体 : "; printArr(a);
    cout << "  比较 " << cmp << " 次，交换 " << swp << " 次\n";

    a = raw; bubbleWithLastSwap(a, cmp, swp);
    cout << "lastSwap 优化: "; printArr(a);
    cout << "  比较 " << cmp << " 次，交换 " << swp << " 次\n";
    return 0;
}

11.2.4 复杂度、稳定性与易错点

空间复杂度 O(1)（只用了一个临时变量做交换），稳定——因为交换的条件写的是 a[j] > a[j+1] 而不是 ≥：只有严格逆序才交换， 于是关键字相等的两个元素永远不会互相跨过，相对次序天然保持不变。

11.3 简单选择排序：交换次数最少的 O(n²) 算法

11.3.1 一句话本质与手推示例

选择排序（selection sort）和冒泡排序的想法很接近，都是「每一轮确定一个元素的最终位置」， 但动作完全不同：冒泡是边走边换，一轮可能换很多次；选择排序是先看完整轮、记住最小值的下标， 最后只换一次。这个差别带来一个非常实用的性质：交换次数最多 n−1 次。

用 A = [5, 2, 9, 1, 7, 3] 手推一遍：

1. 第 1 轮：未排序区间 [0, 5]。先假设 minIdx = 0（值 5）， 依次比较 A[1]=2（更小，minIdx = 1）、A[2]=9（不小）、 A[3]=1（更小，minIdx = 3）、A[4]=7、A[5]=3（都不小）。 共比较 5 次，得到最小值下标 3。交换 A[0] 与 A[3] → [1, 2, 9, 5, 7, 3]。
2. 第 2 轮：区间 [1, 5]，最小值是 A[1] = 2，本来就在位，不交换。
3. 第 3 轮：区间 [2, 5]，最小值是 A[5] = 3，交换 A[2] 与 A[5] → [1, 2, 3, 5, 7, 9]。
4. 第 4 轮：区间 [3, 5]，最小值 A[3] = 5 在位，不交换。
5. 第 5 轮：区间 [4, 5]，最小值 A[4] = 7 在位，不交换。排序完成。

比较次数：5 + 4 + 3 + 2 + 1 = 15 = n(n−1)/2，一次都没少；交换次数：只有 2 次。 这就是选择排序的画像——比较一点都不省，但搬运极其节省。

11.3.2 交互动画

下面的动画用 A = [5, 2, 9, 1, 7, 3, 8, 4, 6, 0] 演示。请留意两个指针： 橙色 j 是扫描指针，蓝色 min 是「目前见过的最小值」。 特别注意 min 的移动方式——它是跳跃式的，而且每次移动都只改一个下标变量，数组一个元素都没动。

11.3.3 为什么「交换次数最多 n−1 次」很值钱

先明确「交换」和「比较」的代价差异。比较两个关键字通常只是读两个数、做一次减法； 而交换两个记录意味着要搬动整条记录（可能几百字节）。如果记录很大、或者交换涉及写磁盘， 一次交换的代价可能是几万次比较。在这种场景下，选择排序的「n−1 次交换上限」就成了硬指标。

把它和冒泡对比一下：同样是 n = 1000 的逆序数据，冒泡排序需要 n(n−1)/2 ≈ 50 万次交换，而选择排序最多 999 次。差 500 倍。 所以老教材里常有一句结论：「当记录本身很大、移动代价远高于比较代价时，选择排序反而优于冒泡排序。」

11.3.4 不稳定性：一个反例讲透

选择排序不稳定。很多同学不理解：明明只是「选出最小值换到前面」，怎么会破坏次序？关键就在 「交换」是长距离的——它会把一个元素越过一大段，其中包括与它关键字相等的元素。

取序列 [5a, 5b, 2]（5a 与 5b 关键字相同，5a 在 5b 前面）。 第 1 轮：最小值是 A[2] = 2，把 A[0] 与 A[2] 交换， 得到 [2, 5b, 5a]。看，5a 被换到了 5b 后面，相对次序翻转了，算法不稳定。

再强调一遍它的机理：交换发生在「区间首」与「最小值所在位置」之间，这两个位置可能相隔很远， 中间夹着的相等元素就被无情地跨过了。归并排序之所以稳定，是因为它只做「相邻段的顺序搬运」， 从不长距离跳跃。

11.3.5 完整 C++ 实现与复杂度

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   简单选择排序（升序）
   每轮在未排序区间 [i, n-1] 中选出最小值，与 A[i] 交换
   比较次数恒为 n(n-1)/2；交换次数最多 n-1 次
   ============================================================ */
void selectionSort(vector<int>& a, long long& cmp, long long& swp) {
    int n = a.size();
    cmp = swp = 0;
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;                        // 先假设 A[i] 最小
        for (int j = i + 1; j < n; ++j) {
            ++cmp;
            if (a[j] < a[minIdx]) minIdx = j;  // 只记下标，不动数组
        }
        if (minIdx != i) {                     // 最小元素已在原位就不必交换
            swap(a[i], a[minIdx]);
            ++swp;
        }
    }
}

/* 变体：每一轮同时找最小值和最大值，从两端向中间收缩。
   比较次数仍是 O(n^2)，但常数约为原来的一半（n/2 轮，每轮约 n 次比较）——
   这是「锦标赛」式的双向选择排序。 */
void selectionSortBidirectional(vector<int>& a, long long& cmp, long long& swp) {
    int n = a.size();
    cmp = swp = 0;
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int minIdx = lo, maxIdx = lo;
        for (int j = lo; j <= hi; ++j) {
            ++cmp;
            if (a[j] < a[minIdx]) minIdx = j;
            ++cmp;
            if (a[j] > a[maxIdx]) maxIdx = j;
        }
        swap(a[lo], a[minIdx]); ++swp;
        /* 注意：如果最大值原本就在 lo 位置，它已经被换到 minIdx 去了，要修正下标 */
        if (maxIdx == lo) maxIdx = minIdx;
        swap(a[hi], a[maxIdx]); ++swp;
        ++lo; --hi;
    }
}

static void printArr(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); ++i) cout << (i ? ", " : "") << a[i];
    cout << "]";
}

int main() {
    vector<int> raw = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0};
    long long cmp = 0, swp = 0;

    vector<int> a = raw;
    selectionSort(a, cmp, swp);
    cout << "选择排序     : "; printArr(a);
    cout << "  比较 " << cmp << " 次，交换 " << swp << " 次\n";      // 45 次比较、7 次交换

    /* 已经有序的输入：比较次数一次都不会少！ */
    vector<int> sorted = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    a = sorted; selectionSort(a, cmp, swp);
    cout << "有序数据     : 比较 " << cmp << " 次，交换 " << swp << " 次\n"; // 仍是 45 次比较

    a = raw; selectionSortBidirectional(a, cmp, swp);
    cout << "双向选择排序 : "; printArr(a);
    cout << "  比较 " << cmp << " 次，交换 " << swp << " 次\n";

    /* 演示不稳定：用 (关键字, 原始编号) 的形式观察相等关键字的相对次序 */
    vector<pair<int, char>> rec = {{5, 'a'}, {5, 'b'}, {2, 'c'}};
    int n = rec.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j)
            if (rec[j].first < rec[minIdx].first) minIdx = j;
        if (minIdx != i) swap(rec[i], rec[minIdx]);
    }
    cout << "不稳定验证   : ";
    for (auto& p : rec) cout << p.first << p.second << " ";   // 2c 5b 5a —— 次序被翻转
    cout << "\n";
    return 0;
}

11.4 直接插入排序：工业界最被低估的排序

11.4.1 一句话本质与手推示例

插入排序（insertion sort）模仿的是人摸扑克牌的动作：左手是已经理好的牌，右手摸到一张新牌， 就从右往左比过去，找到该插的位置塞进去。它的动作只有两个：比较与右移（不是交换！）。 代码短到只有 5 行，但它是 std::sort、qsort 这类工业级排序在小数组上的收尾选择。

用 A = [5, 2, 9, 1, 7] 手推（| 左边是有序区）：

1. 初始：[5 | 2, 9, 1, 7]，把 A[0] 单独视为有序区。
2. i = 1，key = 2：与 A[0] = 5 比较，5 > 2 → 5 右移 → [_, 5 | 9, 1, 7]， j 退到 −1（越界），把 key 写入 A[0] → [2, 5 | 9, 1, 7]。比较 1 次、移动 1 次。
3. i = 2，key = 9：与 A[1] = 5 比较，5 ≤ 9 → 停，key 就地写入 A[2] → [2, 5, 9 | 1, 7]。比较 1 次、移动 0 次。
4. i = 3，key = 1：与 9 比（9 > 1，9 右移）、与 5 比（右移）、与 2 比（右移），j 退到 −1， 写入 A[0] → [1, 2, 5, 9 | 7]。比较 3 次、移动 3 次。
5. i = 4，key = 7：与 9 比（右移）、与 5 比（5 ≤ 7，停），写入 A[3] → [1, 2, 5, 7, 9]。比较 2 次、移动 1 次。

对比第 2 步和第 4 步，你会发现一个规律：如果一个元素本来就该待在原地，它只花 1 次比较； 而如果它需要跨越 k 个元素，就要花 k 次移动。所以总代价约等于「逆序对总数」—— 这正是插入排序「基本有序时接近 O(n)」的原因。

11.4.2 交互动画

动画里额外画了两个视觉元素：左上角紫色方块是暂存变量 key，数组中的虚线框是「坑」—— 也就是元素被搬走后空出来的位置。请特别注意：插入排序靠的是移动而不是交换， 每一次右移都会让坑往左挪一格，直到 key 落进最后的坑。

11.4.3 为什么「基本有序」时接近 O(n)

先把插入排序的代价算清楚。设 M 为总移动次数、C 为总比较次数。内层循环 while (a[j] > key) 每成功一次就移动一个元素，所以 移动次数 = 「需要跨过的元素个数」的总和。精确地说：

为什么 M 恰好等于逆序对总数？因为每移动一个元素 A[j] 到 A[j+1]， 就说明 A[j] > key 且 j 在 key 原来的位置之前——这正是一个逆序对； 而每个逆序对恰好会被处理一次。于是有三种情况：

• 已经有序：逆序对 = 0，M = 0，每个元素只比较 1 次就停，总比较 n−1 次 → O(n)。
• 完全逆序：逆序对 = n(n−1)/2，M = n(n−1)/2，比较约 n(n−1)/2 次 → O(n²)。
• 平均随机：逆序对的期望是 n(n−1)/4 → O(n²)，但系数只有冒泡的一半左右。

这就解释了两件事：① 为什么插入排序是 O(n²) 家族里平均最快的；② 为什么它会成为「小区间收尾」的首选——当一个数组被快排切到只剩 16 个元素时， 这段小区间内部已经相当随机但规模极小，插入排序的低常数会碾压递归开销。

11.4.4 带哨兵的写法（1 基下标）

国内教材通常用 1 基下标，并在 A[0] 处放一个哨兵（sentinel）： 把当前要插入的元素先存进 A[0]，这样内层循环就可以省掉 j ≥ 1 这个边界判断—— 因为 A[0] 就是 key 自己，比较到它一定会停。这是一个典型的「用一点空间换掉一个判断」的技巧， 考试里经常考「哨兵的作用是什么」。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   直接插入排序（升序，0 基下标版本）
   把 A[i] 插入前面已经有序的 A[0..i-1] 中
   比较次数与移动次数都等于「逆序对数量」量级
   ============================================================ */
void insertionSort(vector<int>& a, long long& cmp, long long& mv) {
    int n = a.size();
    cmp = mv = 0;
    for (int i = 1; i < n; ++i) {
        int key = a[i];                        // 暂存待插入元素
        int j = i - 1;
        while (j >= 0 && a[j] > key) {         // 严格大于才右移 → 保证稳定
            ++cmp;
            a[j + 1] = a[j];                   // 元素右移一格（不是交换！）
            ++mv;
            --j;
        }
        if (j >= 0) ++cmp;                      // 最后一次比较（因 a[j] <= key 而停下）
        a[j + 1] = key;                        // 落进最后的空位
    }
}

/* ============================================================
   教材风格：1 基下标 + 哨兵 A[0]
   a[1..n] 存数据，a[0] 空出来当哨兵
   哨兵的作用：省掉内层循环的 j >= 1 边界判断
   ============================================================ */
void insertionSortSentinel(vector<int>& a, int n, long long& cmp, long long& mv) {
    cmp = mv = 0;
    for (int i = 2; i <= n; ++i) {
        if (a[i] >= a[i - 1]) { ++cmp; continue; }   // 小优化：已经有序就不必搬
        a[0] = a[i];                                // 把 key 放进哨兵位
        int j = i - 1;
        while (a[j] > a[0]) {                       // 不必判断 j >= 1：a[0] 一定不满足条件
            ++cmp;
            a[j + 1] = a[j];
            ++mv;
            --j;
        }
        ++cmp;
        a[j + 1] = a[0];                            // 把哨兵里的 key 放回正确位置
    }
}

/* ============================================================
   折半插入排序：用二分查找定位插入点
   比较次数从 O(n^2) 降到 O(n log n)，但移动次数一点没少（仍是 O(n^2)）
   ============================================================ */
void binaryInsertionSort(vector<int>& a, long long& cmp, long long& mv) {
    int n = a.size();
    cmp = mv = 0;
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int lo = 0, hi = i;                     // 在有序区 [0, i-1] 中找插入位置，区间用 [lo, hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            ++cmp;
            if (a[mid] <= key) lo = mid + 1;    // 用 <= 保证即使相等也往右走 → 稳定
            else hi = mid;
        }
        /* 插入位置是 lo，把 [lo, i-1] 整体右移一格 */
        for (int j = i; j > lo; --j) { a[j] = a[j - 1]; ++mv; }
        a[lo] = key;
    }
}

static void printArr(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); ++i) cout << (i ? ", " : "") << a[i];
    cout << "]";
}

int main() {
    vector<int> raw = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0};
    long long cmp = 0, mv = 0;

    vector<int> a = raw;
    insertionSort(a, cmp, mv);
    cout << "直接插入排序 : "; printArr(a);
    cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";      // 31 次比较、25 次移动

    vector<int> sorted = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    a = sorted; insertionSort(a, cmp, mv);
    cout << "基本有序     : 比较 " << cmp << " 次，移动 " << mv << " 次\n"; // 9 次比较、0 次移动 → O(n)

    vector<int> rev = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    a = rev; insertionSort(a, cmp, mv);
    cout << "完全逆序     : 比较 " << cmp << " 次，移动 " << mv << " 次\n"; // 45 次比较、45 次移动 → O(n^2)

    /* 哨兵版：a[1..n] 存数据 */
    vector<int> b(raw.size() + 1, 0);
    for (size_t i = 0; i < raw.size(); ++i) b[i + 1] = raw[i];
    insertionSortSentinel(b, (int)raw.size(), cmp, mv);
    cout << "哨兵版       : ";
    for (size_t i = 1; i < b.size(); ++i) cout << b[i] << (i + 1 < b.size() ? " " : "");
    cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";

    a = raw; binaryInsertionSort(a, cmp, mv);
    cout << "折半插入排序 : "; printArr(a);
    cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";      // 比较次数明显下降
    return 0;
}

11.4.5 折半插入排序：省比较、不省移动

插入排序的「查找插入位置」是在一个有序区里做的，那为什么不用二分查找呢？当然可以，这就得到了 折半插入排序（binary insertion sort）。它把比较次数从 O(n²) 降到 O(n log n)：每个元素用 ⌈log2 i⌉ 次比较定位，总共约 n log n 次比较。

但是！移动次数一次都没少，仍然是 O(n²)。因为找到位置之后，还是要老老实实把 A[lo..i−1] 整段右移一格。所以折半插入排序的总时间复杂度仍然是 O(n²)， 只是把「比较」这一项的系数降下来了。结论：折半插入排序适用于「比较很贵、移动很便宜」的场景 （比如关键字是长字符串），而对普通整数几乎没有提升。

11.4.6 稳定性与工业界的真实用法

插入排序是稳定的：内层循环的条件是 a[j] > key（严格大于）， 遇到相等元素立即停下，key 就落在它右边，绝不会跨过去。这一点和冒泡一样，是靠「不写等号」换来的。

工业实现里插入排序有三个典型用法：

• 小数组直接用它：Java 的 Arrays.sort（对象数组，TimSort）在子数组长度 < 32 时切到插入排序；C++ 的 std::sort（introsort）在区间长度 < 16 时切到插入排序。 原因就是它常数小、无递归开销、对已经部分有序的数据极其高效。
• 作为「基本有序」的收尾：TimSort（Python、Java 对象排序、V8 的 Array.prototype.sort） 先扫出天然的升/降序「run」，再用插入排序把短的 run 补长，最后归并。
• 在线（online）排序：数据是一个一个到达的，插入排序可以在收到第 k 个元素时立刻保持前 k 个有序， 不需要等到全部数据到齐。堆排序、快排都做不到这一点（它们是离线算法）。

11.5 希尔排序：给插入排序装上加速器

11.5.1 一句话本质与手推示例

希尔排序（Shell sort，1959 年由 Donald Shell 提出）又叫缩小增量排序（diminishing increment sort）。 它的出发点是一个观察：插入排序在「基本有序」的序列上极快，但在完全乱序的序列上很慢， 因为一个元素要挪到它该去的位置，只能一格一格地挪。

希尔排序的想法是：既然一次只能挪一格太慢，那就先让元素能大跨度地移动。 取 gap = 5 时，A[0] 与 A[5] 是同组的， 它们可以直接交换——一步跨越 5 个位置！等到大 gap 的几趟做完，序列已经「大的在后面、小的在前面」， 逆序对大幅减少；最后 gap = 1 的那一趟插入排序就非常轻松了。

用 A = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]（n = 10）手推：

1. gap = 5：分为 5 组 —— {A[0],A[5]} = {8,3}、{A[1],A[6]} = {9,5}、{A[2],A[7]} = {1,4}、 {A[3],A[8]} = {7,6}、{A[4],A[9]} = {2,0}。每组只有两个元素，各自排好，得到 [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]。注意 0 一步就从下标 9 跨到了下标 4。
2. gap = 2：分为 2 组，奇数下标一组、偶数下标一组，各自做插入排序，得到 [0, 2, 1, 4, 3, 5, 6, 7, 8, 9]（详细过程见动画）。此时序列已经「大致有序」。
3. gap = 1：整体做一次插入排序。因为只剩下少量逆序对，只要 4 次移动就完成了。

对比一下：如果直接用插入排序处理这个序列，需要 25 次左右的移动；希尔排序三趟加起来只有 19 次左右。 数据规模越大，这个差距越夸张。

11.5.2 交互动画：看清 gap 与分组

下面的动画用 A = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]， 增量序列 5 → 2 → 1。颜色相同的格子属于同一组（下标对 gap 取模相同）， 格子下方还标出了组号。请重点观察：同一个组内的元素，虽然下标相隔很远，但组内是严格按插入排序处理的。

11.5.3 增量序列怎么选：复杂度的命门

希尔排序的时间复杂度完全取决于增量序列的选取，这也是它特别有意思的地方—— 同一份代码，换一个 gap 序列，复杂度可能从 O(n²) 变成 O(n^1.3)。

11.5.4 为什么希尔排序不稳定，又为什么比插入快

先回答「为什么不稳定」：希尔排序会把序列按 gap 分成多个组， 关键字相同的元素很可能被分到不同的组，而每个组是「独立」排序的—— 组与组之间的相对次序完全由「下标对 gap 取模」这个与关键字无关的规则决定。 一旦后续的趟把它们搬进同一个组，谁前谁后就可能和原来相反。

标准教材给的反例是 [49a, 38, 65, 97, 76, 13, 27, 49b]（n = 8，两个 49）， 增量序列取 5 → 3 → 1。我们完整推一遍：

1. gap = 5：分组 {A[0],A[5]}={49a,13}、{A[1],A[6]}={38,27}、{A[2],A[7]}={65,49b}。 组内插入排序后得到 [13, 27, 49b, 97, 76, 49a, 38, 65]。
2. gap = 3：分组 {A[0],A[3],A[6]}、{A[1],A[4],A[7]}、{A[2],A[5]}。 注意 49b 在下标 2、49a 在下标 5，它们这一次被分到了同一组！ 组内比较时 A[2] = 49b 与 key = 49a 满足 49b ≤ 49a（相等）， 于是 49a 停在 49b 后面，不再往前移动。这一趟之后： [13, 27, 49b, 38, 65, 49a, 97, 76]。
3. gap = 1：普通插入排序收尾，得到 [13, 27, 38, 49b, 49a, 65, 97, 76]。

最终结果里 49b 排在了 49a 的前面，而原始序列中 49a 在下标 0、49b 在下标 7 —— 相对次序被颠倒了，所以希尔排序不稳定。

再回答「为什么比插入排序快」：两个原因。

• 一趟大 gap 就能消除大量逆序对。插入排序的移动次数等于逆序对总数，而且每次只能把元素挪一格。 希尔排序在大 gap 时，一次移动可以让元素跨越 gap 个位置，等于「一次移动消灭多个逆序对」。
• 让序列变得「基本有序」，为最后一趟铺路。最后一趟 gap = 1 面对的不再是随机序列， 而是逆序对很少的序列，于是 O(n) 级别的插入排序就够用了。这就是「先粗调、再细调」的思想。

还有个常被忽略的优点：希尔排序是原地排序，空间 O(1)，且代码只是在插入排序外面加了一层 gap 循环。 在嵌入式或对递归过敏的场景，它比快排、归并更受欢迎。

11.5.5 完整 C++ 实现（三种增量序列对比）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   希尔排序（缩小增量排序）
   统一接口：gap 序列由参数传入，最后一趟必须 gap == 1
   ============================================================ */

/* 通用的「按给定增量序列做希尔排序」，并统计比较 / 移动次数 */
void shellSortWithGaps(vector<int>& a, const vector<int>& gaps,
                       long long& cmp, long long& mv) {
    int n = a.size();
    cmp = mv = 0;
    for (size_t gi = 0; gi < gaps.size(); ++gi) {
        int gap = gaps[gi];
        if (gap <= 0 || gap >= n) continue;
        for (int i = gap; i < n; ++i) {        // 对每一组做插入排序
            int key = a[i];
            int j = i - gap;
            while (j >= 0) {
                ++cmp;
                if (a[j] <= key) break;        // 组内已就位（写成 <= 而不是 < 也不会更稳定）
                a[j + gap] = a[j];             // 同组内右移 gap 格
                ++mv;
                j -= gap;
            }
            a[j + gap] = key;
        }
    }
}

/* ① 折半增量：n/2, n/4, ..., 1 —— 最经典，最坏 O(n^2) */
vector<int> gapsShell(int n) {
    vector<int> g;
    for (int h = n / 2; h > 0; h /= 2) g.push_back(h);
    if (g.empty() || g.back() != 1) g.push_back(1);
    return g;
}

/* ② Hibbard 增量：2^k - 1, ..., 7, 3, 1 —— 最坏 O(n^1.5) */
vector<int> gapsHibbard(int n) {
    vector<int> g;
    for (int h = 1; h < n; h = h * 2 + 1) g.push_back(h);   // 1,3,7,15,...
    reverse(g.begin(), g.end());                            // 从大到小
    return g;
}

/* ③ Sedgewick 增量：1, 5, 19, 41, 109, 209, ... —— 最坏约 O(n^(4/3)) */
vector<int> gapsSedgewick(int n) {
    vector<int> g;
    for (int k = 0; ; ++k) {
        int h;
        if (k % 2 == 0) { int t = 1; for (int i = 0; i < k / 2 + 1; ++i) t *= 2; h = 1 + 9 * (t - 1); }
        else            { int t = 1; for (int i = 0; i < (k + 1) / 2 + 1; ++i) t *= 2; h = 1 + 8 * t - 6 * (t / 2); }
        if (h >= n) break;
        g.push_back(h);
    }
    if (g.empty() || g.back() != 1) g.push_back(1);
    reverse(g.begin(), g.end());
    return g;
}

/* Knuth 增量：h = 3h + 1，即 1, 4, 13, 40, 121, ... —— 工程上最常用 */
vector<int> gapsKnuth(int n) {
    vector<int> g;
    int h = 1;
    while (h < n) { g.push_back(h); h = h * 3 + 1; }
    if (g.empty()) g.push_back(1);
    reverse(g.begin(), g.end());
    return g;
}

static void printArr(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); ++i) cout << (i ? ", " : "") << a[i];
    cout << "]";
}
static void printGaps(const char* name, const vector<int>& g) {
    cout << name << " 增量序列: ";
    for (size_t i = 0; i < g.size(); ++i) cout << g[i] << (i + 1 < g.size() ? " -> " : "");
    cout << "\n";
}

int main() {
    vector<int> raw = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
    long long cmp = 0, mv = 0;
    int n = raw.size();

    vector<int> g1 = gapsShell(n), g2 = gapsHibbard(n), g3 = gapsKnuth(n), g4 = gapsSedgewick(n);
    printGaps("折半    ", g1);
    printGaps("Hibbard ", g2);
    printGaps("Knuth   ", g3);
    printGaps("Sedgewick", g4);

    vector<int> a = raw; shellSortWithGaps(a, g1, cmp, mv);
    cout << "折半增量结果   : "; printArr(a); cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";

    a = raw; shellSortWithGaps(a, g2, cmp, mv);
    cout << "Hibbard 结果   : "; printArr(a); cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";

    a = raw; shellSortWithGaps(a, g3, cmp, mv);
    cout << "Knuth 结果     : "; printArr(a); cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";

    a = raw; shellSortWithGaps(a, g4, cmp, mv);
    cout << "Sedgewick 结果 : "; printArr(a); cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";

    /* 对照：用 gap=1 的「假希尔」——其实等价于直接插入排序 */
    vector<int> onlyOne; onlyOne.push_back(1);
    a = raw; shellSortWithGaps(a, onlyOne, cmp, mv);
    cout << "只有 gap=1     : "; printArr(a); cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";

    /* 大规模对比：希尔排序 vs 纯插入排序 */
    const int N = 20000;
    vector<int> big(N);
    for (int i = 0; i < N; ++i) big[i] = (i * 7919) % N;    // 伪随机排列
    a = big; shellSortWithGaps(a, g3, cmp, mv);
    bool ok1 = true;
    for (int i = 1; i < N; ++i) if (a[i - 1] > a[i]) ok1 = false;
    cout << "\nn = " << N << " 时 Knuth 增量希尔排序：比较 " << cmp << " 次，移动 " << mv
         << " 次，有序性校验 " << (ok1 ? "通过" : "失败") << "\n";
    return 0;
}

11.6 堆排序：把数组当成一棵完全二叉树

11.6.1 完全二叉树的数组表示与下标关系

堆排序（heap sort）的全部魔法都建立在一句话上：一棵完全二叉树可以被一个数组「无指针」地表示出来。 因为完全二叉树的结点是从上到下、从左到右逐层填满的，没有任何「空洞」， 所以只要按层序把结点依次放进数组，父子关系就可以用纯算术算出来，一个指针都不用存。

三条关系必须背下来（0 基下标）：

左孩子

left(i) = 2i + 1，越界（≥ n）说明没有左孩子。

右孩子

right(i) = 2i + 2，越界说明没有右孩子。

父结点

parent(i) = (i − 1) / 2（整数除法，向下取整）。

最后一个非叶结点

n/2 − 1（整除）。它的所有后继结点都是叶子，这个下标是建堆的起点。

叶子结点数

⌈n/2⌉；非叶结点数 ⌊n/2⌋。

11.6.2 大根堆与小根堆

大根堆（max-heap）：一棵完全二叉树，且每个结点的关键字都 ≥ 它的两个孩子， 即 A[i] ≥ A[2i+1] 且 A[i] ≥ A[2i+2]。 小根堆（min-heap）把不等号反过来。

三条必须记牢的性质：

• 堆顶是极值：大根堆的 A[0] 一定是全体最大值，小根堆的 A[0] 是最小值。O(1) 取极值，这是堆的价值所在。
• 堆不是排序数组：堆只约束「父子之间」的大小关系，兄弟之间、堂兄弟之间毫无约束。 所以 [9, 7, 8, 6, 2, 3, 5] 与 [9, 8, 7, 6, 2, 3, 5] 都是合法的大根堆。
• 中序遍历不有序：堆不是二叉排序树（BST），不能在堆上做「查找某个值」的操作。

11.6.3 建堆为什么是 O(n)（本节最硬的推导）

先看建堆的做法：从最后一个非叶结点 ⌊n/2⌋ − 1 开始，从后往前对每个结点执行一次 「下沉（sift down）」，直到根结点。为什么是从后往前，而不是从根开始？ 因为下沉操作有一个前提：被下沉结点的左右子树本身必须已经是合法的堆。 叶子天然是堆，所以从后往前处理，轮到某个结点时它的左右子树必然已经调整好了。

很多同学第一次算都会算成 O(n log n)：一共约 n/2 个非叶结点， 每个最多下沉 log n 层，乘起来不就是 O(n log n) 吗？ 这个估计太粗糙了——它默认了「每个结点都下沉满 log n 层」，而事实上绝大多数结点离叶子很近，根本下沉不了几层。

精确的求法是这样的。我们按「高度」给结点分组：

1. 定义结点的高度 h = 它到最远叶子的边数。一个高度为 h 的结点，最多下沉 h 层。
2. 在完全二叉树中，高度为 h 的结点大约有 ⌈n / 2^h+1⌉ 个—— 高度越大，这样的结点越少，而且是以 2 的幂次急剧减少。
3. 于是总代价
   T(n) = Σ_h=0^{⌊log n⌋} ⌈n / 2^h+1⌉ · O(h) 　=　O( n · Σ_h≥0 h / 2^h+1 )　=　O( n/2 · Σ_h≥0 h / 2^h )
4. 关键在最后那个级数。Σ_h≥0 h / 2^h 是一个收敛的级数，其值为 2：
   由 Σ_h≥0 x^h = 1/(1−x) 两边求导得 Σ_h≥1 h·x^h−1 = 1/(1−x)²， 两边乘 x 得 Σ_h≥0 h·x^h = x/(1−x)²， 代入 x = 1/2 得到 (1/2)/(1/2)² = 2。
5. 所以 T(n) = O(n/2 × 2) = O(n)。

用一句大白话总结：「深度大的结点很多但几乎不用下沉，需要下沉很多层的结点极少」， 两边的 trade-off 恰好让总和收敛到一个与 n 成正比的常数。这就是建堆只需要 O(n) 的原因， 也是堆排序「总复杂度 O(n log n)，而不是 O(n log n) 建堆 + O(n log n) 排序 = 常数翻倍」的原因。

11.6.4 交互动画：数组 + 完全二叉树双视图

下面这个动画同时画出数组和它对应的完全二叉树，两边同步高亮，你可以直接看到下标关系。 动画分两个阶段：

• 建堆阶段：从最后一个非叶结点 ⌊10/2⌋ − 1 = 4 开始，倒序对 4、3、2、1、0 号结点依次下沉。
• 排序阶段：反复执行「堆顶 ↔ 堆的最后一个元素交换 → 堆规模减一 → 新堆顶下沉」。 注意被淡化（变灰）的结点就是「已经脱离堆、进入已排序区」的元素。

11.6.5 完整 C++ 实现

代码分成三块：siftDown（把一个结点往下调整到位）、buildHeap（自底向上建堆）、 heapSort（交换 + 缩小 + 下沉）。请特别注意 siftDown 里的 sz 参数—— 它是「当前堆的有效规模」，排序阶段这个值会不断缩小，这正是「已排序区不参与堆调整」的实现方式。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   堆排序（升序 → 用大根堆）
   下标关系（0 基）：左孩子 2i+1，右孩子 2i+2，父结点 (i-1)/2
   ============================================================ */

/* 下沉：把下标 p 的元素往下调整，使 [0, sz) 重新成为大根堆
   前提：p 的左右子树都已经是合法的大根堆 */
void siftDown(vector<int>& a, int p, int sz, long long& cmp, long long& swp) {
    while (true) {
        int l = 2 * p + 1, r = 2 * p + 2;
        if (l >= sz) return;                  // 没有孩子 → 已经是叶子，结束
        int bigger = l;                       // 先假设左孩子更大
        if (r < sz) {
            ++cmp;
            if (a[r] > a[l]) bigger = r;      // 两个孩子都在，挑大的
        }
        ++cmp;
        if (a[bigger] <= a[p]) return;        // 父结点不小于孩子 → 堆性质成立，结束
        swap(a[p], a[bigger]);
        ++swp;
        p = bigger;                           // 继续往下检查
    }
}

/* 建堆：从最后一个非叶结点 n/2-1 开始，倒序下沉。总时间 O(n) */
void buildHeap(vector<int>& a, long long& cmp, long long& swp) {
    int n = a.size();
    for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, i, n, cmp, swp);
}

/* 堆排序主流程：O(n) 建堆 + (n-1) 次「换顶 + 下沉」，每次 O(log n) */
void heapSort(vector<int>& a, long long& cmp, long long& swp) {
    int n = a.size();
    cmp = swp = 0;
    if (n < 2) return;
    buildHeap(a, cmp, swp);                    // 第一步：建大根堆
    for (int end = n - 1; end > 0; --end) {    // 第二步：反复取走堆顶
        swap(a[0], a[end]);                    // 最大值换到末尾，位置确定
        ++swp;
        siftDown(a, 0, end, cmp, swp);         // 堆规模缩到 end，新堆顶下沉
    }
}

/* 变体：小根堆版本（把比较符号反过来即可），用于降序或 Top-K */
void siftDownMin(vector<int>& a, int p, int sz) {
    while (true) {
        int l = 2 * p + 1, r = 2 * p + 2;
        if (l >= sz) return;
        int smaller = l;
        if (r < sz && a[r] < a[l]) smaller = r;
        if (a[smaller] >= a[p]) return;
        swap(a[p], a[smaller]);
        p = smaller;
    }
}

static void printArr(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); ++i) cout << (i ? ", " : "") << a[i];
    cout << "]";
}
static bool isMaxHeap(const vector<int>& a) {
    int n = a.size();
    for (int i = 0; 2 * i + 1 < n; ++i) {
        if (a[i] < a[2 * i + 1]) return false;
        if (2 * i + 2 < n && a[i] < a[2 * i + 2]) return false;
    }
    return true;
}

int main() {
    vector<int> raw = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0};
    long long cmp = 0, swp = 0;

    /* 单独看建堆的结果 */
    vector<int> h = raw;
    cmp = swp = 0;
    buildHeap(h, cmp, swp);
    cout << "建堆结果     : "; printArr(h);
    cout << "  是大根堆？" << (isMaxHeap(h) ? "是" : "否")
         << "　堆顶（最大值）= " << h[0] << "　建堆比较 " << cmp << " 次\n";

    vector<int> a = raw;
    heapSort(a, cmp, swp);
    cout << "堆排序结果   : "; printArr(a);
    cout << "  比较 " << cmp << " 次，交换 " << swp << " 次\n";

    /* 与「逐个上浮插入建堆」对比：后者是 O(n log n) */
    vector<int> up = raw;
    long long upCmp = 0;
    for (size_t i = 1; i < up.size(); ++i) {          // sift up 建堆
        int c = i;
        while (c > 0) {
            int par = (c - 1) / 2;
            ++upCmp;
            if (up[par] >= up[c]) break;
            swap(up[par], up[c]);
            c = par;
        }
    }
    cout << "上浮建堆结果 : "; printArr(up);
    cout << "  是大根堆？" << (isMaxHeap(up) ? "是" : "否") << "　比较 " << upCmp << " 次\n";

    /* 用堆的思路做降序：小根堆依次取出最小值 → 得到升序，再反转 */
    vector<int> d = raw;
    for (int i = (int)d.size() / 2 - 1; i >= 0; --i) siftDownMin(d, i, d.size());
    vector<int> desc;
    for (int end = (int)d.size() - 1; end >= 0; --end) {
        desc.push_back(d[0]);                      // 取出当前最小值
        swap(d[0], d[end]);
        siftDownMin(d, 0, end);
    }
    reverse(desc.begin(), desc.end());             // 反转 → 降序
    cout << "小根堆取降序 : "; printArr(desc); cout << "\n";
    return 0;
}

11.6.6 不稳定性：一个具体例子

堆排序不稳定，而且它的不稳定非常「隐蔽」——不是发生在下沉里，而是发生在「堆顶与末尾交换」那一步。

取序列 [2a, 2b, 1]（两个关键字为 2 的记录）。建堆时： 最后一个非叶结点是 ⌊3/2⌋ − 1 = 0，对下标 0 下沉。 它的两个孩子是 A[1] = 2b 与 A[2] = 1，较大的孩子是 A[1] = 2b； 比较 A[1] = 2b 与父结点 A[0] = 2a：2b > 2a 不成立（相等）， 所以不交换，堆已经是 [2a, 2b, 1]。

排序阶段：end = 2，把 A[0] 与 A[2] 交换 → [1, 2b, 2a]。看！2a 被一步换到了 2b 的后面，相对次序翻转。 虽然 [2a, 2b, 1] 这个例子最终排出来是 [1, 2b, 2a]， 两个 2 的次序确实颠倒了，这就是堆排序不稳定的直接证据。

11.6.7 优先队列：堆在 STL 里的样子

堆在工程中最常见的身份不是「排序算法」，而是优先队列（priority queue）。 优先队列要求「每次取出的都是当前优先级最高的元素」，而堆恰好能在 O(log n) 内完成插入与取极值， 在 O(1) 内读到极值。C++ 提供了两套现成工具：

• <queue> 里的 std::priority_queue<T>：默认是大根堆， 容器适配器，接口只有 push / pop / top / empty / size，遍历不了。
• <algorithm> 里的四个堆算法：make_heap / push_heap / pop_heap / sort_heap， 直接作用在 vector 上，可以随时访问底层数组。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
using namespace std;

/* ============================================================
   STL 里的堆：priority_queue 与 make_heap / push_heap / pop_heap / sort_heap
   记住一句话：STL 的堆全部是「大根堆」语义，要小根堆就自定义比较器
   ============================================================ */

struct Task {
    int priority;          // 优先级，越大越先做
    string name;
    /* 自定义比较器：返回 true 表示 lhs 的优先级「低于」rhs，即 rhs 先出队
       —— 注意这与 sort 的比较器方向相反，是新手最容易踩的坑 */
    bool operator<(const Task& o) const { return priority < o.priority; }
};

int main() {
    /* ---------- ① priority_queue：默认大根堆 ---------- */
    priority_queue<int> pq;
    for (int x : {5, 2, 9, 1, 7, 3}) pq.push(x);
    cout << "priority_queue 依次出队（大根堆）: ";
    while (!pq.empty()) { cout << pq.top() << ' '; pq.pop(); }
    cout << "\n";                              // 9 7 5 3 2 1

    /* 小根堆：用 greater<int> 或者把元素取负 */
    priority_queue<int, vector<int>, greater<int>> minpq;
    for (int x : {5, 2, 9, 1, 7, 3}) minpq.push(x);
    cout << "priority_queue 小根堆       : ";
    while (!minpq.empty()) { cout << minpq.top() << ' '; minpq.pop(); }
    cout << "\n";                              // 1 2 3 5 7 9

    /* 自定义类型 */
    priority_queue<Task> tq;
    tq.push({3, "写作业"}); tq.push({9, "交论文"}); tq.push({6, "打游戏"});
    cout << "任务按优先级出队            : ";
    while (!tq.empty()) { cout << tq.top().name << "(" << tq.top().priority << ") "; tq.pop(); }
    cout << "\n";                              // 交论文(9) 打游戏(6) 写作业(3)

    /* ---------- ② 四个堆算法：直接操作 vector ---------- */
    vector<int> v = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0};

    make_heap(v.begin(), v.end());               // O(n) 建堆
    cout << "make_heap 之后堆顶         : " << v.front() << "\n";   // 9

    v.push_back(100);                            // 先 push_back 进容器
    push_heap(v.begin(), v.end());               // 再 push_heap 调整，让它上浮到位
    cout << "push_heap(100) 之后堆顶    : " << v.front() << "\n";   // 100

    pop_heap(v.begin(), v.end());                // 把堆顶换到末尾，并对 [begin, end-1) 重新调整
    int top = v.back();                          // 堆顶还在容器里，只是被挪到了末尾
    v.pop_back();                                // 真正从容器里删掉
    cout << "pop_heap 取出的最大值      : " << top
         << "，新堆顶 " << v.front() << "\n";                     // 100，新堆顶 9

    make_heap(v.begin(), v.end());
    sort_heap(v.begin(), v.end());               // 反复 pop_heap，最终得到升序数组（堆结构被破坏）
    cout << "sort_heap 之后              : ";
    for (int x : v) cout << x << ' ';
    cout << "\n";                              // 0 1 2 3 4 5 6 7 8 9

    /* 注意：sort_heap 等价于把 make_heap + 反复 pop_heap 走完，
       它比 std::sort 慢（常数更大），实际排序请优先用 std::sort。 */
    return 0;
}

11.6.8 Top-K 问题：堆最漂亮的实战应用

问题：从 n 个数中找出最大的 k 个数（k ≪ n），要求时间尽量少、空间尽量小。

朴素思路：全部排序后取前 k 个，需要 O(n log n) 时间和 O(n) 空间—— 当 n 是 10 亿、k 只有 10 时，把 10 亿个数全排一遍纯属浪费。

堆的思路：维护一个大小为 k 的小根堆。遍历每个元素 x： 如果堆没满就放进去；如果 x > 堆顶（堆顶是这 k 个数里最小的）， 就弹出堆顶、把 x 放进去。遍历结束后，堆里剩下的就是最大的 k 个数。

• 时间复杂度：O(n log k)。每个元素最多触发一次 O(log k) 的调整， 而且平均只有很少的元素能进入堆（后面的元素越来越难超过堆顶）。
• 空间复杂度：O(k)。内存里永远只放 k 个数，10 亿个数流式读入也不怕。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;

/* ============================================================
   Top-K：从 n 个数里取最大的 k 个
   维护一个大小为 k 的小根堆，堆顶是当前候选集合里的最小值（门槛）
   时间 O(n log k)，空间 O(k)
   ============================================================ */
vector<int> topK(const vector<int>& nums, int k) {
    if (k <= 0) return {};
    priority_queue<int, vector<int>, greater<int>> heap;   // 小根堆
    for (int x : nums) {
        if ((int)heap.size() < k) {
            heap.push(x);                     // 堆还没满，先放进来
        } else if (x > heap.top()) {
            heap.pop();                       // 比门槛大 → 淘汰门槛
            heap.push(x);
        }
        /* 否则 x 连门槛都比不过，直接丢弃，一次 O(1) 判断就淘汰了 */
    }
    vector<int> res;
    while (!heap.empty()) { res.push_back(heap.top()); heap.pop(); }
    sort(res.rbegin(), res.rend());           // 从大到小输出
    return res;
}

/* 对照实现 1：全部排序后取前 k 个 —— O(n log n) */
vector<int> topKSort(vector<int> nums, int k) {
    sort(nums.begin(), nums.end(), greater<int>());
    if ((int)nums.size() > k) nums.resize(k);
    return nums;
}

/* 对照实现 2：快速选择（quickselect）—— 平均 O(n)，但会打乱原数组且最坏 O(n^2) */
int quickSelect(vector<int>& a, int l, int r, int k) {
    if (l == r) return a[l];
    int pivot = a[l + (r - l) / 2], i = l, j = r;
    while (i <= j) {
        while (a[i] > pivot) ++i;             // 这里找的是「第 k 大」，所以按降序划分
        while (a[j] < pivot) --j;
        if (i <= j) { swap(a[i], a[j]); ++i; --j; }
    }
    if (k <= j) return quickSelect(a, l, j, k);
    if (k >= i) return quickSelect(a, i, r, k);
    return a[k];
}

int main() {
    vector<int> nums;
    for (int i = 0; i < 100000; ++i) nums.push_back((i * 7919 + 13) % 100000);   // 伪随机

    int k = 5;
    vector<int> r1 = topK(nums, k);
    cout << "堆方法 Top-" << k << "     : ";
    for (int x : r1) cout << x << ' ';
    cout << "\n";

    vector<int> r2 = topKSort(nums, k);
    cout << "全排序 Top-" << k << "    : ";
    for (int x : r2) cout << x << ' ';
    cout << "\n";

    vector<int> tmp = nums;
    cout << "快速选择第 " << k << " 大 : " << quickSelect(tmp, 0, tmp.size() - 1, k - 1) << "\n";

    cout << "两种方法结果一致？" << (r1 == r2 ? "一致" : "不一致") << "\n";

    /* 流式场景：内存放不下全部数据时，堆方法是唯一可行的 */
    cout << "（堆方法只需 O(k) = " << k << " 个额外空间，可以边读边算）\n";
    return 0;
}

11.6.9 堆排序小结

11.7 归并排序：分治的教科书范例

11.7.1 分治三步骤与二路归并

归并排序（merge sort）由冯·诺依曼在 1945 年提出，是最标准的分治（divide and conquer）算法。 它的三步骤是：

1. 分解（Divide）：把当前区间 [l, r] 从中间切成 [l, mid] 与 [mid+1, r]。
2. 解决（Conquer）：递归地对左右两半排序。当区间只剩 1 个元素时，它天然有序，递归到底。
3. 合并（Merge）：把两个已经有序的子区间合并成一个有序区间。这是整个算法的灵魂。

归并排序之所以能做到 O(n log n)，关键在一个漂亮的平衡：分解的层数是 log n （每次对半切），而每一层的合并总代价是 O(n)（每一层加起来正好处理 n 个元素）。 乘起来就是 O(n log n)。而且这个结论与数据分布无关—— 不管输入是随机的还是有序的，切分方式都一样，所以最好、平均、最坏都是 O(n log n)。

二路归并的具体过程（双指针法）

合并两个有序段 A[l..mid] 与 A[mid+1..r] 的方法叫双指针取小： 用 i 指向左段头、j 指向右段头，比较 A[i] 与 A[j]， 谁小就把它抄进临时数组 T，然后对应的指针和 T 的写指针 k 一起后移。 某一侧先取完时，另一侧剩下的元素整段抄过去即可（因为它们本来就有序）。

举例：合并左段 [2, 5, 9] 与右段 [1, 3, 8]：

1. 2 vs 1 → 取 1，T = [1]，j 右移。
2. 2 vs 3 → 取 2，T = [1, 2]，i 右移。
3. 5 vs 3 → 取 3，T = [1, 2, 3]，j 右移。
4. 5 vs 8 → 取 5，T = [1, 2, 3, 5]，i 右移。
5. 9 vs 8 → 取 8，T = [1, 2, 3, 5, 8]，j 已用尽。
6. 右段取完，左段剩下的 [9] 整段抄过去 → T = [1, 2, 3, 5, 8, 9]。

11.7.2 交互动画：递归区间 + 双指针

下面的动画有三个看点：① 画布上方的一排短横线表示当前递归路径上每一层的区间 （颜色最深的那个就是正在处理的区间）；② 中间一行是原数组 A， 蓝色是左段、橙色是右段、变灰表示「该元素已经被取走」；③ 下面一行是临时数组 T，以及 i / j / k 三个指针。请特别注意每次「相等时取左段」的那一步—— 它是归并排序稳定性的全部秘密。

11.7.3 递归版与自底向上（非递归）版

递归版写法最贴近分治的定义，但每一次递归调用都有函数栈开销，而且当 n 很大时递归深度 log n 虽然不大，但常数开销依然存在。工程上（尤其库实现）更常用自底向上（bottom-up）的迭代版： 先两两合并长度为 1 的段，再合并长度为 2 的段，再合并长度为 4 的段…… 外层只有一个 for (len = 1; len < n; len *= 2) 循环，没有任何递归。

两版的时间空间复杂度完全一样，选择哪一个取决于：

• 需要稳定 + 可预测：选迭代版，没有栈溢出风险。
• 需要处理链表：递归版更自然（链表归并排序是链表排序的最优解，空间可以做到 O(log n)）。
• 需要做外排序：必须是迭代版，因为「下一层要读哪些块」需要精确控制。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   归并排序（递归版，升序）
   时间 O(n log n)（最好 = 平均 = 最坏），空间 O(n)，稳定
   ============================================================ */

/* 合并两个相邻有序段 A[l..mid] 与 A[mid+1..r]，借助临时数组 tmp */
void mergeRange(vector<int>& a, int l, int mid, int r, vector<int>& tmp, long long& cmp, long long& mv) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        ++cmp;
        if (a[i] <= a[j]) tmp[k++] = a[i++];   // <= ：相等时取左段 → 保证稳定
        else               tmp[k++] = a[j++];
        ++mv;
    }
    while (i <= mid) { tmp[k++] = a[i++]; ++mv; }   // 左段剩余，整段搬
    while (j <= r)   { tmp[k++] = a[j++]; ++mv; }   // 右段剩余，整段搬
    for (int t = l; t <= r; ++t) a[t] = tmp[t];     // 写回原数组
}

void msort(vector<int>& a, int l, int r, vector<int>& tmp, long long& cmp, long long& mv) {
    if (l >= r) return;                        // 递归边界：0 或 1 个元素天然有序
    int mid = l + (r - l) / 2;                 // 这样写可以避免 l+r 溢出
    msort(a, l, mid, tmp, cmp, mv);
    msort(a, mid + 1, r, tmp, cmp, mv);
    mergeRange(a, l, mid, r, tmp, cmp, mv);
}

void mergeSort(vector<int>& a, long long& cmp, long long& mv) {
    int n = a.size();
    cmp = mv = 0;
    if (n < 2) return;
    vector<int> tmp(n);                        // 临时数组只分配一次，反复复用
    msort(a, 0, n - 1, tmp, cmp, mv);
}

static void printArr(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); ++i) cout << (i ? ", " : "") << a[i];
    cout << "]";
}

int main() {
    vector<int> raw = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0};
    long long cmp = 0, mv = 0;

    vector<int> a = raw;
    mergeSort(a, cmp, mv);
    cout << "归并排序结果 : "; printArr(a);
    cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";

    /* 已经有序 / 完全逆序：比较次数都在 O(n log n) 量级，不会退化 */
    vector<int> sorted = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    a = sorted; mergeSort(a, cmp, mv);
    cout << "有序数据     : 比较 " << cmp << " 次，移动 " << mv << " 次\n";
    vector<int> rev = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    a = rev; mergeSort(a, cmp, mv);
    cout << "逆序数据     : 比较 " << cmp << " 次，移动 " << mv << " 次\n";

    /* 稳定性验证：用 (关键字, 编号) 观察相等关键字的相对次序 */
    vector<pair<int, char>> rec = {{5, 'a'}, {2, 'x'}, {5, 'b'}, {1, 'y'}, {5, 'c'}};
    int n = rec.size();
    vector<pair<int, char>> tmp(n);
    /* 手写一次自底向上归并，便于观察 */
    for (int len = 1; len < n; len *= 2) {
        for (int l = 0; l < n; l += 2 * len) {
            int mid = min(l + len, n) - 1, r = min(l + 2 * len, n) - 1;
            if (mid >= r) continue;
            int i = l, j = mid + 1, k = l;
            while (i <= mid && j <= r) tmp[k++] = (rec[i].first <= rec[j].first) ? rec[i++] : rec[j++];
            while (i <= mid) tmp[k++] = rec[i++];
            while (j <= r) tmp[k++] = rec[j++];
            for (int t = l; t <= r; ++t) rec[t] = tmp[t];
        }
    }
    cout << "稳定性验证   : ";
    for (auto& p : rec) cout << p.first << p.second << " ";   // 1y 2x 5a 5b 5c —— 5 的相对次序没变
    cout << "\n";
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   归并排序（自底向上 / 非递归版）
   外层只有一个 len = 1, 2, 4, 8, ... 的循环，没有任何递归调用
   优点：没有函数栈开销、没有栈溢出风险、便于改造成外排序
   ============================================================ */
void mergeSortIter(vector<int>& a, long long& cmp, long long& mv) {
    int n = a.size();
    cmp = mv = 0;
    if (n < 2) return;
    vector<int> tmp(n);

    for (int len = 1; len < n; len *= 2) {            // 当前有序段的长度
        for (int l = 0; l < n; l += 2 * len) {        // 每次合并相邻两段
            int mid = min(l + len, n) - 1;            // 左段 [l, mid]
            int r   = min(l + 2 * len, n) - 1;        // 右段 [mid+1, r]
            if (mid >= r) continue;                   // 右段不存在，本组无需合并
            int i = l, j = mid + 1, k = l;
            while (i <= mid && j <= r) {
                ++cmp;
                tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // 相等取左 → 稳定
                ++mv;
            }
            while (i <= mid) { tmp[k++] = a[i++]; ++mv; }
            while (j <= r)   { tmp[k++] = a[j++]; ++mv; }
            for (int t = l; t <= r; ++t) a[t] = tmp[t];
        }
    }
}

/* 实用增强：小区间改用插入排序，可以减少递归/循环开销
   （这也是 TimSort 的做法：短的 run 直接用插入排序补长） */
void insertionRange(vector<int>& a, int l, int r) {
    for (int i = l + 1; i <= r; ++i) {
        int key = a[i], j = i - 1;
        while (j >= l && a[j] > key) { a[j + 1] = a[j]; --j; }
        a[j + 1] = key;
    }
}
void mergeSortHybrid(vector<int>& a, long long& cmp, long long& mv, int threshold = 7) {
    int n = a.size();
    cmp = mv = 0;
    if (n < 2) return;
    vector<int> tmp(n);
    for (int l = 0; l < n; l += threshold) insertionRange(a, l, min(l + threshold, n) - 1);
    for (int len = threshold; len < n; len *= 2) {
        for (int l = 0; l < n; l += 2 * len) {
            int mid = min(l + len, n) - 1, r = min(l + 2 * len, n) - 1;
            if (mid >= r) continue;
            int i = l, j = mid + 1, k = l;
            while (i <= mid && j <= r) tmp[k++] = (a[i] <= a[j]) ? a[i++] : 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];
        }
    }
}

static void printArr(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); ++i) cout << (i ? ", " : "") << a[i];
    cout << "]";
}
static bool isSorted(const vector<int>& a) {
    for (size_t i = 1; i < a.size(); ++i) if (a[i - 1] > a[i]) return false;
    return true;
}

int main() {
    vector<int> raw = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0};
    long long cmp = 0, mv = 0;

    vector<int> a = raw;
    mergeSortIter(a, cmp, mv);
    cout << "迭代版归并   : "; printArr(a);
    cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";

    a = raw; mergeSortHybrid(a, cmp, mv);
    cout << "小区间插入版 : "; printArr(a);
    cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";

    /* 边界测试：n = 0..8 及 n = 1000 随机 */
    for (int n = 0; n <= 8; ++n) {
        vector<int> t(n);
        for (int i = 0; i < n; ++i) t[i] = (i * 5 + 3) % 7;
        mergeSortIter(t, cmp, mv);
        if (!isSorted(t)) { cout << "边界 n=" << n << " 失败\n"; return 1; }
    }
    vector<int> big(1000);
    for (int i = 0; i < 1000; ++i) big[i] = (i * 7919) % 1000;
    mergeSortIter(big, cmp, mv);
    cout << "n=1000 随机  : 有序性校验 " << (isSorted(big) ? "通过" : "失败") << "\n";
    return 0;
}

11.7.4 稳定性、空间代价与「为什么不用它排数组」

稳定性：归并排序是稳定的，因为合并时的判断写的是 a[i] <= a[j] 取左段。 这样一来，当左右两段出现相等的元素时，一定是原来在左边的那个先被放进结果数组， 相对次序得以保持。如果把等号去掉（写成 a[i] < a[j] 才取左边）， 相等时会优先取右段，归并排序立刻变成不稳定——这个改动和冒泡里的 > vs >= 是同一类陷阱。

空间：O(n)。合并必须借助一个和原数组等长的临时数组。这一点让归并排序失去了「原地」的资格， 也是它在内存排序中不如快排流行的主要原因。能不能省掉这个数组？

• 原地归并（in-place merge）确实存在，但要把两个有序段原地合并，平均需要 O(n) 次移动， 实现复杂（常用「三次反转」或「内部缓冲」技巧），会显著增大常数，得不偿失。
• 对链表做归并排序时不需要额外数组（改指针即可），空间可降到 O(log n)（递归栈）。 所以在「链表排序」这个特定问题上，归并排序是最优解，这也是 std::list::sort 采用它的原因。
• 工程折中：只开一个和原数组等长的缓冲区，在两个缓冲区之间来回倒，避免每层都新建数组。 本讲的实现就是把 tmp 一次性分配好、全程复用。

11.7.5 外排序：多路归并与败者树

当数据量大到内存装不下（比如 100 GB 的日志要排序，内存只有 4 GB），就必须用外部排序。 它的标准套路分两步：

1. 生成初始归并段（run）：把文件切成若干块，每块读进内存用内部排序（通常用快排或堆排）排好， 再写回磁盘。这样得到一个「内部有序、整体无序」的顺串集合。
2. 多路归并：把这些有序顺串合并成一个整体有序的大文件。每次从 k 个顺串中各读一块进内存， 用k 路归并选出最小的写到输出缓冲区，缓冲区满了就写回磁盘。

多路归并带来一个新问题：k 路归并时，每次选最小要比较 k−1 次， 如果 k 很大（比如 100 路），比较开销会很吓人。解决办法是败者树（loser tree）： 它是一棵完全二叉树，每个内部结点记录「刚刚比较中的败者」，胜者继续向上比。 这样选出全局最小值只需要 O(log k) 次比较，而且当某个顺串的当前元素被取走后， 只需沿着从叶子到根的路径重新比赛，也是 O(log k)。

11.7.6 重点应用：用归并排序求逆序对

逆序对（inversion）的定义：下标 i < j 但 A[i] > A[j] 的一对元素。 逆序对总数是「序列离有序有多远」的度量。例如 [5, 2, 9, 1] 的逆序对有 (5,2)、(5,1)、(2,1)、(9,1)，共 4 个。

暴力做法是双重循环枚举所有 (i, j)，O(n²)。n = 10⁵ 就超时了。 归并排序的做法漂亮得多，核心观察只有一句话：

为什么？因为左段已经有序，如果 A[i] > A[j]，那么 A[i+1], A[i+2], …, A[mid] 只会更大，当然也都大于 A[j]；同时它们在下标上都位于 j 之前，所以全都构成逆序对。 于是本来要一个个数的 (mid − i + 1) 个逆序对，被一次性统计完了。

这样做为什么不会重复计数？因为归并排序是按「归并段」分层的：每一对下标 (p, q) 会在唯一的一层被分开到左右两段，所以每对逆序对恰好被统计一次。 总复杂度与归并排序相同：O(n log n)。

动画里每一帧左上角的「累计逆序对」就是答案。注意观察：这个计数器只在「取右段元素」时增加， 而且一次增加 mid − i + 1 个。

#include <iostream>
#include <vector>
using namespace std;

/* ============================================================
   用归并排序统计逆序对
   逆序对：i < j 但 a[i] > a[j]
   核心：合并时若 a[i] > a[j]，则左段 [i, mid] 全部元素都与 a[j] 构成逆序对
   时间 O(n log n)，空间 O(n)
   ============================================================ */
long long mergeCount(vector<int>& a, int l, int mid, int r, vector<int>& tmp) {
    int i = l, j = mid + 1, k = l;
    long long cnt = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];                  // 左边不大于右边，不产生逆序对
        } else {
            cnt += (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];
    return cnt;
}

long long msortCount(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long long cnt = 0;
    cnt += msortCount(a, l, mid, tmp);
    cnt += msortCount(a, mid + 1, r, tmp);
    cnt += mergeCount(a, l, mid, r, tmp);
    return cnt;
}

long long countInversions(vector<int> a) {     // 传值：不破坏调用者的数组
    int n = a.size();
    if (n < 2) return 0;
    vector<int> tmp(n);
    return msortCount(a, 0, n - 1, tmp);
}

/* 对照：暴力 O(n^2) 统计，只用于小数据验证 */
long long countInversionsBrute(const vector<int>& a) {
    long long cnt = 0;
    for (size_t i = 0; i < a.size(); ++i)
        for (size_t j = i + 1; j < a.size(); ++j)
            if (a[i] > a[j]) ++cnt;
    return cnt;
}

int main() {
    vector<int> a = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0};
    cout << "归并统计逆序对 : " << countInversions(a) << "\n";        // 25
    cout << "暴力统计逆序对 : " << countInversionsBrute(a) << "\n"; // 25

    vector<int> sorted = {1, 2, 3, 4, 5};
    cout << "完全有序       : " << countInversions(sorted) << "\n";  // 0

    vector<int> rev = {5, 4, 3, 2, 1};
    cout << "完全逆序       : " << countInversions(rev) << "\n";     // 10 = 5*4/2

    /* 大规模随机数据：归并 O(n log n) vs 暴力 O(n^2)（暴力这里只跑 n=3000） */
    vector<int> big(200000);
    for (int i = 0; i < 200000; ++i) big[i] = (i * 7919 + 13) % 200000;
    cout << "n=200000 逆序对: " << countInversions(big) << "（归并版，毫秒级完成）\n";

    vector<int> small(3000);
    for (int i = 0; i < 3000; ++i) small[i] = (i * 7919 + 13) % 3000;
    cout << "n=3000 两法一致性: "
         << (countInversions(small) == countInversionsBrute(small) ? "一致" : "不一致") << "\n";

    /* 提示：逆序对数量可能达到 n(n-1)/2，n = 200000 时约 2×10^10，
       必须用 long long（int 会溢出）—— 这是本类题目最常见的 WA 原因。 */
    return 0;
}

11.8 快速排序：实测最快的比较排序

11.8.1 一句话本质与两种划分写法

快速排序（quick sort，Hoare 1960）和归并排序都是分治，但顺序刚好相反： 归并是「先切分、递归排好、最后合并」，快排是「先划分、让基准一步到位、再递归处理两边」。 快排不需要额外的合并步骤，所有工作都在原地完成，这是它比归并省空间的原因。

划分（partition）是快排的全部灵魂。它的目标只有一句话：

划分有两种主流写法，必须都能手写：

下面是挖坑法一趟划分的完整过程（以 A = [5, 2, 9, 1, 7, 3, 8, 4, 6, 0] 为例，基准取 A[0] = 5）：

11.8.2 交互动画：基准、双指针、递归区间

动画用 A = [5, 2, 9, 1, 7, 3, 8, 4, 6, 0, 11, 10]。屏幕上的紫色方块是当前基准， 蓝色 i 与橙色 j 是两个扫描指针，虚线框是待填的坑， 上方短横线是递归调用栈里各层的待排序区间。请特别留意每完成一次划分， 基准的位置就永久固定了 —— 画面上会有一格变成紫色「归位」状态。

11.8.3 基准选择的三种策略与各自的陷阱

快排的性能几乎完全由基准选得好不好决定。理想情况下基准应该接近中位数， 这样每次划分都能把区间砍成两半，递归深度 log n，总时间 O(n log n)。 如果基准每次都是极值，划分就变成「一边 0 个元素、一边 n−1 个元素」，递归深度退化成 n， 总时间变成 O(n²)。

11.8.4 为什么「有序数据 + 端点基准」会退化成 O(n²)

这是快排最经典的考点，必须能把推导写出来。设输入是已经升序的 A = [1, 2, 3, …, n]，基准取首元素 A[l]。

以挖坑法为例，看第 1 趟划分（l = 0, r = n−1，pivot = 1）：

• 右指针 j 从 n−1 开始往左扫。每个元素都 ≥ pivot = 1， 所以 j 一路畅通无阻地退到 j = 0，与 i 相遇。 这一步做了 n−1 次比较。
• 左指针的扫描一次都没执行（i 已经等于 j）。
• 把 pivot = 1 填回 A[0]。划分结果：左子区间为空，右子区间是 [1, n−1]，规模 n−1。

第 2 趟同理：对 [1, n−1] 划分，j 又要从右扫到底，做 n−2 次比较， 分出规模 n−2 的右子区间……依此类推。于是总比较次数为：

对应的递推式是：

这不只是「比较次数多」的问题，更严重的是递归深度变成了 n： 每层递归只减少一个元素，函数调用栈会压入 n 层，栈空间从 O(log n) 变成 O(n)。 当 n = 105 时，仅递归栈就可能吃掉几 MB， 在嵌入式或线程栈很小的环境里会直接栈溢出崩溃。所以「快排最坏 O(n²)」这句话里， 藏着的其实是两个坑：时间退化与空间退化。

11.8.5 递归深度与工程优化四件套

工业界的快排实现（std::sort 的 introsort、Java 的 DualPivotQuicksort）都做了四件事：

1. 小区间改用插入排序。当区间长度小于阈值（通常 8~16）时，递归的开销 （压栈、保护寄存器、函数调用）已经超过了排序本身。此时切到插入排序，实测能快 20%~30%。 std::sort 用的阈值是 16。
2. 三数取中选基准，避免有序数据退化。
3. 尾递归优化（消除尾递归）。快排有两个递归调用，把其中「较长的那一半」用循环处理、 只对「较短的一半」递归，可以把递归深度从 O(n) 压到 O(log n)。 这样即使遇到最坏情况，栈深度也只有 O(log n)，不会栈溢出—— 虽然时间复杂度仍是 O(n²)，但至少程序不会崩。完整可运行示例见下面的代码块。
4. 三路划分处理大量重复元素（见下一节），以及深度超限时切换到堆排序 （introsort 的「intro」就是 introspective，一旦递归深度超过 2 log n 就改用堆排序， 保证最坏也是 O(n log n)）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   快速排序的尾递归优化（消除尾递归）
   把两个递归调用中的「长的一半」改成循环，只递归「短的一半」
   效果：递归深度从最坏 O(n) 降到 O(log n)，杜绝栈溢出
   ============================================================ */

int partitionHole(vector<int>& a, int l, int r) {
    int pivot = a[l], i = l, j = r;            // 挖坑法
    while (i < j) {
        while (i < j && a[j] >= pivot) --j;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) ++i;
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    return i;
}

int maxDepthPlain = 0, maxDepthTail = 0;

/* 普通双递归版：最坏情况下递归深度 = n */
void quickSortPlainD(vector<int>& a, int l, int r, int d) {
    if (d > maxDepthPlain) maxDepthPlain = d;
    if (l >= r) return;
    int p = partitionHole(a, l, r);
    quickSortPlainD(a, l, p - 1, d + 1);
    quickSortPlainD(a, p + 1, r, d + 1);
}

/* 尾递归优化版：只对较短的一半递归，较长的一半用 while 循环吃掉 */
void quickSortTailD(vector<int>& a, int l, int r, int d) {
    if (d > maxDepthTail) maxDepthTail = d;
    while (l < r) {
        int p = partitionHole(a, l, r);
        if (p - l < r - p) {                   // 左半更短 → 递归左边，循环处理右边
            quickSortTailD(a, l, p - 1, d + 1);
            l = p + 1;
        } else {                               // 右半更短 → 递归右边，循环处理左边
            quickSortTailD(a, p + 1, r, d + 1);
            r = p - 1;
        }
    }
}

static bool isSorted(const vector<int>& a) {
    for (size_t i = 1; i < a.size(); ++i) if (a[i - 1] > a[i]) return false;
    return true;
}

int main() {
    /* 最坏情况：完全升序的数据 + 取首元素为基准 */
    const int N = 1000;
    vector<int> asc(N);
    for (int i = 0; i < N; ++i) asc[i] = i;

    vector<int> a = asc;
    quickSortPlainD(a, 0, N - 1, 1);
    cout << "普通双递归版：最大递归深度 = " << maxDepthPlain
         << "（n = " << N << "），有序性 " << (isSorted(a) ? "通过" : "失败") << "\n";

    a = asc;
    quickSortTailD(a, 0, N - 1, 1);
    cout << "尾递归优化版：最大递归深度 = " << maxDepthTail
         << "，有序性 " << (isSorted(a) ? "通过" : "失败") << "\n";

    cout << "\n结论：两者排序结果完全一样，但尾递归优化把栈空间从 O(n) 压到了 O(log n)。\n";
    cout << "这就是为什么工程实现里绝不允许快排出现 O(n) 的递归深度。\n";
    return 0;
}

11.8.6 三路划分：荷兰国旗问题

普通的两路划分有一个致命弱点：当序列中存在大量与基准相等的元素时，它会把相等的元素 一股脑分到同一侧，导致划分极不平衡。极端情况：[5, 5, 5, 5, 5, 5, 5]（全是同一个数）， 取首元素为基准做两路划分，会把所有元素都分到「≥ pivot」的那一边，递归深度变成 n， 复杂度退化成 O(n²)。

解决方法是三路划分（three-way partition），也就是著名的荷兰国旗问题 （因为荷兰国旗恰好是红白蓝三条，正好对应「小于、等于、大于」三段）。它把区间分成三部分：

划分完成后，中间那一段「等于 pivot」的元素整段都不用再递归了—— 它们的最终位置已经确定。于是全相同的序列只要一趟就排完，复杂度是 O(n)。 对于「大量重复关键字」的真实数据（比如按性别、按省份排序的成绩单），三路划分的提升是数量级的。

11.8.7 完整 C++ 实现（Hoare + 随机 + 三数取中 + 三路划分）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

/* ============================================================
   快速排序：四种划分 / 基准策略的完整实现与对照
   ============================================================ */

/* ---------- ① 挖坑法划分（返回基准的最终下标） ---------- */
int partitionHole(vector<int>& a, int l, int r, long long& cmp, long long& mv) {
    int pivot = a[l];                          // 挖坑：a[l] 变成空位
    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) { --j; ++cmp; }   // 从右往左找比 pivot 小的
        if (i < j) { a[i++] = a[j]; ++mv; }              // 填进左边的坑
        while (i < j && a[i] <= pivot) { ++i; ++cmp; }   // 从左往右找比 pivot 大的
        if (i < j) { a[j--] = a[i]; ++mv; }              // 填进右边的坑
    }
    a[i] = pivot;                              // 基准归位
    return i;
}

/* ---------- ② Hoare 版划分（原始论文写法） ---------- */
/* 注意：Hoare 版返回的 j 只是「左右分界」，不是基准的最终位置！
   因此递归区间必须写成 [l, j] 与 [j+1, r]，写成 [l, j-1] 会死循环 */
int partitionHoare(vector<int>& a, int l, int r, long long& cmp, long long& swp) {
    int pivot = a[l + (r - l) / 2];            // 取中间元素为基准，避免有序数据退化
    int i = l - 1, j = r + 1;
    while (true) {
        do { ++i; ++cmp; } while (a[i] < pivot);
        do { --j; ++cmp; } while (a[j] > pivot);
        if (i >= j) return j;
        swap(a[i], a[j]); ++swp;
    }
}

/* ---------- ③ 三数取中：把 l / mid / r 的中位数换到 a[l] ---------- */
void medianOfThreeToLeft(vector<int>& a, int l, int r) {
    int mid = l + (r - l) / 2;
    if (a[mid] < a[l]) swap(a[l], a[mid]);
    if (a[r]   < a[l]) swap(a[l], a[r]);
    if (a[r]   < a[mid]) swap(a[mid], a[r]);
    swap(a[l], a[mid]);                        // 现在 a[l] 是三者中的中位数
}

/* ---------- ④ 随机基准：随机选一个位置换到 a[l] ---------- */
void randomToLeft(vector<int>& a, int l, int r) {
    int k = l + rand() % (r - l + 1);
    swap(a[l], a[k]);
}

/* ---------- ⑤ 小区间插入排序 ---------- */
void insertionRange(vector<int>& a, int l, int r, long long& cmp, long long& mv) {
    for (int i = l + 1; i <= r; ++i) {
        int key = a[i], j = i - 1;
        while (j >= l) {
            ++cmp;
            if (a[j] <= key) break;
            a[j + 1] = a[j]; ++mv; --j;
        }
        a[j + 1] = key;
    }
}

const int INSERT_THRESHOLD = 16;               // 小区间阈值，与 std::sort 一致

/* 综合版快排：三数取中 + 小区间插入 + 短区间递归（控制栈深） */
void quickSort(vector<int>& a, int l, int r, long long& cmp, long long& mv) {
    while (l < r) {
        if (r - l + 1 <= INSERT_THRESHOLD) { insertionRange(a, l, r, cmp, mv); return; }
        medianOfThreeToLeft(a, l, r);          // 三数取中，避免有序退化
        int p = partitionHole(a, l, r, cmp, mv);
        /* 只对较短的一半递归，较长的一半用循环处理 → 栈深 O(log n) */
        if (p - l < r - p) { quickSort(a, l, p - 1, cmp, mv); l = p + 1; }
        else               { quickSort(a, p + 1, r, cmp, mv); r = p - 1; }
    }
}

/* 朴素版（首元素为基准，只用于演示退化，不要在生产代码里用） */
void quickSortNaive(vector<int>& a, int l, int r, long long& cmp, long long& mv) {
    if (l >= r) return;
    int p = partitionHole(a, l, r, cmp, mv);
    quickSortNaive(a, l, p - 1, cmp, mv);
    quickSortNaive(a, p + 1, r, cmp, mv);
}

/* Hoare 版快排（递归区间是 [l, j] 与 [j+1, r]） */
void quickSortHoare(vector<int>& a, int l, int r, long long& cmp, long long& swp) {
    if (l >= r) return;
    int j = partitionHoare(a, l, r, cmp, swp);
    quickSortHoare(a, l, j, cmp, swp);
    quickSortHoare(a, j + 1, r, cmp, swp);
}

static void printArr(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); ++i) cout << (i ? ", " : "") << a[i];
    cout << "]";
}
static bool isSorted(const vector<int>& a) {
    for (size_t i = 1; i < a.size(); ++i) if (a[i - 1] > a[i]) return false;
    return true;
}

int main() {
    vector<int> raw = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0, 11, 10};
    long long cmp = 0, mv = 0;

    vector<int> a = raw; quickSort(a, 0, a.size() - 1, cmp, mv);
    cout << "综合版快排   : "; printArr(a);
    cout << "  比较 " << cmp << " 次，移动 " << mv << " 次\n";

    a = raw; cmp = mv = 0; long long swp = 0;
    quickSortHoare(a, 0, a.size() - 1, cmp, swp);
    cout << "Hoare 版快排 : "; printArr(a);
    cout << "  比较 " << cmp << " 次，交换 " << swp << " 次\n";

    /* 有序数据 + 端点基准：退化的现场 */
    const int N = 2000;
    vector<int> asc(N);
    for (int i = 0; i < N; ++i) asc[i] = i;
    a = asc; cmp = mv = 0;
    quickSortNaive(a, 0, a.size() - 1, cmp, mv);
    cout << "\nn = " << N << " 升序 + 首元素基准（朴素版）：比较 " << cmp << " 次";
    cout << "（n(n-1)/2 = " << (long long)N * (N - 1) / 2 << "）\n";

    a = asc; cmp = mv = 0;
    quickSort(a, 0, a.size() - 1, cmp, mv);
    cout << "n = " << N << " 升序 + 三数取中（综合版）  ：比较 " << cmp << " 次，有序性校验 "
         << (isSorted(a) ? "通过" : "失败") << "\n";

    /* 大量重复元素：三路划分的主场（见下一个代码块） */
    cout << "\n提示：全部元素相同时，两路划分仍会退化成 O(n^2)，请看三路划分的实现。\n";
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   三路划分快速排序（荷兰国旗问题）
   把区间分成 < pivot、== pivot、> pivot 三段
   中间那一段整段跳过递归 —— 大量重复元素时的杀手锏
   ============================================================ */

/* 返回值通过引用传出：lt 是「等于区」的左端，gt 是「等于区」的右端
   划分后：a[l..lt-1] < pivot，a[lt..gt] == pivot，a[gt+1..r] > pivot */
void partition3Way(vector<int>& a, int l, int r, int& lt, int& gt, long long& cmp, long long& swp) {
    int pivot = a[l + (r - l) / 2];            // 取中间元素作基准，避免有序退化
    lt = l;                                    // lt 指向「小于区」的下一个空位
    gt = r;                                    // gt 指向「大于区」的前一个空位
    int i = l;
    while (i <= gt) {
        ++cmp;
        if (a[i] < pivot) {
            swap(a[lt], a[i]); ++swp;
            ++lt; ++i;
        } else if (a[i] > pivot) {
            swap(a[i], a[gt]); ++swp;
            --gt;                              // 注意：i 不前进！换过来的元素还没检查
        } else {
            ++i;                               // 等于 pivot，留在中间区
        }
    }
}

void quickSort3Way(vector<int>& a, int l, int r, long long& cmp, long long& swp) {
    while (l < r) {
        if (r - l + 1 <= 16) {                 // 小区间用插入排序收尾
            for (int i = l + 1; i <= r; ++i) {
                int key = a[i], j = i - 1;
                while (j >= l && a[j] > key) { a[j + 1] = a[j]; --j; }
                a[j + 1] = key;
            }
            return;
        }
        int lt, gt;
        partition3Way(a, l, r, lt, gt, cmp, swp);
        /* 中间段 [lt, gt] 已经就位，不参与递归 */
        if (lt - l < r - gt) { quickSort3Way(a, l, lt - 1, cmp, swp); l = gt + 1; }
        else                 { quickSort3Way(a, gt + 1, r, cmp, swp); r = lt - 1; }
    }
}

/* 对照：两路划分（挖坑法）在大量重复元素上的表现 */
void quickSort2Way(vector<int>& a, int l, int r, long long& cmp, long long& swp) {
    if (l >= r) return;
    int pivot = a[l], i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) { --j; ++cmp; }
        if (i < j) { a[i++] = a[j]; ++swp; }
        while (i < j && a[i] <= pivot) { ++i; ++cmp; }
        if (i < j) { a[j--] = a[i]; ++swp; }
    }
    a[i] = pivot;
    quickSort2Way(a, l, i - 1, cmp, swp);
    quickSort2Way(a, i + 1, r, cmp, swp);
}

static void printArr(const vector<int>& a, int limit = 30) {
    cout << "[";
    for (int i = 0; i < (int)a.size() && i < limit; ++i) cout << (i ? ", " : "") << a[i];
    if ((int)a.size() > limit) cout << ", ...";
    cout << "]";
}
static bool isSorted(const vector<int>& a) {
    for (size_t i = 1; i < a.size(); ++i) if (a[i - 1] > a[i]) return false;
    return true;
}

int main() {
    /* 全部元素相同：三路划分一趟搞定，两路划分退化成 O(n^2) */
    const int N = 4000;
    vector<int> same(N, 7);

    vector<int> a = same;
    long long cmp = 0, swp = 0;
    quickSort3Way(a, 0, a.size() - 1, cmp, swp);
    cout << "全相同(三路划分) : 比较 " << cmp << " 次，交换 " << swp
         << " 次，有序? " << (isSorted(a) ? "是" : "否") << "\n";

    a = same; cmp = swp = 0;
    quickSort2Way(a, 0, a.size() - 1, cmp, swp);
    cout << "全相同(两路划分) : 比较 " << cmp << " 次，交换 " << swp
         << " 次　← 明显退化\n";

    /* 只有三种取值的典型数据（比如按成绩等级排序） */
    vector<int> grade;
    for (int i = 0; i < 3000; ++i) grade.push_back((i * 7919) % 3);
    a = grade; cmp = swp = 0;
    quickSort3Way(a, 0, a.size() - 1, cmp, swp);
    cout << "三种取值(三路)   : 比较 " << cmp << " 次，有序? " << (isSorted(a) ? "是" : "否") << "\n";

    /* 普通随机数据 */
    vector<int> rnd(3000);
    for (int i = 0; i < 3000; ++i) rnd[i] = (i * 7919 + 13) % 3000;
    a = rnd; cmp = swp = 0; quickSort3Way(a, 0, a.size() - 1, cmp, swp);
    cout << "随机数据(三路)   : 比较 " << cmp << " 次，有序? " << (isSorted(a) ? "是" : "否") << "\n";

    vector<int> demo = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0, 11, 10};
    cmp = swp = 0; quickSort3Way(demo, 0, demo.size() - 1, cmp, swp);
    cout << "小样例结果       : "; printArr(demo); cout << "\n";
    return 0;
}

11.8.8 不稳定性，以及「为什么实测最快」

快排不稳定。原因还是那个老熟人——长距离交换。划分时 i 与 j 可能相隔很远，交换一次就会让一个元素跨过一大段，中间夹着的相等元素自然被跨过去了。

具体例子：[5a, 3, 5b, 1]，取首元素 5a 为基准做挖坑法划分。 j 从右往左找比 5 小的，停在下标 3（值 1），填进 A[0] → [1, 3, 5b, 1]；接着 i 从左往右找比 5 大的，走到 i = j = 3 相遇， 把基准填回去 → [1, 3, 5b, 5a]。5a 与 5b 的次序被颠倒了，不稳定。

那为什么快排实测还是最快？三个原因：

• 内层循环极简单。划分的核心就是两个 while 加一次比较，没有函数调用、 没有复杂的下标计算，现代 CPU 一个周期能执行好几条这样的指令。相比之下堆排序每次下沉都要算 2i+1、2i+2 并做两次比较，指令数是快排的好几倍。
• 顺序访问，缓存友好。划分时 i 从左往右、j 从右往左， 都是连续地址的顺序扫描，CPU 的硬件预取器能完美预测，缓存命中率极高。 堆排序则是在数组里「跳着走」（下标翻倍），几乎每次访问都跨越大段内存， 缓存未命中率极高——这是堆排序慢的根本原因。
• 常数因子小、平均比较次数少。快排的平均比较次数约为 1.39 n log₂n， 而归并排序是 n log₂n 次比较 + n log₂n 次数组写入（写内存比比较贵得多）。 归并的「写」开销抵消了它比较次数上的优势。

11.9 基数排序：不比较也能排序

11.9.1 LSD 与 MSD：从最低位还是最高位开始

基数排序（radix sort）是分配类排序的代表：它从不比较任何两个关键字的大小， 而是把关键字看成「若干位数字的组合」，按位把元素分配进桶里再收集回来，反复若干轮就排好了。 它是唯一能在 O(n) 量级（当位数 d 是常数时）完成排序的实用算法之一， 也就此绕开了 11.1.3 提到的 Ω(n log n) 比较下界。

按处理顺序，基数排序分两种：

• LSD（Least Significant Digit first，最低位优先）：从个位开始，依次处理十位、百位…… 每一轮都对整个序列做一次「分配 + 收集」。这是最常用的形式，代码简单，且天然适合处理定长整数。
• MSD（Most Significant Digit first，最高位优先）：从最高位开始，按最高位把序列分成若干组， 然后对每一组递归处理次高位。它更像「桶排序 + 递归」，可以提前终止（前面的位已经分开了就不用看后面的位）， 但实现复杂、需要递归、而且不稳定。

本讲统一用 LSD，因为它是考试与工程里的主流，而且它的正确性依赖于一个关键性质：稳定性（见 11.9.3）。

11.9.2 三轮完整手推（[170, 45, 75, 90, 802, 24, 2, 66]）

我们用 A = [170, 45, 75, 90, 802, 24, 2, 66] 完整推三轮（个位 → 十位 → 百位）：

第 1 轮：按个位分配

分配结果：bucket[0] = [170, 90]，bucket[2] = [802, 2]， bucket[4] = [24]，bucket[5] = [45, 75]，bucket[6] = [66]， 其余桶为空。
按 bucket[0] → bucket[9] 的顺序收集，得到： [170, 90, 802, 2, 24, 45, 75, 66]。此时序列已按个位有序。

第 2 轮：按十位分配

注意 802 与 2 的十位都是 0（不足的位按 0 处理）—— 它们在 bucket[0] 里的顺序是 [802, 2]， 正好保持了上一轮收集后的先后次序。这一点至关重要。
收集得到：[802, 2, 24, 45, 66, 170, 75, 90]。此时序列已按后两位有序。

第 3 轮：按百位分配

收集：bucket[0] = [2, 24, 45, 66, 75, 90]，bucket[1] = [170]， bucket[8] = [802]，得到 [2, 24, 45, 66, 75, 90, 170, 802]——排序完成！

11.9.3 交互动画：10 个桶的分配与收集

动画把 10 个桶竖着画出来，元素被「丢进」对应的桶里，再按桶号顺序接回结果序列。 请重点盯住两处：① 同一个桶里元素的上下顺序；② 每一轮结束后序列的变化规律 —— 第 1 轮后按个位有序，第 2 轮后按后两位有序，第 3 轮后整体有序。

11.9.4 为什么基数排序必须稳定

这是基数排序最核心、也最容易考的一个问题。答案是：因为每一位的处理都要依赖上一轮的结果， 而上一轮的结果正是靠「桶内保持原序」保留下来的。

用具体数字说明。假设第 1 轮按个位排完后有 [802, 2]（它们个位都是 2， 802 因为原来在前面所以排在前面）。第 2 轮按十位分配时，两者的十位都是 0， 会被放进同一个桶 bucket[0]。此时：

• 如果分配时保持原序（稳定），桶里是 [802, 2]，收集后 802 仍在 2 前面 —— 由于 802 的百位比 2 大，第 3 轮会把它们分开，最终得到 …, 2, …, 802，正确。
• 如果分配时打乱了原序（不稳定），桶里可能变成 [2, 802]， 那么第 3 轮按百位分配后仍然得到 2 在 802 前面 —— 结果碰巧还对。 但考虑 24 与 45：如果第 1 轮后它们的相对次序被打乱， 第 2 轮十位不同（2 与 4）还能分开，可第 3 轮百位都是 0 时又会被塞进同一个桶， 此时顺序错误就直接变成最终结果的错误。

更严格的表述是：基数排序的正确性建立在「按第 k 位排序时，前面 k−1 位已经有序」这个循环不变式上。 而「低位已经有序」这个信息完全存储在序列的排列顺序里——一旦某一轮破坏了相对次序， 低位的有序信息就永久丢失了，后续轮次无法再恢复。

11.9.5 复杂度、链式实现与完整代码

时间复杂度：设最大数有 d 位、基数为 r（十进制 r = 10）、元素个数为 n。 每一轮分配要扫一遍 n 个元素，收集要把 r 个桶走一遍，所以每轮 O(n + r)， d 轮合计：

当 d 是常数（比如 32 位整数最多 10 位十进制数）时，它就是 O(n)—— 比任何比较排序都快。但要注意两点：① 如果 d ≈ log n（比如把很大的数当字符串排）， 复杂度会变成 O(n log n)；② 只有当关键字的取值范围比较小、位数不多时，基数排序才划算， 否则桶的空间开销和清桶的时间会吃掉全部优势。

链式基数排序：如果元素很大（比如每条记录几百字节），每一轮都把它们在数组里搬来搬去太贵了。 工程做法是用链表：把每个桶实现成一条链，分配时只改指针（O(1)），收集时把 10 条链首尾相接。 这样一整轮下来一个元素都不用移动，只有指针在动。 这也是「链式基数排序」在教材里被单独讲一节的原因。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* ============================================================
   基数排序（LSD，最低位优先，十进制）
   每一轮：按当前位「分配」到 10 个桶，再按桶号顺序「收集」
   关键：收集必须稳定（先进先出），否则低位的信息会丢失
   时间 O(d(n+r))，空间 O(n+r)
   ============================================================ */

/* 取整数 x 的第 k 位（k = 0 表示个位） */
int digitAt(long long x, int k) {
    while (k-- > 0) x /= 10;
    return (int)(x % 10);
}

/* 基础版：用计数数组 + 前缀和定位，一趟分配收集 O(n + 10) */
void radixSortLSD(vector<int>& a, long long& moves) {
    int n = a.size();
    moves = 0;
    if (n < 2) return;

    int maxVal = *max_element(a.begin(), a.end());
    int d = 1;                                  // 最大数的位数
    while (maxVal >= 10) { maxVal /= 10; ++d; }

    vector<int> out(n);
    for (int k = 0; k < d; ++k) {               // 第 k 轮：按第 k 位排序
        int cnt[10] = {0};
        for (int i = 0; i < n; ++i) ++cnt[digitAt(a[i], k)];   // ① 统计每个桶的大小

        for (int b = 1; b < 10; ++b) cnt[b] += cnt[b - 1];     // ② 前缀和 → 每个桶的结束位置

        /* ③ 从后往前扫描，把元素放进对应的桶里。
              必须从后往前！这样同一个桶内先出现的元素后写入，
              写入位置从后往前排，最终桶内顺序 = 原顺序，即「稳定」。 */
        for (int i = n - 1; i >= 0; --i) {
            int b = digitAt(a[i], k);
            out[--cnt[b]] = a[i];
            ++moves;
        }
        for (int i = 0; i < n; ++i) a[i] = out[i];             // ④ 收集回原数组
    }
}

/* 支持负数的版本：把负数平移到非负区间再排 */
void radixSortWithNegative(vector<int>& a, long long& moves) {
    int n = a.size();
    moves = 0;
    if (n < 2) return;
    int mn = *min_element(a.begin(), a.end());
    if (mn < 0) for (int& x : a) x -= mn;        // 整体平移成非负
    radixSortLSD(a, moves);
    if (mn < 0) for (int& x : a) x += mn;        // 平移回去
}

/* 链式基数排序（用静态链表模拟，避免元素搬移） */
struct Node { int val; int next; };
void radixSortLinked(vector<int>& a, long long& moves) {
    int n = a.size();
    moves = 0;
    if (n < 2) return;
    int maxVal = *max_element(a.begin(), a.end());
    int d = 1;
    while (maxVal >= 10) { maxVal /= 10; ++d; }

    vector<Node> node(n);
    for (int i = 0; i < n; ++i) {
        node[i].val = a[i];
        node[i].next = (i + 1 < n) ? (i + 1) : -1;   // -1 表示链表结束
    }
    int head = 0;

    for (int k = 0; k < d; ++k) {
        int tail[10], bhead[10];
        for (int b = 0; b < 10; ++b) { tail[b] = -1; bhead[b] = -1; }
        /* 分配：把链表上的每个结点挂到对应桶的链尾，只改指针 */
        for (int p = head; p != -1; ) {
            int nxt = node[p].next;
            int b = digitAt(node[p].val, k);
            node[p].next = -1;
            if (bhead[b] == -1) { bhead[b] = tail[b] = p; }
            else { node[tail[b]].next = p; tail[b] = p; }
            ++moves;
            p = nxt;
        }
        /* 收集：把 10 条桶链首尾相接 */
        head = -1;
        int last = -1;
        for (int b = 0; b < 10; ++b) {
            if (bhead[b] == -1) continue;
            if (head == -1) head = bhead[b];
            else node[last].next = bhead[b];
            last = tail[b];
        }
    }
    /* 把链表写回数组 */
    int i = 0;
    for (int p = head; p != -1; p = node[p].next) a[i++] = node[p].val;
}

static void printArr(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); ++i) cout << (i ? ", " : "") << a[i];
    cout << "]";
}
static bool isSorted(const vector<int>& a) {
    for (size_t i = 1; i < a.size(); ++i) if (a[i - 1] > a[i]) return false;
    return true;
}

int main() {
    vector<int> raw = {170, 45, 75, 90, 802, 24, 2, 66};
    long long moves = 0;

    vector<int> a = raw;
    radixSortLSD(a, moves);
    cout << "LSD 基数排序        : "; printArr(a);
    cout << "  搬运元素 " << moves << " 次（d=3 轮 × 8 个）\n";

    a = raw; radixSortLinked(a, moves);
    cout << "链式基数排序        : "; printArr(a);
    cout << "  指针操作 " << moves << " 次（元素零搬移）\n";

    vector<int> neg = {170, -45, 75, -90, 802, 24, -2, 66};
    a = neg; radixSortWithNegative(a, moves);
    cout << "含负数版本          : "; printArr(a);
    cout << "  有序性校验 " << (isSorted(a) ? "通过" : "失败") << "\n";

    /* 大规模测试 */
    vector<int> big(100000);
    for (int i = 0; i < 100000; ++i) big[i] = (int)((i * 7919LL + 13) % 100000);
    a = big; radixSortLSD(a, moves);
    cout << "n=100000            : 有序性校验 " << (isSorted(a) ? "通过" : "失败")
         << "，搬运 " << moves << " 次\n";

    a = big; radixSortLinked(a, moves);
    cout << "n=100000（链式）    : 有序性校验 " << (isSorted(a) ? "通过" : "失败") << "\n";
    return 0;
}

11.9.6 与计数排序、桶排序的关系

这三种「分配类排序」是同一个家族的三兄弟，关系一定要理清：

一句话概括三者的关系：计数排序是「按值定位」，桶排序是「按区间分堆」，基数排序是「按位重复计数排序」。 计数排序可以看作「桶大小为 1、桶的个数等于值域」的桶排序； 基数排序则是把计数排序当成子过程，用 d 轮「低开销的计数排序」换取对更大值域的适应能力。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

/* ============================================================
   计数排序（counting sort）—— 基数排序每一轮的子过程
   不比较关键字，而是用「值 → 出现次数」的数组直接算出位置
   时间 O(n + k)，空间 O(n + k)，k 为值域大小
   ============================================================ */
void countingSort(vector<int>& a, int maxVal) {
    int n = a.size();
    if (n < 2) return;
    vector<int> cnt(maxVal + 1, 0), out(n);

    for (int i = 0; i < n; ++i) ++cnt[a[i]];              // ① 统计次数
    for (int v = 1; v <= maxVal; ++v) cnt[v] += cnt[v - 1];   // ② 前缀和 = 每个值的「结束位置」

    /* ③ 倒序扫描：保证稳定性。
          若正序扫描，相同值的元素会被倒着放进结果数组 → 不稳定。 */
    for (int i = n - 1; i >= 0; --i) out[--cnt[a[i]]] = a[i];

    for (int i = 0; i < n; ++i) a[i] = out[i];
}

/* 桶排序（bucket sort）：按值域分桶，桶内用插入排序
   适用前提：数据在值域上「均匀分布」 */
void bucketSort(vector<double>& a) {
    int n = a.size();
    if (n < 2) return;
    int B = n;                                            // 桶的个数
    vector<vector<double>> buckets(B);
    for (double x : a) {
        int idx = (int)(x * B);
        if (idx >= B) idx = B - 1;                        // 处理 x == 1.0 的边界
        buckets[idx].push_back(x);
    }
    for (int b = 0; b < B; ++b) {                         // 桶内插入排序
        for (size_t i = 1; i < buckets[b].size(); ++i) {
            double key = buckets[b][i];
            int j = (int)i - 1;
            while (j >= 0 && buckets[b][j] > key) { buckets[b][j + 1] = buckets[b][j]; --j; }
            buckets[b][j + 1] = key;
        }
    }
    int k = 0;
    for (int b = 0; b < B; ++b)
        for (double x : buckets[b]) a[k++] = x;
}

static void printArr(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); ++i) cout << (i ? ", " : "") << a[i];
    cout << "]";
}

int main() {
    /* 计数排序：值域必须小 */
    vector<int> a = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0, 5, 2};
    countingSort(a, 9);
    cout << "计数排序   : "; printArr(a); cout << "\n";

    /* 稳定性验证：相同关键字的相对次序必须保持不变 */
    vector<int> keys = {3, 1, 3, 2, 1};
    vector<char> tag  = {'a', 'b', 'c', 'd', 'e'};
    int n = keys.size();
    vector<int> cnt(4, 0), pos(4, 0);
    for (int i = 0; i < n; ++i) ++cnt[keys[i]];
    for (int v = 1; v < 4; ++v) cnt[v] += cnt[v - 1];
    vector<pair<int, char>> out(n);
    for (int i = n - 1; i >= 0; --i) out[--cnt[keys[i]]] = {keys[i], tag[i]};
    cout << "稳定性验证 : ";
    for (auto& p : out) cout << p.first << p.second << " ";   // 1b 1e 2d 3a 3c
    cout << "\n";

    /* 桶排序：均匀分布的浮点数 */
    vector<double> f = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
    bucketSort(f);
    cout << "桶排序     : ";
    for (double x : f) cout << x << ' ';
    cout << "\n";

    /* 为什么计数排序不能排大范围数据：值域 k = 10^8 时，
       cnt 数组就要 400 MB —— 空间直接爆掉。
       这时应当改用「排序 + 离散化」或者基数排序。 */
    cout << "注意：计数排序的空间是 O(n + k)，k 是值域而不是 n。\n";
    cout << "      k = 1e8 时仅计数数组就需要约 400 MB，必须慎用。\n";
    return 0;
}

11.10 八大排序算法综合对比

11.10.1 一张表看完全部

下表是本讲的核心速查表，建议背下来。表中 n 为元素个数，k 为值域大小， d 为最大位数，r 为基数。所有「稳定」栏的判断依据都是 11.1.2 的定义。

① 只有带 swapped 标志的优化版冒泡才是最好 O(n)，原始版恒为 O(n²)。 ② 希尔排序的最坏复杂度取决于增量序列：折半增量是 O(n²)，Hibbard 是 O(n^1.5)， Sedgewick 约 O(n^4/3)。 ③ 快排可以通过「三数取中 + 随机化 + 深度超限切堆排序」（introsort）把最坏情况压到 O(n log n)。

11.10.2 怎么选：决策流程图

考试里常问「给定场景该用哪种排序」，工程里更是天天要选。下面这张流程图按 「规模 → 关键字特征 → 稳定性 → 内存 → 是否需要 Top-K」的顺序逐层过滤， 从最上面的入口一路往下走即可。

11.11 工程视角：排序是程序里跑得最多的代码

前面十节把八种排序的原理讲完了，但看真实的生产系统会发现：写业务代码的人 几乎从来不自己实现排序，只会写一行 sort()，而这一行背后各语言标准库给出的答案 完全不一样。这一节换一副眼镜，不再问「算法怎么写的」，而是问四个工程问题—— 生产系统调用的是哪个算法？为什么必须选它？代价是什么？什么时候会翻车？ 每个落点都按「用什么算法 → 为什么必须用它 → 代价 / 陷阱」三段来写。

11.11.1 生产级标准库排序：为什么同一个语言对两类数据用两种算法

先看一张「标准库实现对照表」——它回答的是：你敲的那一行 sort() 底下跑的是什么。

最值得琢磨的是 Java 那一栏：同一个 Arrays.sort，对 int[] 用双轴快排， 对 String[] 却用 Timsort。这不是历史包袱，而是一条被反复验证的设计原则—— 「基本类型排序只要快，对象排序还必须稳」。三层理由：

• 基本类型没有「身份」。两个 5 完全无法区分，交换它们不丢失任何信息， 稳定性对基本类型毫无意义，那就选最快的（双轴快排的划分更均匀，实测少 10% 左右比较）。
• 对象有业务含义。两个 Student 分数都是 90，但一个是张三、一个是李四。 用户传进来的 Comparator 可能只比分数，「分数相同的人保持原有次序」就是用户 已经依赖上的行为。不稳定排序会让这个依赖偶发失效——最难查。
• Java 的选择器是类型，不是标志位。int[] 与 Integer[] 是两种方法重载， 语言能在编译期挑出正确的那套算法，不必让用户写 Arrays.sort(a, STABLE)—— 把「用哪个算法」的决策权收进标准库，是工业级 API 的通用原则。

代价同样实在：要维护多套算法与阈值常数，还要为「缓冲区分配失败」写退化路径 （std::stable_sort 拿不到临时内存就退到原地归并，常数立刻变差）； 而这些阈值（16、32、47、286）不是推导出来的，是在真实机器上反复实测标定的， 换硬件可能要重调。标准库替你做了正确的选择，但正确是有维护成本的。

11.11.2 插入排序的真实地位：O(n²) 算法活在 O(n log n) 算法内部

很多同学学完 11.4 就认定「插入排序是 O(n²)，属于被淘汰的算法」。事实恰好相反： 你在生产环境每一次调用排序，都极可能真的跑到了插入排序——所有工业快排都在小区间切到它： C++ 的 std::sort 阈值是 16（_S_threshold）；Java 双轴快排是 INSERTION_SORT_THRESHOLD = 47、Timsort 的 MIN_MERGE = 32； Python / JavaScript 同理。为什么偏偏是这类收尾活？四条理由：

1. 常数小。内层只有「比较 + 搬一格」，不用选基准、不用划分、不用交换。 n = 16 时最坏也就 120 次移动，而快排还要为这 16 个元素再递归 4 层。
2. 没有函数调用开销。再往下还有约 log₂16 = 4 层调用栈，每次都要压栈、存寄存器、返回。 n 小的时候，调用开销比比较本身还贵。
3. 缓存友好。它只顺着数组前后移动；快排划分是两个指针从两端来回跳。
4. 此时的数据往往「基本有序」。快排划分到小区间时，元素已经历若干轮划分， 天然带局部有序性；而插入排序在基本有序时接近 O(n)，这是白送的加速。

这条结论的价值不在「记住 16」这个数字，而在它背后的思维方式： 复杂度描述的是 n → ∞ 时的增长形态，常数描述的是 n 很小时的真实耗时。 工程实现必须同时优化这两者，所以才会出现「把最坏 O(n²) 的算法嵌进最坏 O(n log n) 的算法里」 这种在纯理论视角下看起来很荒谬、在工程视角下却完全合理的结构。

11.11.3 快排的工程风险：最坏 O(n²) 与算法复杂度攻击

快排是平均最快的比较排序，也是唯一一个「输入本身能决定它性能」的常用排序。 11.8.4 已经推导过：朴素取首元素为基准时，一个已经升序的数组就是它的最坏输入。 现在把这件事放到生产环境里看，性质完全变了。

11.11.8 那段代码在本机（g++ 15.2.0，-O2，n = 200 000）的数据里最刺眼的一格是： 已升序输入下朴素快排要 4 424 429 μs（4.4 秒），混合快排只要 1 056 μs。

两点必须读懂：① 有序输入是日常数据而非稀有品——按主键扫出来的结果、按时间写入的日志、 上一步刚排好的数组本来就基本有序，最坏输入不需要对手构造，日常就能撞上； ② 递归深度 199 999 层意味着 n = 200 000 时栈要吃掉几十 MB，本机栈大勉强没崩， 换到线程栈只有几百 KB 的环境就是直接段错误。另外，大量重复元素是独立的另一种退化， 只有三路划分能治：全相同序列直接降到 O(n)。

11.11.4 稳定性为什么重要：多键排序必须靠它

稳定性的全部价值集中在一件事上：多键排序（multi-key sort）。场景：商品表要按 「先按价格升序，价格相同的按销量降序」展示，而原始数据本来就是按销量降序排好的。 工程上最自然的做法不是写双关键字比较器，而是分两次排：先按销量降序，再按 价格升序且必须用稳定排序。

为什么这样就对？稳定排序保证「价格相同的元素保持第二趟排序前的相对次序」，而那正是按销量降序的次序 ——于是价格相同的商品自然按销量降序排列。一个单键排序器 + 稳定性，等价于一个多键排序器； 换成不稳定排序，前一趟的销量次序当场作废。这条原理到处都是：

• 数据库的 ORDER BY a, b：优化器可能选择「先用 b 排一遍、 再用稳定排序按 a 排一遍」的执行计划，前提就是排序算子稳定。反过来，写 ORDER BY a 却期望「a 相同的行按插入顺序出来」，就是在 依赖标准没有承诺的稳定性——想稳就写成 ORDER BY a, id。
• Excel / 表格软件的多列排序：用户先点「主要关键字 = 价格」再点「次要关键字 = 销量」， 软件内部就是「从次要关键字往主要关键字倒着排」，每一步都必须是稳定排序。 早期表格软件换成不稳定实现后，用户报的「排序结果乱跳」就是这个 bug。
• 日志按时间戳排序还要保持原相对次序：多分片日志合并时同一毫秒内常有几十条记录， 运维依赖「同一毫秒内的顺序 = 物理写入顺序」，所以必须稳定。
• 竞赛里的「离散化 + 双关键字」：两个关键字相同的元素常需保持读入顺序， 用 std::sort（不稳定）在个别数据上就会错。正确写法是把下标作为第二关键字一起比—— 这正是「把不稳定排序改造成稳定的」最常用的手法。

11.11.5 外部排序：数据比内存大时怎么绕过去

前面所有排序都有一个隐含前提：数据全都在内存里。可生产环境天天遇到反例——100 GB 日志要排序 而机器只有 4 GB 内存。11.7.5 讲了机制，这里把它当真实的工程问题算到底： 100 GB 数据 + 4 GB 内存，到底怎么排、要读几遍磁盘？

先看瓶颈在哪：100 GB 做内部排序，CPU 约 n log₂n ≈ 100G × 27 次比较，按每秒 10⁸ 次估算 是几分钟量级；而读写 100 GB 按 SATA SSD 500 MB/s 算是 200 秒一轮。所以这里 CPU 不是瓶颈、磁盘 I/O 才是，目标就一条：让数据过磁盘的次数尽量少。

标准套路分两步，下图是它的完整形态（含每个数字的来历）：

三个结论：

• 趟数公式 S = ⌈log_k m⌉（m 为初始归并段数、k 为归并路数）：每趟要把全部数据 读写一遍，所以总 I/O = 2n × S。k 站在对数的底数上，把 k 从 2 提到 8，趟数就从 ⌈log₂29⌉ = 5 掉到 ⌈log₈29⌉ = 2， 代价只是多几个输入缓冲区——这是外部排序里性价比最高的一步优化。
• 内存几乎决定了 m。缓冲区越大 → 块越少 → m 越小 → 趟数越少。所以工程上常把内存的 80% 以上都拿来做缓冲，这与内存排序「省空间是美德」的直觉正好相反：这里浪费内存才是正确策略。
• 置换选择（replacement selection）是笔可观的保险。小根堆边输出边补新记录，平均能生成约 2m 长的初始归并段（段数从 29 降到 15）。本例里两者都只需 2 趟、同为 600 GB， 但段数减半意味着离「多出一趟」的临界点更远——数据再多一点、内存再小一点， 它就省下整整一趟（200 GB、200 秒）；代价是内部排序从「快排一批」变成「维护一个堆」（见第 12 讲）。

它的生产落点，这几处你每天都在用：

• 数据库的 ORDER BY 落盘排序。MySQL 的 filesort、PostgreSQL 的 external merge sort 都是这套机制：结果集小就在内存里快排，超过 sort_buffer_size / work_mem 就切到「分块排序 → 多路归并」并写临时文件。 这是「排序相关慢查询」最常见的成因——参数给小了，一次查询就从毫秒变几十秒。
• MapReduce / Spark 的 shuffle。map 端在内存里排好、溢写磁盘（spill），reduce 端做 k 路归并 ——这就是「shuffle and sort」名字里带 sort 的原因。Hadoop 能排 TB 级数据靠的不是神奇算法， 就是把这一节的 I/O 账算清楚、把 k 调对。
• 日志分析。上百 GB 日志按时间戳排序去重， sort -S 2G -T /data/tmp big.log | uniq -c 背后就是外部排序 （-S 是内存缓冲大小，-T 是临时目录）。它还提供 -s 专门用来 关掉默认的最后一道稳定化比较——「稳定」在命令行工具里就已经是用户要操心的开关。
• 磁盘空间的隐性成本。100 GB 输入至少要再占 100 GB 临时空间（归并段 + 输出文件）。 「排序把磁盘写满」是真实事故，部署清单里永远有一条：预留与输入等量的临时空间。

11.11.6 堆排序的真实用途不是排序，而是优先队列

11.6 讲了整节的堆排序，但真实系统里没人用堆排序来排序——它常数比快排大，实测总慢一截。 那堆在工程里干什么？它几乎只以「优先队列」的身份出现。

这里有个值得一提的反例：很多人以为「操作系统任务调度一定用优先队列」， 其实 Linux 的 CFS 调度器用的是红黑树（vruntime 最小的进程在最左边），不是堆。 因为调度器不只需要「取最小」，还要快速删除任意进程、修改任意进程的键（睡眠、唤醒、优先级变化）： 红黑树是完整的动态有序集，支持 O(log n) 查找/删除/修改；而堆只擅长「反复取最值」， 想删中间某个元素得先 O(n) 找到它。堆不是万能优先队列，它只是「取最值」这件事的最省实现。

所以堆的工程定位是一句话：当「只需反复取最值」「内存紧张」「元素以流的方式到达」同时成立时， 堆是唯一正确的选择——一个普通数组就实现了 O(log n) 的动态最值。但需求里一旦出现「按任意键查找」 「删除任意元素」「范围查询」，就该换红黑树 / B+ 树了。

11.11.7 非比较排序的工程边界：什么时候能用，什么时候不能碰

计数、基数、桶排序是工程里一把锋利但很窄的刀：不比较关键字，而是利用键的数值结构 把元素直接「放」到位置上，换来惊人的速度，也换来一个硬边界。

• 计数排序：值域必须小且已知。复杂度 O(n + k)。真实用途：按年龄（0~150）、 按百分制分数（0~100）、按 HTTP 状态码（100~599）做直方图。k 一旦失控（比如按用户 ID 排 1 亿条），O(k) 的计数数组直接爆内存——瓶颈从时间变成空间。
• 基数排序：键必须能拆成定长的「位」。复杂度 O(d(n + r))。天生适合手机号 （11 位定长数字）、IPv4（4 字节，4 轮 256 进制）、身份证号、时间戳等定长整数键。
• 桶排序：键必须能均匀映射到桶。分布一偏斜（90% 数据挤进一个桶）桶内就退化成 O(n²)—— 它把「排序问题」换成了「分布假设问题」，而真实分布往往不满足假设。

然后是那条不能碰的边界：它们不能用于任意可比较对象。自定义的 Student、一段文本、 一个「按业务规则比较」的结构体，都没有「第几位」的概念，也没有可枚举的值域，基数/计数排序 无从下手（不是「慢」，是根本无法执行）。所以规则很干脆：比较排序是通用解， 非比较排序是专用解，只有三条同时满足才有资格用它——① 键是整数或可无损映射成整数； ② 值域小（计数）或定长（基数）；③ 映射开销 ≪ 排序省下的开销。

11.11.8 一段可跑的代码：混合排序、阈值与有序输入打回原形

这段程序把前面的结论验证一遍：① 一个「区间 ≤ 16 就切插入排序」的混合快排；② 一个 「取首元素为基准」的朴素快排当对照；③ 三路划分版本外加 std::sort；④ 用 chrono 计时，在随机 / 已升序 / 大量重复 / 近乎有序四种输入上打印对照表。编译运行： g++ -std=c++17 -O2 sort_hybrid.cpp && ./sort_hybrid。

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
#include <string>
using namespace std;

/* ============================================================
   工业界排序的真实拼法：混合快排 = 快排 + 小区间切插入排序
   四种实现同台对比：
     朴素快排   取首元素为基准，小区间也不切插排
     混合快排   三数取中 + 区间 <= 16 切插入排序（libstdc++ 的做法）
     三路快排   专治「大量重复元素」，= pivot 的整段一次排定
     std::sort  introsort：快排 + 堆排 + 插入排序
   四种输入特征：随机 / 已升序 / 大量重复 / 近乎有序
   ============================================================ */

const int THRESHOLD = 16;          /* libstdc++ 的 introsort 用的就是这个阈值 */

/* ---------- 插入排序：小区的王者，O(n²) 却活在 O(n log n) 内部 ---------- */
void insertionSort(vector<int> &a, int l, int r) {
    for (int i = l + 1; i <= r; ++i) {
        int key = a[i], j = i - 1;
        while (j >= l && a[j] > key) { a[j + 1] = a[j]; --j; }   /* 严格大于 => 稳定 */
        a[j + 1] = key;
    }
}

/* ---------- 三数取中：解决「数据本来就有序」这种真实存在的退化 ---------- */
int medianOfThree(vector<int> &a, int l, int r) {
    int m = l + (r - l) / 2;
    if (a[l] > a[m]) swap(a[l], a[m]);
    if (a[l] > a[r]) swap(a[l], a[r]);
    if (a[m] > a[r]) swap(a[m], a[r]);
    swap(a[m], a[r]);                   /* 中位数藏到区间末尾当哨兵 */
    return a[r];
}

/* ---------- Hoare 划分（基准已就位在 r） ---------- */
int partitionHoare(vector<int> &a, int l, int r) {
    int pivot = medianOfThree(a, l, r);
    int i = l - 1, j = r;
    while (true) {
        while (a[++i] < pivot) {}
        while (a[--j] > pivot) { if (j == l) break; }
        if (i >= j) break;
        swap(a[i], a[j]);
    }
    swap(a[i], a[r]);
    return i;
}

/* ---------- 混合快排：区间 <= THRESHOLD 直接甩给插入排序 ---------- */
void hybridSort(vector<int> &a, int l, int r) {
    if (r - l + 1 <= THRESHOLD) { insertionSort(a, l, r); return; }
    int p = partitionHoare(a, l, r);
    hybridSort(a, l, p - 1);
    hybridSort(a, p + 1, r);
}

/* ---------- 朴素快排：首元素当基准。递归深度用全局变量记下来 ---------- */
long long g_naiveDepth = 0;

void naiveSort(vector<int> &a, int l, int r, long long depth) {
    if (l >= r) return;
    if (depth > g_naiveDepth) g_naiveDepth = depth;
    int pivot = a[l];                   /* 首元素当基准 —— 有序数据下这里是灾难 */
    int i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) --j;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) ++i;
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    naiveSort(a, l, i - 1, depth + 1);
    naiveSort(a, i + 1, r, depth + 1);
}

/* ---------- 三路划分：< p / == p / > p 三段，相等段不参与递归 ---------- */
void quick3Way(vector<int> &a, int l, int r) {
    if (l >= r) return;
    int pivot = a[l + (r - l) / 2];
    int lt = l, i = l, gt = r;
    while (i <= gt) {
        if (a[i] < pivot) swap(a[lt++], a[i++]);
        else if (a[i] > pivot) swap(a[i], a[gt--]);
        else ++i;
    }
    quick3Way(a, l, lt - 1);
    quick3Way(a, gt + 1, r);
}

/* ---------- 计时外壳：同一份数据分别喂给四种实现 ---------- */
bool g_sortedOk;                        /* 结果正确性，防止「快但排错」 */

long long timeIt(vector<int> a, int which, long long &depth) {
    auto b = chrono::steady_clock::now();
    if (which == 0) {
        g_naiveDepth = 0;
        naiveSort(a, 0, (int)a.size() - 1, 1);
        depth = g_naiveDepth;
    } else if (which == 1) hybridSort(a, 0, (int)a.size() - 1);
    else if (which == 2) quick3Way(a, 0, (int)a.size() - 1);
    else sort(a.begin(), a.end());
    auto e = chrono::steady_clock::now();
    for (size_t i = 1; i < a.size(); ++i)
        if (a[i - 1] > a[i]) { g_sortedOk = false; break; }
    return chrono::duration_cast<chrono::microseconds>(e - b).count();
}

void report(const string &name, const vector<int> &data) {
    long long t0, t1, t2, t3, d0 = 0, dummy = 0;
    g_sortedOk = true;
    t0 = timeIt(data, 0, d0);
    t1 = timeIt(data, 1, dummy);
    t2 = timeIt(data, 2, dummy);
    t3 = timeIt(data, 3, dummy);
    printf("%-12s %-12lld %-12lld %-12lld %-12lld %-10lld %s\n",
           name.c_str(), t0, t1, t2, t3, d0, g_sortedOk ? "ok" : "FAIL");
}

int main() {
    const int N = 200000;
    mt19937 rng(20250916);

    vector<int> rnd(N);
    for (int i = 0; i < N; ++i) rnd[i] = (int)(rng() % 1000000u);

    vector<int> sortedArr = rnd;
    sort(sortedArr.begin(), sortedArr.end());

    vector<int> dup(N);
    for (int i = 0; i < N; ++i) dup[i] = (int)(rng() % 10u);      /* 值域只有 10 个 */

    vector<int> nearly = sortedArr;                              /* 近乎有序：只动 10% */
    for (int i = 0; i < N / 10; ++i) {
        int x = (int)(rng() % N), y = (int)(rng() % N);
        swap(nearly[x], nearly[y]);
    }

    printf("n = %d，THRESHOLD = %d，单位 us\n", N, THRESHOLD);
    printf("----------------------------------------------------------------------------\n");
    printf("%-12s %-12s %-12s %-12s %-12s %-10s %s\n",
           "输入特征", "朴素快排", "混合快排", "三路快排", "std::sort", "朴素递归深度", "正确性");
    printf("----------------------------------------------------------------------------\n");
    report("随机", rnd);
    report("已升序", sortedArr);
    report("大量重复", dup);
    report("近乎有序", nearly);
    printf("----------------------------------------------------------------------------\n");
    return 0;
}

本机实测输出（Intel Core Ultra 9 275HX / Windows / g++ 15.2.0 / -O2，n = 200 000）：

n = 200000，THRESHOLD = 16，单位 us
----------------------------------------------------------------------------
输入特征 朴素快排 混合快排 三路快排 std::sort    朴素递归深度 正确性
----------------------------------------------------------------------------
随机       10589        9708         12940        9784         39         ok
已升序    4424429      1056         2628         964          199999     ok
大量重复 355876       3147         2033         2839         26124      ok
近乎有序 5151         3535         6608         3402         204        ok
----------------------------------------------------------------------------

逐行读一遍，前面的结论就都落地了：

• 「已升序」这一行最重要。同一个朴素快排，随机数据只要 10 589 μs，有序数据要 4 424 429 μs——慢了 4 190 倍，而混合快排只要 1 056 μs。原因就是 11.8.4 的 T(n) = T(n−1) + (n−1) → n(n−1)/2。更直观的证据在最后一列：朴素快排递归深度 199 999 层（随机数据只有 39 层）——这个深度差就是「栈溢出」风险的真身。
• 「大量重复」专治「快排加了随机化还是慢」。值域只有 10 个的数组，朴素快排 355 876 μs， 三路快排只要 2 033 μs（快约 175 倍）。混合快排这里是 3 147 μs——它没有三路划分， 靠的只是「小区间切插排」这把钝器，可见两种优化不能互相替代。
• 「随机」这一行反而没有戏剧性。四种实现都在 10 ms 上下，std::sort 还略快于手写版 （libstdc++ 另外做了「深度超限切堆排」「带哨兵插排」等细节）。这是好消息：你手写的方向是对的。
• 「近乎有序」说明了阈值的价值来源。只有 10% 元素被打乱时，混合快排 3 535 μs 对朴素快排 5 151 μs；拉开差距的不是快排部分，而是最后几层「插入排序在近乎有序时接近 O(n)」的红利。
• 别忘了最后一列的正确性检查。「跑得快」和「排对了」是两件事——性能对比代码 必须自带校验，否则你测的可能是「一个飞快但排错的算法」。

11.11.9 工程选型对比表：六个算法的五个现实维度

11.10.1 那张表比的是复杂度，用来初筛；下面这张比的是现实维度—— 「在我这台机器、这个数据、这个业务约束下该调哪个」。两张表对照着看： 复杂度告诉你「能不能用」，现实维度告诉你「该不该用」。

读表有个诀窍：把「能否用于外部排序」这一列当分水岭。装得下内存时胜负在「常数与缓存」上，快排赢； 装不下时胜负在「顺序 I/O 还是随机 I/O」上，归并赢——这一列一变，前面所有维度的排名全部作废。 所以选型第一步永远是问清数据规模：规模决定瓶颈，瓶颈决定算法。

11.11.10 本节小结：把工程问题变成三个提问

这一节不讲新算法，讲的是一副眼镜。把它压缩成三个可以随手用的提问：

1. 「数据有多大？装得下内存吗？」装得下 → 比常数与缓存，选快排系（std::sort）； 装不下 → 比顺序 I/O 与趟数，选归并系（外部排序），并把 k 与缓冲区尽量做大。
2. 「结果需要稳定吗？」需要（多键排序、要保持原相对次序）→ 用明确承诺稳定的接口， 或把次序显式写进比较器；不需要 → 用最快的，稳定性对基本类型毫无意义。
3. 「输入是谁给的？最坏情况会不会被触发？」输入可信、规模可控 → 快排随便用； 输入来自外部 → 必须让最坏有保证（三数取中 + 随机化 + 三路划分 + 深度兜底）， 这已经不是性能问题，而是可用性 / 安全问题。

回头看本章八种算法的工程分工非常清晰：插入排序活在所有快排的内核里； 快排是内存排序的默认答案；归并扛着「稳定」与「外部排序」两件事； 堆的真实身份是优先队列；计数与基数在定长整数上提供数量级加速； 冒泡、选择、希尔则是理解排序思想的阶梯。它们在真实系统里怎么被调用、参数怎么标定， 还会在第 12 讲继续往源码级深挖。

11.12 本章小结、易错点与自测

11.12.1 必须记住的十二件事

11.12.2 易错点清单

11.12.3 速查：如何从「中间状态」反推算法

11.12.4 自测题（答案折叠，先自己做）

11.12.5 配套练习建议