排序体系与下界分析（下）

12.1 五大排序体系总览：把 23 种排序归位

12.1.1 为什么要先分类

排序算法有几十种，如果只是把它们当成一堆互不相干的名字去背，考试时很容易「记住了却用不出来」。 但如果你知道每一个算法属于哪一族，很多事情会瞬间变得清晰：

• 复杂度可以推测。同一族的算法，往往共享同一套复杂度下界与优化瓶颈。 比如插入类所有变体（直接插入、折半插入、表插入、2-路插入）的时间复杂度都是 O(n²)， 它们之间的差别只是「少比较几次」或「少移动几次」，属于常数级优化。
• 稳定性可以推测。归并类只要写对「相等时取左段」就一定稳定；交换类只要做「跨越式交换」 就一定不稳定。记住族的性质，比背单个算法的标签可靠得多。
• 适用场景可以推测。插入类吃「基本有序」，交换类吃「逆序对少」， 选择类吃「移动代价高」，归并类吃「链表与外排序」，基数类吃「值域可控」。

所以我们按核心动作（而不是按时间复杂度）把排序分成五大体系。 判断一个算法属于哪一族，只需问一句：它靠什么把元素放到正确位置上？

插入类

靠「找一个位置插进去」。维持一个有序区，把新元素插到有序区的合适位置，其余元素后移。

交换类

靠「交换逆序的一对」。不额外开辟有序区，通过不断消除逆序对来收敛。

选择类

靠「选出最值再放到边界」。每一轮从无序区挑出最小（或最大）的元素，与边界交换或输出。

归并类

靠「合并两个有序段」。分治到长度为 1，再自底向上合并。

基数类

靠「按关键字的值域直接定位」。不做元素间比较，用下标或桶直接算出元素该去的位置。

12.1.2 五大体系分类思维导图

下图把本章涉及的 23 种排序按五大体系铺开，每类都标注了核心思想与代表算法。 图中用「★」标出的是本讲新讲的内容（上一讲已经展开过的用「·」标记）。 建议你把这张图截下来当复习提纲——它就是本讲的目录。

12.1.3 上一讲八种排序的结论汇总

在进入新内容之前，先把上一讲八种排序的结论压缩成一张表。 这张表不含实现细节，只保留「考试要写、面试要答」的那几个数字；完整的大对比表在 12.10 节。

12.2 插入类扩展：三个变体，一条死路

插入排序有两个可优化的量：比较次数（找插入位置要比较几次）和移动次数（腾位置要搬几个元素）。 直接插入排序两者都是 O(n²)。于是很自然地会问： 能不能分别把这两个量降下来？ 本节三个算法正好对应三种尝试：折半插入优化比较、表插入优化移动、2-路插入同时优化两者。 但你会看到——它们都没能突破 O(n²)，原因非常值得琢磨。

12.2.1 折半插入排序：比较次数降到 O(n log n)，但时间还是 O(n²)

一句话本质：既然有序区已经排好，找插入位置就不必逐个比较，直接二分查找。

直接插入排序在找位置时，是拿 A[i] 和有序区从右往左逐个比。 最坏情况下（新元素最小）要比 i 次，累计 1+2+…+(n−1) = O(n²)。 但有序区是有序的——有序就可以二分！用折半查找定位，每次定位只需 ⌈log₂ i⌉ 次比较，累计 Σ log₂ i = O(n log n)。

为什么总时间还是 O(n²)？因为移动次数的瓶颈一点都没缓解。 插入 A[i] 时，为了腾出位置，下标 low..i-1 的所有元素都必须整体后移一格， 这是物理上必须搬动的数据，无法通过「更聪明的查找」省掉。 最坏情况（逆序数组）下，第 i 次插入要移动 i 个元素，累计移动 n(n−1)/2 = O(n²) 次。 一次移动和一次比较在计算模型里都算「一步基本操作」，所以数量级没变。

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

/* ============================================================
   折半插入排序（binary insertion sort）
   与直接插入排序的唯一区别：用折半查找确定插入位置 low，
   从而把「比较次数」从 O(n^2) 降到 O(n*log n)。
   但「移动次数」仍然是 O(n^2)，所以总时间复杂度不变。
   稳定性：用 while (low <= high) 找「第一个大于 key 的位置」，
          相等元素不会被跨过，因此是稳定的。
   ============================================================ */
void binaryInsertionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int low = 0, high = i - 1;
        /* 折半查找：在 a[0..i-1] 中找第一个 > key 的位置 */
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > key) high = mid - 1;   /* 相等时走 else 分支，保证稳定 */
            else               low = mid + 1;
        }
        /* 此时 low 就是插入位置，把 a[low..i-1] 整体后移一格 */
        for (int j = i - 1; j >= low; --j) a[j + 1] = a[j];
        a[low] = key;
    }
}

/* 统计比较次数与移动次数，用于和直接插入排序对照 */
struct Stat { long long cmp, mov; };
Stat binaryInsertionCount(vector<int> a) {
    Stat s{0, 0};
    int n = a.size();
    for (int i = 1; i < n; ++i) {
        int key = a[i], low = 0, high = i - 1;
        while (low <= high) {
            ++s.cmp;
            int mid = low + ((high - low) >> 1);
            if (a[mid] > key) high = mid - 1; else low = mid + 1;
        }
        for (int j = i - 1; j >= low; --j) { a[j + 1] = a[j]; ++s.mov; }
        a[low] = key; ++s.mov;
    }
    return s;
}

/* 直接插入排序的计数版，用来对照 */
Stat directInsertionCount(vector<int> a) {
    Stat s{0, 0};
    int n = a.size();
    for (int i = 1; i < n; ++i) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { ++s.cmp; a[j + 1] = a[j]; ++s.mov; --j; }
        if (j >= 0) ++s.cmp;                    /* 最后一次「不满足条件」的比较也要计入 */
        a[j + 1] = key; ++s.mov;
    }
    return s;
}

int main() {
    vector<int> a = {5, 2, 9, 1, 7, 3, 8, 0, 6, 4};
    binaryInsertionSort(a);
    for (int x : a) cout << x << ' ';
    cout << "\n";                        // 0 1 2 3 4 5 6 7 8 9

    /* 最坏输入：完全逆序，观察两个计数 */
    vector<int> b = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    Stat s = binaryInsertionCount(b);
    Stat d = directInsertionCount(b);
    cout << "n=10 逆序（折半插入）：比较 " << s.cmp << " 次，移动 " << s.mov << " 次\n";
    cout << "n=10 逆序（直接插入）：比较 " << d.cmp << " 次，移动 " << d.mov << " 次\n";
    /* 比较：19 对 45，约从 n^2/2 降到 n*log2(n) 量级；移动：两者都是 54 —— 一点没省！
       这就是「比较降了、时间没降」的实证：移动才是这个算法的时间瓶颈。 */
    return 0;
}

12.2.2 表插入排序：用静态链表把移动次数降为 0

一句话本质：既然移动元素很贵，那就不移动元素——改用 next[] 数组串出一条有序链， 插入时只改两个指针。

数组的随机存取本来是优点，但在插入排序里恰恰成了负担：为了保持「物理下标顺序 = 逻辑顺序」， 每次插入都得搬家。表插入排序（list insertion sort）干脆放弃这个约束： 元素物理位置永远不动，另开一个 next[] 数组， 用 next[i] 表示「逻辑上下一个元素是谁」，形成一个静态链表。

插入过程：先沿 next 链从表头开始逐个比较，找到第一个比新元素大的结点， 然后把新结点挂到它前面。整个过程只有两次指针赋值（next[pre] = i; next[i] = cur;）， 一次元素移动都没有。

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

/* ============================================================
   表插入排序（静态链表插入排序）
   · 元素物理位置永不改变，用 next[] 串成有序静态链表
   · 插入时只改两个指针 → 元素移动次数 = 0
   · 但定位仍需沿链逐个比较 → 比较次数仍为 O(n^2)
   · 失去了随机存取：按逻辑序号取第 k 个元素要 O(k)
   · 稳定性：新结点插在「第一个大于它的结点」之前，相等元素保持原有先后 → 稳定
   ============================================================ */
struct Node {
    int  data;
    int  next;      // 逻辑后继的下标，0 表示链表结束（下标 0 作哨兵，不存数据）
};

void listInsertionSort(vector<Node>& r) {
    int n = r.size() - 1;               // r[0] 是哨兵
    r[0].next = 0;                      // 初始空链表
    for (int i = 1; i <= n; ++i) {
        int pre = 0, cur = r[0].next;   // pre 是 cur 的前驱
        /* 沿链找第一个 data 大于 r[i].data 的结点 */
        while (cur != 0 && r[cur].data <= r[i].data) {
            pre = cur;
            cur = r[cur].next;
        }
        r[i].next = cur;                // 挂链：两步赋值，零元素移动
        r[pre].next = i;
    }
}

/* 沿 next 链输出有序序列（逻辑顺序） */
void printSorted(const vector<Node>& r) {
    for (int p = r[0].next; p != 0; p = r[p].next) cout << r[p].data << ' ';
    cout << "\n";
}

/* 把静态链表「重排」成物理有序：按逻辑顺序重新摆放元素，
   这样重排之后再按数组下标顺序输出就是有序的。这一步是 O(n^2) 的搬移，
   实际工程中通常不做，直接沿链遍历即可。 */
void rearrange(vector<Node>& r) {
    int n = r.size() - 1;
    vector<int> order;
    for (int p = r[0].next; p != 0; p = r[p].next) order.push_back(p);
    vector<Node> tmp(n + 1);
    tmp[0].data = INT_MIN;
    for (int k = 0; k < n; ++k) tmp[k + 1].data = r[order[k]].data;
    for (int k = 0; k <= n; ++k) { r[k].data = tmp[k].data; r[k].next = k + 1; }
    r[n].next = 0;
}

int main() {
    vector<int> a = {4, 2, 6, 1, 5, 3};
    vector<Node> r(a.size() + 1);
    r[0].data = INT_MIN;                // 哨兵：值设为最小，省掉边界判断
    for (int i = 0; i < (int)a.size(); ++i) r[i + 1].data = a[i];

    listInsertionSort(r);
    printSorted(r);                     // 1 2 3 4 5 6
    rearrange(r);
    printSorted(r);                     // 1 2 3 4 5 6（重排后物理也有序）
    return 0;
}

12.2.3 2-路插入排序：移动次数降到约 n²/8

一句话本质：把辅助数组当成循环数组，以第一个元素为界，比它小的往前插、比它大的往后插， 于是「后移」被分摊到了两端，平均只需搬一半的元素。

直接插入排序里，每次插入都要把比新元素大的所有元素后移一位。如果新元素很小，就要搬一大片。 2-路插入（two-way insertion sort）的想法是：让数据从中间向两边长。

1. 开设与 A 等长的辅助数组 D，把 A[0] 放进 D[0]， 用 first 和 final 两个指针标记 D 中已占用区间的两端。
2. 对 A[i]：若 A[i] < D[0]（比界值小），就往前（first 方向）插入； 否则往后（final 方向）插入。
3. 关键是 D 是循环数组：first 往前走到下标 0 之后会绕到 n−1， 所以两端的空间可以互相借用，不会溢出。
4. 因为往两端插入，平均每次只需移动约一半的元素，总移动次数从 n²/2 降到约 n²/8。

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

/* ============================================================
   2-路插入排序（two-way insertion sort）
   · 开一个与待排数组等长的辅助数组 buf，从「两端向中间」使用：
       左段 buf[0..l) 放 < v[0] 的元素，按「递减」排列 —— 等价于不断向左端插入
       右段 buf[r..n) 放 >= v[0] 的元素，按「递增」排列 —— 等价于不断向右端插入
   · 移动量被摊到两端，比直接插入少很多（见下方实测数据）
   · 比较次数与总时间复杂度仍是 O(n^2)，所以这属于「常数级优化」
   · 额外空间 O(n)；相等元素一律走右段且用严格小于才交换 → 稳定
   实现要点：左段是递减的，写回时必须「从后往前」取值才能还原成递增 —— 
            这是本算法最容易写错的一步，写反了数组就完全乱掉。
   ============================================================ */
void twoWayInsertionSort(vector<int>& v, long long* movOut = nullptr) {
    int n = v.size();
    if (n < 2) { if (movOut) *movOut = 0; return; }
    vector<int> buf(n);
    long long mov = 0;
    int l = 0, r = n;                     // 左段 buf[0..l)，右段 buf[r..n)，中间是空闲区

    for (int i = 0; i < n; ++i) {
        int x = v[i];
        if (x < v[0]) {
            /* 左段：递减排列。新元素先放到左段右端，再逐格左移到正确位置 */
            int j = l;
            buf[j] = x; ++mov;
            while (j > 0 && buf[j - 1] < buf[j]) { swap(buf[j - 1], buf[j]); ++mov; --j; }
            ++l;
        } else {
            /* 右段：递增排列。新元素先放到右段左端，再逐格右移到正确位置。
               注意用「严格小于」才交换：相等元素不会互相跨过 → 稳定 */
            int j = r - 1;
            buf[j] = x; ++mov;
            while (j + 1 < n && buf[j + 1] < buf[j]) { swap(buf[j], buf[j + 1]); ++mov; ++j; }
            --r;
        }
    }
    /* 写回：左段递减 → 从 l-1 倒着取，正好是递增；右段本来就是递增，顺着取 */
    int k = 0;
    for (int i = l - 1; i >= 0; --i) v[k++] = buf[i];
    for (int i = r; i < n; ++i) v[k++] = buf[i];
    if (movOut) *movOut = mov;
}

/* 对照：直接插入排序的移动次数 */
long long directMoveCount(const vector<int>& src) {
    vector<int> a = src;
    long long mov = 0;
    for (int i = 1; i < (int)a.size(); ++i) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; ++mov; --j; }
        a[j + 1] = key; ++mov;
    }
    return mov;
}

int main() {
    vector<int> a = {5, 2, 9, 1, 7, 3, 8, 0, 6, 4};
    twoWayInsertionSort(a);
    for (int x : a) cout << x << ' ';
    cout << "\n";                       // 0 1 2 3 4 5 6 7 8 9

    /* 正确性验证：随机数据（含大量重复值）批量比对 */
    mt19937 rng(7);
    int fails = 0;
    for (int test = 0; test < 20000; ++test) {
        int n = 1 + (int)(rng() % 80);
        int range = 1 + (int)(rng() % 25);      // 故意让值域很小，制造大量重复
        vector<int> v(n), w;
        for (int i = 0; i < n; ++i) v[i] = (int)(rng() % range);
        w = v;
        sort(w.begin(), w.end());
        twoWayInsertionSort(v);
        if (v != w) ++fails;
    }
    cout << "20000 组随机数据（含重复元素）验证：" << (fails == 0 ? "全部通过" : "有失败") << "\n";

    /* 移动次数对照：为什么说它只是「常数级优化」 */
    vector<int> b = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    long long m2 = 0;
    vector<int> b2 = b;
    twoWayInsertionSort(b2, &m2);
    cout << "n=10 逆序：2-路插入移动 " << m2 << " 次，直接插入移动 "
         << directMoveCount(b) << " 次\n";

    /* 随机数据上的平均移动次数（n = 200，跑 200 次取平均） */
    double s2 = 0, s1 = 0;
    const int TRIALS = 200, N = 200;
    for (int t = 0; t < TRIALS; ++t) {
        vector<int> v(N);
        for (int i = 0; i < N; ++i) v[i] = (int)(rng() % 100000);
        long long mm = 0;
        vector<int> v2 = v;
        twoWayInsertionSort(v2, &mm);
        s2 += (double)mm;
        s1 += (double)directMoveCount(v);
    }
    cout << "n=200 随机数据平均移动次数：2-路插入 " << (long long)(s2 / TRIALS)
         << "，直接插入 " << (long long)(s1 / TRIALS)
         << "（n^2/2 = " << N * N / 2 << "）\n";
    cout << "→ 移动量确实少了很多，但仍是 O(n^2) 量级：所以总时间复杂度依然是 O(n^2)。\n";
    return 0;
}

12.3 交换类扩展：鸡尾酒、梳排序与奇偶排序

交换类的共同特征：不开辟新的有序区，靠不断把逆序的相邻（或相隔 gap 的）元素对换掉来收敛。 冒泡是它的最朴素形态，快排是它的最强形态，中间还夹着几个很有意思的改良版。

12.3.1 鸡尾酒排序：一趟向右，一趟向左

一句话本质：冒泡每趟只能把最大值推到右端；鸡尾酒排序交替方向， 正反各来一趟，于是最大值和最小值能同时向两端就位。

回忆冒泡的退化场景：数组 [2,3,4,5,6,7,8,1]。 前面 7 个已经有序，只有最小值 1 在最右端。冒泡每一趟只能把元素向左挪一格（因为它是靠相邻交换推进的）， 所以 1 要挪到最左端需要足足 7 趟。而鸡尾酒排序第 1 趟从左到右把 8 送到末尾， 第 2 趟从右到左扫描时，1 会被连续交换一路带到开头——2 趟搞定。

下面这个动画把两个算法放在同一组数据上并排跑，你可以直接对比它们的趟数、比较次数与交换次数：

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

/* ============================================================
   鸡尾酒排序（cocktail sort / 双向冒泡排序）
   · 奇数趟从左到右（把最大值推到右端），偶数趟从右到左（把最小值推到左端）
   · 对「大部分有序，但最值落在错误一端」的数据，趟数可大幅减少
   · 最好 O(n)（本身有序时一趟就发现无交换）；平均与最坏仍 O(n^2)
   · 空间 O(1)；稳定（只交换严格逆序的相邻元素）
   下面这版用 lo / hi 收缩边界，一趟正向 + 一趟反向算「两趟」，
   但终止条件是「某一趟没有任何交换」，比死板地跑完 n-1 轮更早停。
   ============================================================ */
void cocktailSort(vector<int>& a) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        bool sw = false;
        for (int i = lo; i < hi; ++i)                 /* 正向一趟 */
            if (a[i] > a[i + 1]) { swap(a[i], a[i + 1]); sw = true; }
        --hi;
        if (!sw) break;                               /* 一趟无交换 → 已整体有序 */
        sw = false;
        for (int i = hi; i > lo; --i)                 /* 反向一趟 */
            if (a[i - 1] > a[i]) { swap(a[i - 1], a[i]); sw = true; }
        ++lo;
        if (!sw) break;
    }
}

/* 返回趟数，用于和普通冒泡对比。
   「一趟」= 一次单向扫描（正向或反向各算一趟），这样和冒泡的趟数可以直接比较。 */
int cocktailPasses(const vector<int>& src, long long& cmps) {
    vector<int> a = src;
    int lo = 0, hi = (int)a.size() - 1, pass = 0;
    cmps = 0;
    while (lo < hi) {
        /* 正向一趟：把最大值送到 a[hi] */
        bool sw = false;
        for (int i = lo; i < hi; ++i) { ++cmps; if (a[i] > a[i + 1]) { swap(a[i], a[i + 1]); sw = true; } }
        ++pass; --hi;
        if (!sw) break;
        /* 反向一趟：把最小值送到 a[lo] —— 关键就是这一趟 */
        sw = false;
        for (int i = hi; i > lo; --i) { ++cmps; if (a[i - 1] > a[i]) { swap(a[i - 1], a[i]); sw = true; } }
        ++pass; ++lo;
        if (!sw) break;
    }
    return pass;
}

int bubblePasses(const vector<int>& src, long long& cmps) {
    vector<int> a = src;
    int n = a.size(), pass = 0;
    cmps = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) { ++cmps; if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); swapped = true; } }
        ++pass;
        if (!swapped) break;
    }
    return pass;
}

int main() {
    vector<int> a = {2, 3, 4, 5, 6, 7, 8, 1};
    long long c1 = 0, c2 = 0;
    cout << "冒泡趟数   = " << bubblePasses(a, c1)   << "，比较 " << c1 << " 次\n";   // 7，比较 28 次
    cout << "鸡尾酒趟数 = " << cocktailPasses(a, c2) << "，比较 " << c2 << " 次\n";   // 3，比较 18 次
    /* 小口径说明（考点与实现要对得上）：
       理论上"两趟就够"——正向一趟把 8 送到右端、反向一趟把 1 送到左端，
       这两趟共比较 7 + 6 = 13 次；
       但本实现还要再跑一趟"没有发生交换"的确认趟（5 次比较）才能确认已经有序，
       所以程序统计出来是 3 趟、18 次比较。
       考点的口径记住「鸡尾酒 2 趟 vs 冒泡 7 趟」即可；18 次是含确认趟的实现计数。 */

    vector<int> b = a;
    cocktailSort(b);
    for (int x : b) cout << x << ' ';
    cout << "\n";                     // 1 2 3 4 5 6 7 8

    /* 随机数据上验证正确性 */
    mt19937 rng(11);
    for (int t = 0; t < 200; ++t) {
        int n = 1 + (int)(rng() % 50);
        vector<int> v(n), w;
        for (int i = 0; i < n; ++i) v[i] = (int)(rng() % 15);
        w = v;
        sort(w.begin(), w.end());
        cocktailSort(v);
        if (v != w) { cout << "随机测试失败！\n"; return 1; }
    }
    cout << "200 组随机数据验证通过\n";
    return 0;
}

12.3.2 梳排序：gap 递减的「粗排 + 收尾」

一句话本质：它是冒泡与希尔思想的私生子——用不断缩小的间隔 gap 做跨越式比较， 最后 gap = 1 时退化成标准冒泡来收尾。

冒泡慢在哪？慢在它只能比较相邻元素，一次交换最多消除一个逆序对， 而且一个「小元素在右端」的远距离逆序要挪很多趟。梳排序的做法是： 一开始用很大的 gap（比如 gap = n）去比较 A[i] 与 A[i+gap]， 这样一次交换就能让元素跨越很长的距离；然后让 gap 逐步缩小，做越来越细的调整。 「梳子」的比喻很贴切：先用大齿距把打结处梳开，再换小齿距理顺。

为什么是除以 1.3 而不是除以 2？这是一个经验值（由 Lacey 与 Box 在 1991 年提出）。 关键在于：如果每轮 halving，当 n = 2^k 时 gap 序列会变成 n, n/2, n/4, …, 8, 4, 2, 1，这些 gap 有一个大于 1 的公约数 2， 导致每一轮都在比较同一批「互相之间原本就有序」的下标对，效率很差。 除以 1.3 得到的 gap 序列通常互质性更好，实测平均性能接近 O(n log n)。

下面动图演示 gap 从 10 一路递减到 1 的完整过程，注意「相距 gap 个位置」的连线：

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

/* ============================================================
   梳排序（comb sort）
   · gap 从 n 开始，每轮 gap = floor(gap / 1.3)，最后 gap = 1 时用冒泡收尾
   · 思想 = 冒泡的相邻比较 + 希尔的「大间隔先粗排」
   · 最坏 O(n^2)，平均接近 O(n log n)，空间 O(1)
   · 不稳定：gap > 1 时的交换跨越了中间元素，相等关键字的相对次序会被打乱
   ============================================================ */
void combSort(vector<int>& a) {
    int n = a.size();
    int gap = n;
    bool swapped = true;
    while (gap > 1 || swapped) {
        gap = (int)(gap / 1.3);
        if (gap < 1) gap = 1;
        swapped = false;
        for (int i = 0; i + gap < n; ++i) {
            if (a[i] > a[i + gap]) {
                swap(a[i], a[i + gap]);
                swapped = true;
            }
        }
    }
}

/* 打印 gap 序列，直观看到递减过程 */
void showGaps(int n) {
    int gap = n;
    cout << "gap 序列：" << gap;
    while (gap > 1) {
        gap = (int)(gap / 1.3);
        if (gap < 1) gap = 1;
        cout << " -> " << gap;
    }
    cout << "\n";
}

/* 对照实验：比较「除 1.3」与「除 2（halving）」在 n = 2^k 上的差别 */
long long combSwaps(const vector<int>& src, double divisor) {
    vector<int> a = src;
    int n = a.size(), gap = n;
    long long sw = 0;
    bool swapped = true;
    while (gap > 1 || swapped) {
        gap = (int)(gap / divisor);
        if (gap < 1) gap = 1;
        swapped = false;
        for (int i = 0; i + gap < n; ++i)
            if (a[i] > a[i + gap]) { swap(a[i], a[i + gap]); swapped = true; ++sw; }
    }
    return sw;
}

int main() {
    vector<int> a = {8, 4, 2, 1, 7, 3, 9, 5, 6, 0};
    showGaps(10);                  // 10 -> 7 -> 5 -> 3 -> 2 -> 1
    combSort(a);
    for (int x : a) cout << x << ' ';
    cout << "\n";                  // 0 1 2 3 4 5 6 7 8 9

    /* n = 16，构造一个偏斜输入，对比两种 gap 策略的交换次数 */
    vector<int> b;
    for (int i = 0; i < 16; ++i) b.push_back((i * 7 + 5) % 16);
    cout << "divisor 1.3 交换 " << combSwaps(b, 1.3)
         << " 次；divisor 2.0 交换 " << combSwaps(b, 2.0) << " 次\n";
    return 0;
}

12.3.3 奇偶排序（砖块排序）：为并行而生的交换类

一句话本质：把所有相邻比较拆成「奇数对」和「偶数对」两组，两组交替执行； 同一组内部的比较互不干扰，因此可以完全并行。

奇偶排序（odd-even sort，又叫砖块排序 brick sort）的步骤是：

1. 奇数阶段：比较并交换 (A[1],A[2]), (A[3],A[4]), (A[5],A[6]), …
2. 偶数阶段：比较并交换 (A[0],A[1]), (A[2],A[3]), (A[4],A[5]), …
3. 两个阶段交替进行，直到某一整轮（奇 + 偶）都没有发生交换。

它的时间复杂度是 O(n²)，和冒泡一样差；但它有一个冒泡没有的性质： 奇偶排序是最简单的并行排序算法。因为在奇数阶段里，所有的比较对互不重叠， 在 GPU 或 SIMD 上可以一次性全部算完，于是并行时间复杂度降到 O(n) （需要 O(n) 个处理器）。这是「串行复杂度差但并行友好」的典型案例。 奇偶排序是稳定的（只交换严格逆序的相邻元素）。

12.4 选择类补充：锦标赛排序与树形选择排序

选择类的基本动作是「从无序区选出最值」。简单选择排序的问题在于： 每一轮都要从头扫描一遍，上一轮辛苦比较出来的信息全部丢弃， 所以 n 轮下来是 O(n²) 次比较。 锦标赛排序的核心洞察就是：把比较结果存下来，下一轮就不用重比了。

12.4.1 一句话本质与比较次数分析

把 n 个元素放到完全二叉树的叶子上，两两比赛，小的升到父结点； 父结点继续两两比赛，直到根结点——根就是全局最小值。 这个「每个内部结点保存两个孩子中的胜者」的树，就叫胜者树（winner tree）， 也叫树形选择排序。

建树需要比较多少次？完全二叉树有 n 个叶子和 n−1 个内部结点， 每个内部结点对应一次比较，所以恰好是 n − 1 次—— 这和「线性扫描找最小值需要 n−1 次比较」完全一样，一点没省。 省的地方在后续：

当我们取走根结点（最小值）后，需要找第二小的元素。注意—— 第二小的元素一定在「最小值走过的路径上输给它的那些对手」之中， 因为其它元素都是被这些对手直接或间接淘汰的。 这条路径的长度就是树高 ⌈log₂ n⌉。 所以我们只需把该叶子位置置为 +∞，然后沿着这条路径重赛（重新两两比较）， 用 ⌈log₂ n⌉ 次比较就能得到新的最小值。

12.4.2 胜者树的结构与重赛过程

下面这张图给出 A = [3,1,4,1,5,9,2,6] 的完整胜者树。 注意叶子上的下标标注：内部结点保存的是「赢家所在的叶子下标」而不是值本身， 这样重赛时才能顺着下标找到路径。

下面的动画逐场比赛地建树，然后连续输出 4 个最小值，每次输出后都会演示「重赛」：

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

/* ============================================================
   锦标赛排序（树形选择排序 / 胜者树）
   · 完全二叉树，叶子存原始数据，内部结点存「赢家所在的叶子下标」
   · 建树 n-1 次比较；每输出一个最小值，沿路径重赛 ceil(log2 n) 次
   · 总比较次数 O(n log n)，额外空间 O(n)（2n 个结点的胜者树）
   · 不稳定：相等元素谁先被取走取决于树结构，相对次序会被打乱
   ============================================================ */
struct WinnerTree {
    int n;                      // 叶子个数（补齐到 2 的幂）
    vector<int> val;            // 参赛值，叶子位置为原始数据，其它为 INF
    vector<int> win;            // win[t] = 该子树胜者所在的叶子下标

    explicit WinnerTree(const vector<int>& a) {
        n = 1;
        while (n < (int)a.size()) n <<= 1;            // 补齐到 2 的幂，便于完全二叉树编号
        val.assign(2 * n, INT_MAX);
        for (int i = 0; i < (int)a.size(); ++i) val[n + i] = a[i];
        win.assign(2 * n, -1);
        for (int i = 0; i < n; ++i) win[n + i] = n + i;  // 叶子自己就是胜者
        build();
    }

    /* 自底向上建树：每个内部结点比较一次，共 n-1 次 */
    void build() {
        for (int t = n - 1; t >= 1; --t) {
            int L = win[2 * t], R = win[2 * t + 1];
            win[t] = (val[L] <= val[R]) ? L : R;
        }
    }

    /* 输出全部元素（非递减） */
    vector<int> sortAll() {
        vector<int> out;
        for (int k = 0; k < n; ++k) {
            int best = win[1];                            // 根结点给出最小值所在叶子
            if (val[best] == INT_MAX) break;              // 补齐出来的空位，跳过
            out.push_back(val[best]);
            val[best] = INT_MAX;                          // 该选手退赛
            /* 沿路径重赛：从叶子一路比到根 */
            for (int t = best / 2; t >= 1; t /= 2) {
                int L = win[2 * t], R = win[2 * t + 1];
                win[t] = (val[L] <= val[R]) ? L : R;
            }
        }
        return out;
    }
};

/* 统计比较次数，验证 n-1 + (n-1)*log2(n) 的量级 */
long long tournamentComparisons(const vector<int>& a, int& logn) {
    int n = 1;
    while (n < (int)a.size()) n <<= 1;
    logn = 0;
    for (int t = n; t > 1; t >>= 1) ++logn;          // logn = log2(n)
    vector<int> val(2 * n, INT_MAX), win(2 * n, -1);
    for (int i = 0; i < (int)a.size(); ++i) val[n + i] = a[i];
    for (int i = 0; i < n; ++i) win[n + i] = n + i;
    long long cmp = 0;
    for (int t = n - 1; t >= 1; --t) {                 // 建树：n-1 次比较
        int L = win[2 * t], R = win[2 * t + 1];
        ++cmp;
        win[t] = (val[L] <= val[R]) ? L : R;
    }
    int got = 0;
    while (got < (int)a.size()) {
        int best = win[1];
        if (val[best] == INT_MAX) break;
        ++got;
        val[best] = INT_MAX;
        for (int t = best / 2; t >= 1; t /= 2) {       // 重赛：最多 log2(n) 次比较
            int L = win[2 * t], R = win[2 * t + 1];
            ++cmp;
            win[t] = (val[L] <= val[R]) ? L : R;
        }
    }
    return cmp;
}

/* 对照：简单选择排序的比较次数（与数据无关，恒为 n(n-1)/2） */
long long selectionComparisons(int n) { return (long long)n * (n - 1) / 2; }

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    WinnerTree wt(a);
    for (int x : wt.sortAll()) cout << x << ' ';
    cout << "\n";       // 1 1 2 3 4 5 6 9

    int logn = 0;
    long long cmp = tournamentComparisons(a, logn);
    cout << "n=8：胜者树比较 " << cmp << " 次（建树 " << (8 - 1)
         << " + 每次重赛 " << logn << " 层），简单选择排序需要 "
         << selectionComparisons(8) << " 次\n";

    /* 换一个更大的规模，差距才看得出来 */
    const int N = 1 << 14;                       // n = 16384
    vector<int> big(N);
    mt19937 rng(99);
    for (int i = 0; i < N; ++i) big[i] = (int)(rng() % 1000000);
    int lg2 = 0;
    long long c2 = tournamentComparisons(big, lg2);
    cout << "n=" << N << "：胜者树约 " << c2 << " 次，简单选择排序需要 "
         << selectionComparisons(N) << " 次（约 "
         << (double)selectionComparisons(N) / c2 << " 倍）\n";
    return 0;
}

12.4.3 为什么堆排序取代了胜者树

既然胜者树是 O(n log n)，为什么我们平时讲、平时用的是堆排序而不是胜者树？ 这是考试里非常经典的一道「比较题」，答案有三个层次：

12.5 非比较排序：计数、桶与基数

前面所有算法都在做同一件事：比较两个元素的大小。 而这一节的三种算法一次元素间比较都不做（或只做常数次）， 它们靠的是关键字的值域结构：既然关键字是 0～k 的整数，那我直接把「值」当下标用不就行了？ 正因为它们绕开了「比较」这个模型，12.8 节的 Ω(n log n) 下界对它们不成立。

12.5.1 计数排序：O(n + k) 与「必须稳定」的原因

一句话本质：统计每个值出现几次，用前缀和算出每个值应该占据的下标区间，然后倒序把元素放进输出数组。

计数排序（counting sort）要求关键字是范围可控的非负整数（设值域为 0..k−1）。 三步走：

1. 统计频次：cnt[v] 记录值 v 出现了多少次。这一步只看值，不看顺序。
2. 求前缀和：pre[v] = cnt[0] + cnt[1] + … + cnt[v]， 含义是「值 ≤ v 的元素共有多少个」，也就是值 v 的元素应该落在 [0, pre[v]) 区间的最右端。
3. 倒序放置：从 i = n−1 开始往左遍历原数组，执行 out[--pre[A[i]]] = A[i]。

下面动图把这三步逐帧演示，并把「相同关键字的先后顺序」显式标记出来：

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

/* ============================================================
   计数排序（counting sort）—— 稳定版本
   前提：关键字是 [0, k) 范围内的整数
   时间：O(n + k)      空间：O(n + k)      稳定：是（靠倒序放置保证）
   ============================================================ */
vector<int> countingSort(const vector<int>& a, int k) {
    int n = a.size();
    vector<int> cnt(k, 0), out(n, 0);

    /* 第一步：统计每个值出现的次数，O(n) */
    for (int i = 0; i < n; ++i) ++cnt[a[i]];

    /* 第二步：前缀和。pre[v] 表示「值 <= v 的元素共有多少个」，
       也就是值 v 的元素在输出数组中的「末尾位置（开区间上界）」。O(k) */
    for (int v = 1; v < k; ++v) cnt[v] += cnt[v - 1];

    /* 第三步：倒序遍历原数组，先 --cnt[值] 再落位。
       倒序是稳定性的关键：最后出现的元素先占掉该值的最后一个空位，
       于是更靠前的同值元素只能放在它左边，相对次序得以保持。O(n) */
    for (int i = n - 1; i >= 0; --i) out[--cnt[a[i]]] = a[i];

    return out;
}

/* 反例演示：把第三步写成正序会怎样？（不稳定） */
vector<int> countingSortUnstable(const vector<int>& a, int k) {
    int n = a.size();
    vector<int> cnt(k, 0), pos(k, 0), out(n, 0);
    for (int i = 0; i < n; ++i) ++cnt[a[i]];
    pos[0] = 0;
    for (int v = 1; v < k; ++v) pos[v] = pos[v - 1] + cnt[v - 1];
    for (int i = 0; i < n; ++i) out[pos[a[i]]++] = a[i];   /* 正序 → 相同值被翻转 */
    return out;
}

int main() {
    /* 用「值 * 10 + 原始下标」编码，方便观察稳定性：
       例如 40 = 值 4 且原始下标 0，51 = 值 5 且原始下标 1 */
    vector<int> raw = {4, 1, 3, 4, 3, 2};
    vector<int> enc;
    for (int i = 0; i < (int)raw.size(); ++i) enc.push_back(raw[i] * 10 + i);

    vector<int> s1 = countingSort(enc, 60);
    cout << "稳定版  ：";
    for (int x : s1) cout << "(" << x / 10 << ",idx" << x % 10 << ") ";
    cout << "\n";       /* (1,idx1) (2,idx5) (3,idx2) (3,idx4) (4,idx0) (4,idx3) —— 同值按原下标升序 */

    vector<int> s2 = countingSortUnstable(enc, 60);
    cout << "正序版  ：";
    for (int x : s2) cout << "(" << x / 10 << ",idx" << x % 10 << ") ";
    cout << "\n";       /* (1,idx1) (2,idx5) (3,idx2) (3,idx4) …… 顺序被打乱 */

    vector<int> plain = countingSort(raw, 5);
    for (int x : plain) cout << x << ' ';
    cout << "\n";       // 1 2 3 3 4 4
    return 0;
}

12.5.2 桶排序：先粗分堆，再各自排好

一句话本质：把值域均匀切成 m 段（桶），把元素按值丢进对应的桶， 每个桶内部单独排序，最后按桶号顺序收集。

桶排序（bucket sort）和计数排序的关系很密切：计数排序是「一个值一个桶」的极端情形， 桶排序则是「一个区间一个桶」，因此它不要求关键字是整数，只要求能把值映射到桶号 （常见做法是 ⌊x · m⌋，其中 x ∈ [0,1)）。

复杂度分析的关键在于数据分布。假设 n 个元素独立均匀地落在 [0,1)， 开 n 个桶：

• 每个桶里期望只有 1 个元素（n 个球扔进 n 个盒子）， 桶内用插入排序的期望代价是 O(1)；
• 全部桶加起来：分桶 O(n) + 桶内排序 O(n) + 收集 O(n) = O(n)；
• 严格证明要用到「桶大小的平方和期望为 O(n)」这个结论 （每对元素落进同一个桶的概率是 1/n，共 C(n,2) 对，期望 (n−1)/2）， 所以总代价是 O(n)。

最坏情况：所有数据都挤在一个桶里（例如数据全部集中在 [0.9, 1.0)）， 桶排序就退化成对一个长度为 n 的数组做插入排序 → O(n²)。 所以工程上桶排序往往配合「先抽样估计分布」使用。 桶排序是稳定的（前提：分桶时按原顺序追加、桶内用稳定排序）。

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

/* ============================================================
   桶排序（bucket sort）—— 适用于 [0,1) 上近似均匀分布的浮点数
   · 分桶 O(n) + 桶内插入排序 O(n)（均匀分布时）+ 收集 O(n) = O(n)
   · 最坏 O(n^2)（数据全部集中到同一个桶）
   · 额外空间 O(n + m)；稳定（分桶按原序追加 + 桶内用插入排序）
   ============================================================ */
void bucketSort(vector<double>& a, int m) {
    int n = a.size();
    if (n < 2) return;
    vector<vector<double>> b(m);

    /* 分桶：按原数组顺序追加，保证桶内相对次序不变 → 稳定性的第一个条件 */
    for (int i = 0; i < n; ++i) {
        int k = (int)(a[i] * m);
        if (k >= m) k = m - 1;              /* 边界：a[i] 恰好等于 1.0 时兜底 */
        b[k].push_back(a[i]);
    }

    /* 桶内排序：插入排序常数小、且稳定 → 稳定性的第二个条件 */
    for (int k = 0; k < m; ++k) {
        for (int i = 1; i < (int)b[k].size(); ++i) {
            double key = b[k][i];
            int j = i - 1;
            while (j >= 0 && b[k][j] > key) { b[k][j + 1] = b[k][j]; --j; }
            b[k][j + 1] = key;
        }
    }

    /* 按桶号从小到大收集 */
    int idx = 0;
    for (int k = 0; k < m; ++k)
        for (double x : b[k]) a[idx++] = x;
}

/* 统计各桶元素个数，直观看到「均匀 vs 集中」的差别 */
void showBucketLoad(const vector<double>& a, int m) {
    vector<int> cnt(m, 0);
    for (double x : a) { int k = min((int)(x * m), m - 1); ++cnt[k]; }
    for (int k = 0; k < m; ++k) cout << "桶" << k << ":" << cnt[k] << "  ";
    cout << "\n";
}

int main() {
    vector<double> a = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.68, 0.33};
    showBucketLoad(a, 5);                  // 桶0:2 桶1:2 桶2:2 桶3:2 桶4:2 —— 很均匀
    bucketSort(a, 5);
    for (double x : a) cout << x << ' ';
    cout << "\n";                          // 0.12 0.17 0.21 0.26 0.33 0.39 0.68 0.72 0.78 0.94

    /* 反例：数据集中在 [0.9, 1.0) */
    vector<double> c;
    for (int i = 0; i < 10; ++i) c.push_back(0.9 + i * 0.009);
    showBucketLoad(c, 5);                  // 桶0:0 桶1:0 桶2:0 桶3:0 桶4:10 —— 全部挤在一个桶
    cout << "全部落进同一个桶 → 退化为对一个长度 n 的数组做插入排序 → O(n^2)\n";
    return 0;
}

12.5.3 基数排序的 LSD 与 MSD

基数排序（radix sort）在上一讲已经讲过 LSD（最低位优先，Least Significant Digit） 版本， 这里只补充两种方向的对照与结论，细节请回看第 11 讲。

12.6 归并类扩展：多路归并、胜者树/败者树与原地归并

归并类最朴素的形式是 2-路归并，它在上一讲已经详细讲过。本节要把归并这条线拉长： 往大处走，就是 k 路归并与外部排序（内存装不下时怎么办）； 往小处走，就是原地归并（不想开 O(n) 辅助数组时怎么办）。

12.6.1 2-路归并的复习与「单趟 O(n)」结论

先明确一个后面反复要用的结论：把两个长度分别为 L、R 的有序段合并成一个有序段， 比较次数最多 L + R − 1 次，时间严格 O(L + R) = O(n)。 原因很简单：每做一次比较就至少有一个元素被「定下来」输出，除了最后一次之外不会有浪费。

下面的动画先演示标准 2-路归并（需要辅助数组），再演示原地归并的手摇算法：

12.6.2 多路归并：为什么外排序一定要用 k 路

一句话本质：外部排序的时间几乎全花在磁盘 I/O 上，所以要用「更大的归并路数 k」 来减少归并的趟数，从而减少读写磁盘的次数。

场景：一个 100GB 的文件要排序，内存只有 1GB。做法是：

1. 置换选择 / 内部排序生成初始归并段：每次读进内存能装下的部分，排好序写回磁盘， 得到一个「归并段（run）」。100GB / 1GB = 100 个归并段。
2. 多趟 k 路归并：把 k 个归并段合并成一个更大的归并段，反复进行直到只剩一个。

为什么 k 越大越省？设初始归并段有 m 个，做 k 路归并， 则归并趟数为 S = ⌈log_k m⌉，每趟都要把全部 n 条记录读一遍、写一遍， 所以总 I/O 次数 = 2n·⌈log_k m⌉（读 + 写各 n）。看这个式子：k 在底数上，趟数随 k 对数下降。

但天下没有免费的午餐：k 路归并每一轮都要「从 k 个归并段的当前首元素中挑出最小的」。 朴素做法是线性扫描 k 个候选，每次输出花 O(k)， 总共 O(nk) 次比较。当 k 很大（比如 100），这部分内部计算的开销就会盖过 I/O 的收益。 于是我们需要一个「从 k 个候选里 O(log k) 取最小」的结构——胜者树 / 败者树。

工程上用的具体是败者树（loser tree），它是胜者树的改良版。为了让你看清两者的关系， 下面先讲清胜者树这条更直观的路线，再说明败者树做了什么改进。

12.6.3 胜者树与败者树：把「k 选 1」从 O(k) 降到 O(log k)

一句话本质：把 k 个归并段当前的首元素放到一棵完全二叉树的叶子上， 内部结点保存「这一小场比赛的结论」。选最小值只看根，取走之后只沿一条路径重赛， 于是每次更新只需 ⌈log₂ k⌉ 次比较。

两种树的差别只有一句话，但效果差别很大：

胜者树

内部结点保存胜者（较小者）的叶子编号。取走冠军后沿路径重赛时， 每一层必须重新访问两个孩子才能算出谁是胜者，所以每层要触及两个结点。

败者树

内部结点保存败者，冠军另外用 ls[0] 单独存放。 重赛时「赢家已经被带上来了」，所以每层只需拿当前赢家与结点上记着的那个败者比一次， 不必再去访问兄弟结点——路径上访问的结点数约为胜者树的一半。

两者都是 O(log k) 次比较，差别在常数（每层访问的结点数）。 下图给出败者树的结构与一次完整的重赛过程：

下面这份实现给出 k 路归并 + 胜者树选择器。选胜者树而不是败者树来写，是因为它更直观、 更容易一次写对；两者复杂度相同，把这份代码里的 recompute 改成 「只与结点记录的败者比较一次、不访问兄弟结点」，就得到败者树版本。

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

/* ============================================================
   k 路归并 + 胜者树选择器（外部排序的核心构件）
   · 问题：从 k 个有序归并段中反复挑出最小值。朴素做法每输出一个
     要扫描 k 个候选 → O(k)；用树形结构可以压到 O(log k)。
   · 胜者树（winner tree）：把 k 个归并段当前的首元素放在完全二叉树
     的叶子上，内部结点保存「两个孩子中的胜者（较小者）的叶子编号」。
     取最小值 = 读根结点 O(1)；取走后只沿该叶子到根的路径重赛，
     路径长度 = ⌈log2 k⌉ → 单次更新 O(log k)。
   · 这就是外部排序所用「败者树」的同族结构。两者的复杂度都是
     O(log k)；败者树的差别只在于把「败者」而不是「胜者」记在结点上，
     于是重赛时每层不必再去访问兄弟结点，路径上访问的结点少一半
     （见正文图 12-6 的对比说明）。
   · 实现要点：叶子编号从 K 开始（K = 把 k 向上补齐到 2 的幂），
     于是父结点 = t/2、左孩子 = 2t、右孩子 = 2t+1；
     补齐出来的空叶子值恒为 INT_MAX，永远当败者。
   ============================================================ */
struct WinnerTree {
    int k, K;                    // k = 归并路数；K = 补齐到 2 的幂
    vector<int> key;             // 叶子值，下标 K .. 2K-1
    vector<int> win;             // win[t] = 结点 t 子树中最小值的叶子编号；-1 表示该子树全空
    vector<int> owner;           // owner[leaf] = 该叶子属于哪一路

    explicit WinnerTree(const vector<vector<int>>& runs) {
        k = runs.size();
        K = 1;
        while (K < k) K <<= 1;                       // 补齐到 2 的幂
        key.assign(2 * K, INT_MAX);
        owner.assign(2 * K, -1);
        win.assign(K, -1);
        for (int i = 0; i < k; ++i)
            if (!runs[i].empty()) { key[K + i] = runs[i][0]; owner[K + i] = i; }
        for (int t = K - 1; t >= 1; --t) recompute(t);   // 自底向上建树
        win[0] = relink();
    }

    /* 取结点 node 子树的胜者；叶子若已取空（值为 INT_MAX）则返回 -1 */
    int kid(int node) const {
        if (node >= K) return (key[node] == INT_MAX) ? -1 : node;
        return win[node];
    }
    /* 用两个孩子重算结点 t：两边都空则 t 也空，否则取较小者 */
    void recompute(int t) {
        int a = kid(2 * t), b = kid(2 * t + 1);
        if (a < 0)       win[t] = b;
        else if (b < 0)  win[t] = a;
        else             win[t] = (key[a] <= key[b]) ? a : b;
    }
    int relink() { return (K == 1) ? kid(K) : win[1]; }

    int champion() const { return win[0]; }            // 全局最小值所在叶子；-1 表示全部取完

    /* 某个叶子的值被改动（或该路取空）之后，沿路径重赛：每层一次比较 */
    void update(int leaf) {
        for (int t = leaf / 2; t >= 1; t /= 2) recompute(t);
        win[0] = relink();
    }
};

/* 用胜者树做 k 路归并 */
vector<int> kWayMerge(const vector<vector<int>>& runs, long long& treeHeight) {
    int k = runs.size();
    treeHeight = 0;
    for (int t = k; t > 1; t >>= 1) ++treeHeight;      // 树高 = ⌈log2 k⌉
    vector<int> pos(k, 0), out;
    WinnerTree wt(runs);
    while (true) {
        int leaf = wt.champion();
        if (leaf < 0) break;                           // 全部取完
        int seg = wt.owner[leaf];
        out.push_back(wt.key[leaf]);
        ++pos[seg];
        /* 从该段读入下一条记录；段空了就置为 INF（等价于「该选手退赛」） */
        wt.key[leaf] = (pos[seg] < (int)runs[seg].size()) ? runs[seg][pos[seg]] : INT_MAX;
        wt.update(leaf);
    }
    return out;
}

/* 对照：朴素 k 路扫描，每输出一个元素要比较 O(k) 次 */
vector<int> naiveKWayMerge(const vector<vector<int>>& runs, long long& cmps) {
    int k = runs.size();
    vector<int> pos(k, 0), out;
    cmps = 0;
    while (true) {
        int best = -1;
        for (int i = 0; i < k; ++i) {
            if (pos[i] >= (int)runs[i].size()) continue;
            ++cmps;
            if (best < 0 || runs[i][pos[i]] < runs[best][pos[best]]) best = i;
        }
        if (best < 0) break;
        out.push_back(runs[best][pos[best]++]);
    }
    return out;
}

int main() {
    /* ---- 例 1：k = 5 的小例子，结果一目了然 ---- */
    vector<vector<int>> runs = {
        {12, 30, 44},
        {7,  18, 55},
        {3,  15, 21},
        {25, 27, 40},
        {9,  33, 36}
    };
    long long h1 = 0, c2 = 0;
    vector<int> r1 = kWayMerge(runs, h1);
    vector<int> r2 = naiveKWayMerge(runs, c2);
    for (int x : r1) cout << x << ' ';
    cout << "\n";        // 3 7 9 12 15 18 21 25 27 30 33 36 40 44 55
    cout << "两种实现结果一致：" << (r1 == r2 ? "是" : "否") << "\n";

    /* ---- 例 2：批量随机测试，验证正确性（含空段与大量重复值） ---- */
    mt19937 rng(11);
    int fails = 0;
    for (int t = 0; t < 20000; ++t) {
        int k = 1 + (int)(rng() % 24);
        vector<vector<int>> rs(k);
        for (int i = 0; i < k; ++i) {
            int len = (int)(rng() % 8);
            for (int j = 0; j < len; ++j) rs[i].push_back((int)(rng() % 50));
            sort(rs[i].begin(), rs[i].end());          // 每个归并段内部有序
        }
        long long hh = 0, cc = 0;
        if (kWayMerge(rs, hh) != naiveKWayMerge(rs, cc)) ++fails;
    }
    cout << "20000 组随机 k 路归并测试（k = 1..24，含空段）："
         << (fails == 0 ? "全部通过" : "有失败") << "\n";

    /* ---- 例 3：规模大一点，看 O(log k) 与 O(k) 的差距 ---- */
    const int K = 64, PER = 200;
    vector<vector<int>> big(K);
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j < PER; ++j) big[i].push_back((int)(rng() % 100000));
        sort(big[i].begin(), big[i].end());
    }
    long long h2 = 0, d2 = 0;
    vector<int> m1 = kWayMerge(big, h2);
    vector<int> m2 = naiveKWayMerge(big, d2);
    cout << "k = " << K << "、每段 " << PER << " 条记录，共 " << m1.size() << " 条：\n";
    cout << "  胜者树  ：每次重赛沿路径比较 " << h2 << " 次（⌈log2 " << K << "⌉），合计约 "
         << h2 * (long long)m1.size() << " 次\n";
    cout << "  朴素扫描：每轮最多 " << K << " 次，合计 " << d2 << " 次\n";
    cout << "  结果一致：" << (m1 == m2 ? "是" : "否") << "\n";
    cout << "→ k 越大，两者的差距越大：这就是外部排序必须用树形选择器的原因。\n";
    return 0;
}

12.6.4 原地归并：手摇算法（三次翻转）

一句话本质：归并之所以要 O(n) 辅助空间，是因为「把右边的元素插到左边元素之前」 必须腾地方。手摇算法发现：如果只是交换两个相邻的块，可以原地做——翻转三次就行。

问题描述：数组里有相邻两块 L = A[l..m-1] 与 R = A[m..r]， 想在不使用额外空间的前提下把它们整体换位（保持各自块内顺序），变成 R L。

举个具体例子，交换 L = [1,2] 与 R = [3,4]（合并成 [1,2,3,4]）：

1. 翻转 L：[2,1 | 3,4]
2. 翻转 R：[2,1 | 4,3]
3. 翻转整体：[3,4,1,2] ✅ 两块位置互换了，而且各自内部顺序也恢复了。

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

/* ============================================================
   原地归并（手摇算法 / three reversals）
   · 用「三次翻转」原地交换相邻两块，从而避免 O(n) 辅助数组
   · 空间 O(1)，但元素移动次数最坏 O(n^2)（比标准归并的 O(n) 差得多）
   · 不稳定：整块交换会打乱跨越两块的相等元素的相对次序
   ============================================================ */

/* 三次翻转：把 a[l..m-1] 与 a[m..r] 两块整体换位（保持各自块内顺序） */
void handShake(vector<int>& a, int l, int m, int r) {
    reverse(a.begin() + l, a.begin() + m);        /* ① 翻转左块 */
    reverse(a.begin() + m, a.begin() + r + 1);    /* ② 翻转右块 */
    reverse(a.begin() + l, a.begin() + r + 1);    /* ③ 翻转整段 */
}

/* 递归版原地归并：先找需要交换的边界，再用二分 + 手摇把块换位 */
void inplaceMergeRec(vector<int>& a, int l, int m, int r) {
    if (l >= m || m > r) return;
    int i = l, j = m;
    /* 跳过左块中已经比右块首元素小的前缀 */
    while (i < m && a[i] <= a[m]) ++i;
    /* 跳过右块中比 a[i] 小的前缀：这些元素最终要整体挪到左块前面 */
    while (j <= r && a[j] < a[i]) ++j;
    if (i == m) return;                            /* 左块整体小于右块 → 已就绪 */
    if (i == j - 1) { swap(a[i], a[m]); }          /* 退化情形：只剩一个元素要换，直接交换 */
    else          { handShake(a, i, m, j - 1); }   /* 两块整体换位 */
    /* 换位之后，a[i..i+(j-m)-1] 已经就位，剩下的两段递归处理 */
    int newMid = i + (j - m);
    inplaceMergeRec(a, newMid, j, r);
}

void inplaceMergeSort(vector<int>& a, int l, int r) {
    if (r - l < 1) return;
    int m = l + ((r - l) >> 1);
    inplaceMergeSort(a, l, m);
    inplaceMergeSort(a, m + 1, r);
    inplaceMergeRec(a, l, m + 1, r);
}

/* 对照：标准归并（需要 O(n) 辅助数组），用来验证原地版结果一致 */
void stdMergeSort(vector<int>& a, int l, int r, vector<int>& buf) {
    if (r - l < 1) return;
    int m = l + ((r - l) >> 1);
    stdMergeSort(a, l, m, buf);
    stdMergeSort(a, m + 1, r, buf);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) buf[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= m) buf[k++] = a[i++];
    while (j <= r) buf[k++] = a[j++];
    for (int t = l; t <= r; ++t) a[t] = buf[t];
}

int main() {
    vector<int> a = {1, 4, 7, 2, 3, 9};
    handShake(a, 0, 3, 5);                     /* 交换 [1,4,7] 与 [2,3,9] */
    for (int x : a) cout << x << ' ';
    cout << "\n";                              /* 2 3 9 1 4 7 */

    vector<int> b = {8, 3, 5, 1, 9, 2, 7, 4, 6, 0};
    vector<int> c = b, buf(b.size());
    inplaceMergeSort(b, 0, b.size() - 1);
    stdMergeSort(c, 0, c.size() - 1, buf);
    for (int x : b) cout << x << ' ';
    cout << "\n";                              /* 0 1 2 3 4 5 6 7 8 9 */
    cout << "原地版与标准版结果一致：" << (b == c ? "是" : "否") << "\n";
    return 0;
}

12.7 工程实战：标准库到底用的是什么排序

学完理论，最有价值的一步是看看真正被千万行代码调用的排序长什么样。 你会发现标准库的做法和教科书完全不同——它不追求某一个算法的最优， 而是追求「在所有输入上都不会太差」。

12.7.1 std::sort 的内省排序（Introsort）

一句话本质：以快速排序为主干，用插入排序处理小区间，用堆排序兜底递归过深的情况， 三种算法各管一段，拼出「平均接近快排 + 最坏 O(n log n)」。

为什么非要这么拼？因为快排有两个天生的短板：

• 小区间效率低。当区间只剩十几个元素时，快排还要递归划分、还要选枢轴， 函数调用与划分的开销远超实际需要的比较次数。而插入排序在小规模、基本有序的数据上常数最小。 所以主流实现都设一个阈值（libstdc++ 是 16），区间长度 ≤ 阈值时直接插排返回。
• 深度会失控。如果枢轴每次都选到最值（比如对手刻意构造的输入）， 划分变成 1 : n−1，递归深度退化成 O(n)，时间复杂度 O(n²)，甚至爆栈。内省（introspective） 的含义就是：算法自己监视递归深度，一旦超过 2⌊log₂ n⌋ 就判定「划分已经严重偏斜」， 立刻改用堆排序处理该区间——堆排最坏也是 O(n log n)，且额外空间 O(1)。

下面动图把「当前处在哪种模式」实时标出来，你可以看到深度超限时是如何切换到堆排的：

下面这份代码是一个可以直接编译运行的 introsort 实现，把三道保险都写全了：

#include <bits/stdc++.h>
using namespace std;

/* ============================================================
   自己实现 introsort（内省排序）= 快速排序 + 插入排序 + 堆排序
   竞赛写法：全局数组 + 自由函数，区间统一用 [lo, hi) 左闭右开
     · 主干：三数取中选枢轴的快速排序
     · 小区间（len <= 16）：改用插入排序收尾
     · 递归深度 > 2*floor(log2(n))：改用堆排序，保证最坏 O(n log n)
   平均 O(n log n)，最坏 O(n log n)，空间 O(log n)，不稳定
   数组大小依据：MAXN = 3e5 + 5，够放 3e5 个元素
   ============================================================ */

const int MAXN = 300005;
const int INSERTION_THRESHOLD = 16;

int a[MAXN];
int n = 0;

/* ---------- 插入排序：只处理 [lo, hi) ---------- */
void insertionSort(int lo, int hi) {
    for (int i = lo + 1; i < hi; ++i) {
        int key = a[i], j = i;
        while (j > lo && a[j - 1] > key) { a[j] = a[j - 1]; --j; }
        a[j] = key;
    }
}

/* ---------- 下沉：把 a[lo .. lo+len-1] 看成堆，调整下标 root ---------- */
void siftDown(int lo, int len, int root) {
    while (true) {
        int child = 2 * root + 1;
        if (child >= len) break;
        if (child + 1 < len && a[lo + child] < a[lo + child + 1]) ++child;   // 取较大的孩子
        if (a[lo + root] < a[lo + child]) {
            swap(a[lo + root], a[lo + child]);
            root = child;
        } else break;
    }
}

/* ---------- 堆排序：只处理 [lo, hi)，最坏也是 O(n log n) ---------- */
void heapSort(int lo, int hi) {
    int len = hi - lo;
    for (int i = len / 2 - 1; i >= 0; --i) siftDown(lo, len, i);      // 建大顶堆
    for (int end = len - 1; end > 0; --end) {
        swap(a[lo], a[lo + end]);                                     // 最大值换到末尾
        siftDown(lo, end, 0);                                         // 剩余部分重新成堆
    }
}

/* ---------- 三数取中：把中位数换到 hi-2 位置并返回该下标 ---------- */
int medianOfThree(int lo, int hi) {          // [lo, hi)
    int mid = lo + (hi - lo) / 2;
    --hi;                                    // 指向最后一个有效元素
    if (a[mid] < a[lo]) swap(a[mid], a[lo]);
    if (a[hi] < a[lo])  swap(a[hi], a[lo]);
    if (a[hi] < a[mid]) swap(a[hi], a[mid]);
    /* 此时 a[lo] <= a[mid] <= a[hi]，把 mid 换到 hi-1 当枢轴，a[hi] 留作右端哨兵 */
    swap(a[mid], a[hi - 1]);
    return hi - 1;
}

/* ---------- 核心：带深度限制的快排 ---------- */
void introsortLoop(int lo, int hi, int depthLimit) {   // [lo, hi)
    while (hi - lo > INSERTION_THRESHOLD) {
        if (depthLimit == 0) { heapSort(lo, hi); return; }   // ① 深度用尽 → 堆排兜底
        --depthLimit;
        int pivot = medianOfThree(lo, hi);                   // ② 三数取中
        int i = lo, j = hi - 1;
        while (true) {
            while (a[++i] < a[pivot]) {}
            while (a[pivot] < a[--j]) {}
            if (i < j) swap(a[i], a[j]); else break;
        }
        swap(a[i], a[pivot]);                                // 枢轴归位
        introsortLoop(i + 1, hi, depthLimit);                // 递归处理右半
        hi = i;                                              // 左半用循环继续处理（尾递归优化）
    }
    /* ③ 小区间直接退出，最后对整个区间做一次插入排序收尾 */
}

void introSort(int lo, int hi) {             // [lo, hi)
    if (hi - lo < 2) return;
    int depthLimit = 2 * (int)log2((double)(hi - lo));       // 2 * floor(log2 n)
    introsortLoop(lo, hi, depthLimit);
    insertionSort(lo, hi);                                   // 小区间收尾
}

int main() {
    n = 40;
    for (int i = 0; i < n; ++i) a[i] = (i * 17 + 5) % 40;
    introSort(0, n);
    for (int i = 0; i < n; ++i) printf("%d ", a[i]);
    printf("\n");

    /* 和标准库结果比对 */
    int b[40];
    for (int i = 0; i < n; ++i) b[i] = a[i];
    sort(b, b + n);
    bool same = true;
    for (int i = 0; i < n; ++i) if (a[i] != b[i]) same = false;
    printf("与 std::sort 结果一致：%s\n", same ? "是" : "否");

    /* 已经有序的输入（快排的经典最坏场景）也不再退化 */
    n = 100000;
    for (int i = 0; i < n; ++i) a[i] = i;
    introSort(0, n);
    printf("10 万条已排序数据 introsort 完成，首尾 = %d %d\n", a[0], a[n - 1]);
    return 0;
}

12.7.2 std::stable_sort：稳定优先的归并实现

std::stable_sort 的实现是归并排序，但它比教科书的归并更讲究空间：

• 先尝试原地做。如果内存分配的尝试失败，它会退化到「原地归并」的版本， 此时时间复杂度从 O(n log n) 恶化到 O(n log² n)—— 但仍然保持稳定。
• 成功时就开 O(n) 缓冲。标准做法是先申请一个 n 大小的临时缓冲区， 然后做自底向上 / 自顶向下的 2-路归并，并对小区间（约 15 个元素）改用插入排序。

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

/* ============================================================
   std::sort（不稳定）与 std::stable_sort（稳定）的行为对比
   场景：先按分数排名，分数相同的按「原顺序」保持先后 —— 这正是稳定性要解决的
   ============================================================ */
struct Student {
    string name;
    int    score;
};

int main() {
    vector<Student> v = {
        {"小明", 90}, {"小红", 85}, {"小刚", 90},
        {"小美", 85}, {"小强", 90}, {"小丽", 85}
    };

    /* ---- 1) std::sort：不稳定，同分学生的相对次序无法保证 ---- */
    vector<Student> a = v;
    std::sort(a.begin(), a.end(), [](const Student& x, const Student& y) {
        return x.score > y.score;            /* 只按分数比较 */
    });
    cout << "std::sort（不稳定）：\n";
    for (auto& s : a) cout << "  " << s.name << " " << s.score << "\n";

    /* ---- 2) std::stable_sort：同分学生保持输入中的先后 ---- */
    vector<Student> b = v;
    std::stable_sort(b.begin(), b.end(), [](const Student& x, const Student& y) {
        return x.score > y.score;
    });
    cout << "std::stable_sort（稳定）：\n";
    for (auto& s : b) cout << "  " << s.name << " " << s.score << "\n";

    /* ---- 3) 如果不允许用 stable_sort，可以自己「加次关键字」把不稳定排序变成稳定排序 ---- */
    vector<pair<Student, int>> c;
    for (int i = 0; i < (int)v.size(); ++i) c.push_back({v[i], i});   // 原始下标作为次关键字
    std::sort(c.begin(), c.end(), [](const pair<Student, int>& x, const pair<Student, int>& y) {
        if (x.first.score != y.first.score) return x.first.score > y.first.score;
        return x.second < y.second;                                   // 同分时按原下标升序 → 等价于稳定
    });
    cout << "自己加次关键字后的 std::sort：\n";
    for (auto& p : c) cout << "  " << p.first.name << " " << p.first.score << "\n";

    cout << "\n后两种结果应当完全一致（都等价于稳定排序）。\n";
    return 0;
}

12.7.3 Timsort：为真实数据而生的排序

一句话本质：真实世界的数据不是随机的——它常常是「几段有序数据拼起来」。 Timsort 先扫描出这些天然有序的游程（run），再用归并把它们合并起来。

Timsort 由 Tim Peters 在 2002 年为 Python 设计，后来成为 Java（对象数组）、 Android、V8 等平台的标准排序。它的核心机制有三点：

1. 识别游程（run）。从左往右扫描，找出一段已经非递减（或严格递减，递减就原地翻转成递增） 的连续片段。真实数据里这种 run 往往很长——比如一个已经按时间排序、又追加了几条新记录的表。
2. 用插入排序把短 run 补到最小长度。如果某个 run 长度小于 minrun（32～64 之间， 由 n 计算得出），就用插入排序把它扩展到 minrun 长度。 因为对「已经基本有序」的片段做插入排序几乎是 O(长度) 的。
3. 用归并合并 run，并用「折半插入 + 加洛普（gallop）模式」加速。 合并时如果发现某一方的元素连续赢了很多次，就切换到「二分查找批量搬运」的 gallop 模式， 一次搬一大段。

12.7.4 为什么 C 的 qsort 常常比手写快排还慢

这是工程上一个非常经典的现象：同样是自己写的快排，用 std::sort 编译后飞快， 换成 qsort 却慢了好几倍。原因主要有四条，按重要性排序：

1. 函数指针无法内联（最主要原因）。qsort 的签名是 void qsort(void* base, size_t n, size_t size, int (*cmp)(const void*, const void*))。 比较逻辑是通过函数指针传入的。编译器在编译 qsort 时必须假设这个指针随时可能指向任何函数， 因此无法把它内联展开——每一次比较都是一次真实的函数调用： 压栈、跳转、返回、寄存器保存与恢复。而 std::sort 是模板， 比较器作为模板参数传入，编译器可以把 operator< 或 lambda 完全内联， 一次比较可能只编译成一两条指令（比如 cmp %eax, %edx）。这个差距在 n 较大时通常是 2～5 倍。
2. void* 带来的间接访问与无法优化。qsort 只知道元素大小 size， 必须靠 memcpy 式的字节搬移来交换元素，无法像模板那样直接按类型读写， 编译器也没法把这种「运行时才知道大小的内存操作」优化成寄存器操作。
3. 算法本身的差异。很多 qsort 实现是纯快排（部分实现加了小区间插排，但很少加深度兜底）， 遇到偏斜输入会退化到 O(n²)；而 std::sort 是 introsort， 最坏也是 O(n log n)。
4. 缺少针对性的枢轴策略。一些老实现用「取首元素」或「取中间元素」做枢轴， 对已排序输入极不友好；std::sort 用三数取中（部分实现还用 ninther 九数取中）。

下面这段代码把四条原因量化出来：在完全相同的输入上跑 std::sort、qsort、stable_sort 与手写快排， 你就能亲眼看到「函数指针 vs 编译期内联」的差距有多大。

#include <bits/stdc++.h>
using namespace std;
using Clock = chrono::steady_clock;

/* ============================================================
   排序性能对照实验：std::sort vs qsort vs stable_sort vs 手写快排
   竞赛写法：全局数组 + 自由函数，计时用 <chrono> 的 steady_clock
   结论预期：std::sort 通常最快；qsort 因为「函数指针无法内联」而明显偏慢
   （具体倍数与编译器、优化级别、数据类型有关，本程序只做量级演示）
   数组大小依据：N = 3e5，量级差别看得清，跑起来也就一两秒
   ============================================================ */

const int N = 300000;

int baseArr[N];        // 原始随机数据（只读，不参与排序）
int work[N];           // 每次计时前从这里复制一份，保证四种排序面对同一份数据

/* 把 baseArr 复制到 work（复制不计入计时） */
void copyBase() {
    for (int i = 0; i < N; ++i) work[i] = baseArr[i];
}

/* 两个时间点之间隔了多少毫秒 */
double msBetween(Clock::time_point t0, Clock::time_point t1) {
    return chrono::duration<double, milli>(t1 - t0).count();
}

/* ---- qsort 需要的 C 风格比较函数（函数指针 → 无法内联） ---- */
int cmpInt(const void *a, const void *b) {
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);
}

/* ---- 手写朴素快排：取首元素为枢轴。它无法应对已排序输入，
       所以下面用「比较次数计数器」代替跑完全程（否则 n = 20 万要等到天荒地老） ---- */
long long naiveQuickCmps = 0;

void naiveQuick(int lo, int hi, int depthCap) {
    if (lo >= hi) return;
    if (depthCap <= 0) return;                     // 演示用：到了极深就停手，避免爆栈
    int pivot = work[lo], i = lo, j = hi;
    while (i < j) {
        while (i < j) { ++naiveQuickCmps; if (work[j] < pivot) break; --j; }
        work[i] = work[j];
        while (i < j) { ++naiveQuickCmps; if (work[i] > pivot) break; ++i; }
        work[j] = work[i];
    }
    work[i] = pivot;
    naiveQuick(lo, i - 1, depthCap - 1);
    naiveQuick(i + 1, hi, depthCap - 1);
}

int main() {
    mt19937 rng(12345);
    for (int i = 0; i < N; ++i) baseArr[i] = (int)(rng() % 1000000);

    /* 四种方式：注意都在同一份随机数据上比较 */
    copyBase();
    Clock::time_point t0 = Clock::now();
    sort(work, work + N);                                  // ① std::sort（内省排序）
    Clock::time_point t1 = Clock::now();

    copyBase();
    Clock::time_point t2 = Clock::now();
    qsort(work, N, sizeof(int), cmpInt);                   // ② C 的 qsort：比较器是函数指针
    Clock::time_point t3 = Clock::now();

    copyBase();
    Clock::time_point t4 = Clock::now();
    stable_sort(work, work + N);                           // ③ std::stable_sort：稳定但有额外空间
    Clock::time_point t5 = Clock::now();

    copyBase();
    Clock::time_point t6 = Clock::now();
    naiveQuick(0, N - 1, 200);                             // ④ 手写朴素快排
    Clock::time_point t7 = Clock::now();

    double tStd = msBetween(t0, t1), tQs = msBetween(t2, t3);
    double tSt = msBetween(t4, t5), tNv = msBetween(t6, t7);

    printf("n = %d，随机数据（单位 ms，越小越好）\n", N);
    printf("  std::sort        : %.1f\n", tStd);
    printf("  qsort            : %.1f   （约为 std::sort 的 %.1f 倍）\n",
           tQs, tStd > 0 ? tQs / tStd : 0.0);
    printf("  std::stable_sort : %.1f   （稳定，代价是额外空间与常数）\n", tSt);
    printf("  手写朴素快排     : %.1f   （取首元素为枢轴）\n", tNv);

    /* ---- 最坏输入：已经完全有序。这里不跑朴素快排（那是 O(n^2)），
            而是直接数它的比较次数，用数字说明「退化」有多可怕 ---- */
    const int M = 4096;                            // 只统计规模 M 的比较次数，再外推
    for (int i = 0; i < M; ++i) work[i] = i;
    naiveQuickCmps = 0;
    naiveQuick(0, M - 1, M + 10);
    printf("\n已排序输入上「取首元素为枢轴」的朴素快排（n = %d）：\n", M);
    printf("  比较次数 = %lld，而 n(n-1)/2 = %lld  → 完全退化为 O(n^2)\n",
           naiveQuickCmps, (long long)M * (M - 1) / 2);

    for (int i = 0; i < N; ++i) work[i] = i;       // n = 3e5 的已排序输入
    Clock::time_point t8 = Clock::now();
    sort(work, work + N);
    Clock::time_point t9 = Clock::now();
    printf("  而 std::sort（内省排序）在 n = %d 的已排序输入上只用 %.1f ms —— 三数取中 + 堆排兜底让它不退化\n",
           N, msBetween(t8, t9));
    printf("  结论：这就是内省排序存在的意义。\n");
    return 0;
}

12.8 比较排序的下界：为什么至少需要 Ω(n log n)

这是本章、也常常是整个《数据结构》课程里最漂亮的一个证明。 它回答的问题看起来简单得可疑：「排序 n 个数，最少要比较多少次？」 而这个问题的答案，解释了为什么我们折腾了这么多算法，却始终跳不出 O(n log n) （除非放弃比较）。

12.8.1 决策树模型：把任何比较排序画成一棵树

先明确我们要证明的对象：比较排序（comparison sort）—— 指的是「算法在运行过程中，获取信息的唯一手段是比较两个元素的大小」。 它不允许读取元素的值本身（比如不能把元素当下标用），也不允许做哈希。 冒泡、插入、选择、希尔、堆、归并、快排都属于这一类。

现在关键的一步抽象：把算法的全部执行过程画成一棵二叉树。规则是：

• 树中的每一个内部结点代表算法做的一次比较，比如「a < b ?」。
• 这个结点有两个孩子，分别对应这次比较的两种可能结果（真 / 假，即 < 或 ≥）。
• 算法沿着「实际出现的那个结果」对应的分支继续往下走。
• 当算法确定了一个输出（即确定了一个排列）时，就到达一个叶子。 每个叶子上标注这次执行所输出的那个排列。

这棵树就叫决策树（decision tree）。它有两个必须记住的性质：

12.8.2 叶子数必须 ≥ n!：6 个排列一个都不能少

现在的推理链条只有三步，每一步都极其自然：

1. n 个元素一共有 n! 种不同的排列（输入）。 比如 3 个元素有 3! = 6 种排列：abc, acb, bac, bca, cab, cba。
2. 排序算法必须能正确处理每一种输入。不同输入的正确输出是不同的： 输入 abc 应该输出 abc，输入 cba 应该输出 abc （注意——排序的输出是值的有序序列，但我们关心的是「哪个原始元素去了哪个位置」这个排列）。 因此算法至少需要 n! 种不同的「执行路径」来区分这 n! 种输入。
3. 一棵高度为 h 的二叉树最多有 2^h 个叶子。（这是二叉树的基本性质： 第 k 层最多 2^k 个结点，所以叶子数 ≤ 2^h。）

把三步串起来：既然算法必须能区分 n! 种输入，就必须有至少 n! 个叶子； 而高度 h 的二叉树最多只有 2^h 个叶子，于是：

如果叶子数不够会怎样？那就意味着有两种不同的输入走到同一个叶子、得到同一个输出—— 而这两种输入的正确输出不同，所以算法必然在其中一种上给出错误答案。 这就是「叶子不够就一定有解被漏掉」的严格含义。

12.8.3 3 元素决策树：最少 3 次比较

拿最小的情况亲手验证一下。3 个元素 a, b, c 共有 3! = 6 种排列。 如果要证明「2 次比较够不够」，只需看：h = 2 的二叉树最多 2² = 4 个叶子，而我们需要 6 个——装不下。 所以 2 次比较必然不够，至少需要 3 次（2² = 4 < 6 ≤ 8 = 2³）。 下面这棵树同时也构造性地证明了 3 次就够了（所以 3 是最优的）。

下面这个动画从叶子往根逐步搭出这棵树，并走一条具体路径（输入 a=2, b=1, c=3）：

12.8.4 用 Stirling 公式与积分放缩证明 log₂(n!) = Ω(n log n)

从 2^h ≥ n! 出发，两边取以 2 为底的对数（对数是单调递增的，不等号方向不变）：

证法一：积分放缩（最适合手写答卷）

log₂ x 是单调递增函数，因此对每个 i ≥ 1 有 log₂ i ≥ ∫_{i−1}^{i} log₂ x dx（在 [i−1, i] 上，被积函数处处 ≤ log₂ i）。 把 i = 1..n 加起来：

当 n ≥ 4 时 n log₂ n − 1.4427n ≥ (1/2)·n log₂ n （因为此时 log₂ n ≥ 2.885）。所以

证法二：Stirling 公式（结论更精确）

Stirling 公式给出 n! ~ √(2πn) · (n/e)^n，即 n! = √(2πn)·(n/e)^n·(1 + O(1/n))。两边取以 2 为底的对数：

由于 log₂ e ≈ 1.4427 是常数，主项就是 n log₂ n，所以 log₂(n!) = n log₂ n − Θ(n) = Θ(n log n)。于是：

12.8.5 平均情况的下界与信息论表述

上面的结论是最坏情况的。平均情况的下界同样成立，而且更强： 对决策树中所有叶子的深度按「每种输入等概率（各 1/n!）」求平均，得到平均比较次数。 可以证明（用「给定叶子数时，二叉树的外部路径长度最小值在完全平衡时取到」这一事实）：

也就是说，即使按平均情况算，比较排序也至少需要 Ω(n log n) 次比较。 这一点很多人会记错（以为「平均下界比最坏下界松」）——实际上二者同阶： 因为决策树的叶子数就固定是 n!，一棵有 n! 个叶子的二叉树， 其平均深度必然至少是 log₂(n!)（平衡时最小）。

信息论的一般表述：把这个证明抽象出来，就是信息论里的一个标准论证：

这个「信息论下界」的框架可以套用到很多问题上，是一把万能钥匙： 只要你能数出「可能的答案有多少种（N）」和「一次操作最多能提供多少信息（k）」， 就能立刻给出 Ω(log_k N) 的下界。例如：

12.8.6 为什么基数排序、计数排序能突破这个下界

这是整个下界理论里最常考的辨析点，一定要能脱口而出。

把三种算法放在决策树模型下对照，就能看清本质差别：

12.9 稳定性的深入剖析

12.9.1 形式化定义

「稳定」这个说法很口语化，先把它定义清楚：

为什么会有「相等元素」这个概念？因为在真实数据里，元素很少只有一个字段。 一个学生记录有姓名、学号、分数；一次交易有金额、时间、流水号。 排序时我们指定的主关键字（比如分数）往往有重复值， 而重复值之间其实是有区别的——它们的区别就是「原来谁在前」。 稳定性要保住的正是这个区别。

12.9.2 什么场景下「必须」稳定

12.9.3 用多关键字排序证明「稳定」的价值

下面这个命题值得完整写一遍，因为它同时说明了两件事：稳定性是什么、 以及「先次后主 + 稳定排序」为什么等价于「按组合关键字排序」。

12.9.4 19 种排序的稳定性逐个分析与反例

背结论容易忘，看懂反例才记得牢。下面这张表给出每个不稳定排序的具体反例数据。 记号约定：5a 表示「值为 5、且在原序列中排在 5b 前面」的元素。

12.9.5 如何把不稳定排序改成稳定

有三种实用手段，按推荐程度排序：

1. 加「原始下标」作为次关键字（最实用）。 给每个元素附带它在原数组中的下标 idx，比较规则改成： 主关键字不等时比主关键字，相等时比 idx（小的在前）。 这样一来所有元素的比较结果都不相等（idx 唯一）， 排序结果被唯一确定，而「idx 小者在前」正好就是稳定性的要求。
   代价：每个元素多一个字段，比较多一次分支。用 std::sort + 这个技巧， 通常比直接换 std::stable_sort 更快。
2. 换一个稳定的算法。需要稳定又要 O(n log n)，就用归并排序 （std::stable_sort、Timsort 都是这个路线）。 如果数据基本有序、规模不大，直接用插入排序或冒泡也行。
3. 把排序过程「捆绑」成整体。把 (key, 原始序号) 打包成一个复合关键字， 整体参与比较与移动。这与第 1 种本质相同，只是实现上更彻底（比如包装成 struct 或 pair）。

12.10 综合对比、选型决策与外部排序

12.10.1 排序算法综合大对比表

这张表是本讲的核心产出，把 22 种排序放在同一组维度下横向比较。 建议对照图 12-1 的五大体系一起看：同一族的算法，在「稳定性」「是否原地」上往往有一致的规律。

说明：比较? 列表示「是否属于比较排序」；原地? 列表示「空间是否为 O(1)」（或仅递归栈）。 「移动次数」在部分教材里按「元素赋值」计，在部分教材里按「交换」计，比较不同教材数据时要注意口径。

12.10.2 排序算法选择的决策流程

面试和实际开发里，比「背复杂度」更重要的是「拿到问题能立刻定位到该用哪个」。 下面这张流程图给出了一条最常用的决策路径： 数据量 → 是否要求稳定 → 数据分布 → 是否要求最坏保证 → 选定算法。

12.10.3 外部排序专节：内存装不下的数据怎么排

一句话本质：外部排序的瓶颈不是 CPU 而是磁盘 I/O， 所以它的全部设计目标都是「让读写磁盘的次数尽量少」。

设文件有 n 条记录，内存一次只能装 m 条。经典的两阶段方案是：

1. 阶段一：生成初始归并段。把文件分成 n/m 块，每块读进内存排序后写回磁盘， 得到 ⌈n/m⌉ 个有序的「归并段（run）」。
2. 阶段二：多趟 k 路归并。每次把 k 个归并段合并成一个更长的归并段， 反复进行直到只剩一个。归并时用败者树从 k 个段的首元素里 O(log k) 取最小。

为什么用 k 路而不是 2 路？设初始归并段有 m 个，则归并趟数是 S = ⌈log_k m⌉；每趟要把 n 条记录完整读一遍、写一遍， 所以总 I/O 量 = 2n·⌈log_k m⌉。k 出现在底数上，所以增大 k 能显著减少趟数。

置换选择为什么能生成长度约 2 倍内存的归并段

这是外部排序里最有趣的一个结论，很多人第一次看会觉得很神奇。 置换选择（replacement selection）的过程是：

1. 先把 m 条记录读进内存，建成一个最小堆（m 为内存能容纳的记录数）。
2. 输出堆顶的最小值 x（写到当前归并段），然后从磁盘读入下一条记录 y。
3. 比较 y 与刚输出的 x：
   • 若 y ≥ x：y 可以排在 x 后面，属于当前归并段，把它放进堆的根位置并向下筛选。
   • 若 y < x：y 比 x 小，不可能出现在当前归并段里（当前段是递增输出的）， 把它暂存到内存的「待用区」，本轮不参与输出。堆的有效大小减 1。
4. 当堆中「有效元素」全部输出完，当前归并段结束。把待用区的记录重新建堆，开始下一个归并段。

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

/* ============================================================
   置换选择（replacement selection）—— 外部排序生成初始归并段的算法
   · 内存里维护一个大小为 m 的最小堆
   · 输出堆顶最小值 x，同时读入下一条记录 y：
        y >= x  → y 属于当前归并段，插入堆
        y <  x  → y 放进「待用区」，本轮不输出
   · 堆中有效元素耗尽 → 当前段结束，把待用区重新建堆，开新段
   · 平均段长约 2m（随机数据），最坏退化为 m
   本程序用内存数组模拟磁盘文件，用来统计平均段长。
   ============================================================ */
struct RunInfo { vector<int> data; };

vector<RunInfo> replacementSelection(const vector<int>& file, int m, long long& reads) {
    vector<RunInfo> runs;
    int n = file.size();
    int next = 0;                                  // 下一条待读入记录在文件中的下标
    reads = 0;

    /* 初始：读入 m 条记录建最小堆 */
    vector<int> heap;
    for (int i = 0; i < m && next < n; ++i, ++next) { heap.push_back(file[next]); ++reads; }
    make_heap(heap.begin(), heap.end(), greater<int>());

    vector<int> frozen;                            // 待用区（属于下一个归并段）
    while (!heap.empty()) {
        RunInfo cur;
        while (!heap.empty()) {
            pop_heap(heap.begin(), heap.end(), greater<int>());
            int x = heap.back();
            heap.pop_back();
            cur.data.push_back(x);                 // 输出 x 到当前归并段

            if (next < n) {
                int y = file[next++];
                ++reads;
                if (y >= x) {
                    heap.push_back(y);             // 可以接在当前段后面 → 回到堆里
                    push_heap(heap.begin(), heap.end(), greater<int>());
                } else {
                    frozen.push_back(y);           // 比 x 小 → 只能等下一段
                }
            }
        }
        runs.push_back(cur);
        /* 当前段结束：把待用区重新建堆，开始下一段 */
        heap.swap(frozen);
        frozen.clear();
        make_heap(heap.begin(), heap.end(), greater<int>());
    }
    return runs;
}

/* 对照：直接分块 + 块内排序（段长固定为 m） */
vector<RunInfo> plainChunks(const vector<int>& file, int m) {
    vector<RunInfo> runs;
    for (int i = 0; i < (int)file.size(); i += m) {
        RunInfo r;
        int e = min((int)file.size(), i + m);
        r.data.assign(file.begin() + i, file.begin() + e);
        sort(r.data.begin(), r.data.end());
        runs.push_back(r);
    }
    return runs;
}

int main() {
    const int N = 1000, M = 50;                    // 1000 条记录，内存只能装 50 条
    vector<int> file(N);
    mt19937 rng(2024);
    for (int i = 0; i < N; ++i) file[i] = (int)(rng() % 100000);

    long long reads = 0;
    vector<RunInfo> r1 = replacementSelection(file, M, reads);
    int total = 0, minLen = N, maxLen = 0;
    for (auto& r : r1) {
        total += r.data.size();
        minLen = min(minLen, (int)r.data.size());
        maxLen = max(maxLen, (int)r.data.size());
        /* 顺便验证：每个归并段内部必须是有序的 */
        if (!is_sorted(r.data.begin(), r.data.end())) { cout << "错误：段内无序！\n"; return 1; }
    }
    cout << "置换选择：段数 = " << r1.size() << "，平均段长 = "
         << (double)total / r1.size() << "（最短 " << minLen << "，最长 " << maxLen << "）\n";
    cout << "理论预期：平均约 2m = " << 2 * M << "，段数约 n/(2m) = " << N / (2 * M) << "\n";

    vector<RunInfo> r2 = plainChunks(file, M);
    cout << "直接分块：段数 = " << r2.size() << "，平均段长 = " << M
         << "（固定）\n";
    cout << "→ 置换选择把段数从 " << r2.size() << " 降到 " << r1.size()
         << "，归并趟数随之减少，I/O 更省。\n";

    /* 最坏情况：逆序文件 */
    vector<int> desc(N);
    for (int i = 0; i < N; ++i) desc[i] = N - i;
    long long rd2 = 0;
    vector<RunInfo> r3 = replacementSelection(desc, M, rd2);
    cout << "逆序文件时：段数 = " << r3.size() << "，平均段长 = "
         << (double)N / r3.size() << "（退化为 m = " << M << "，不会更差）\n";
    return 0;
}

最佳归并树：用赫夫曼思想安排归并顺序

当归并段的长度不相等时（置换选择产生的段长通常不一样）， 「先合并哪几个段」会影响总 I/O 量。这时候可以借用赫夫曼树（Huffman tree）的思想来安排。

设各归并段长度为 L₁, L₂, …, L_m，每次归并都要把这些记录读一遍写一遍， 所以总代价 ≈ 2 × Σ (Lᵢ × 该段参与的归并次数)。 这正好就是赫夫曼树里的「带权外部路径长度」：把段长当权值，构造赫夫曼树， 权值小的段先合并（路径长）、权值大的段后合并（路径短），总代价最小。

12.11 工程视角：真实系统里的排序工程

12.7 节回答了「标准库用什么算法」，12.6 与 12.10.3 节回答了「内存装不下怎么排」，12.9 节讲透了稳定性。 但生产系统里的排序还有一批 12.7 没覆盖的问题：真实数据不是随机数据、有 64 个核却只快 4 倍、 一次不稳定排序会让分页出现重复行与丢失行。本节专补这些空白，最后给出一个反直觉的结论—— 最好的排序优化，往往是根本不排序。

12.11.1 真实数据不是随机的：run 与归并栈的完整机制

12.7.3 节点明了 Timsort 的三个关键词（run、插排扩展 minrun、归并合并）。这里补上「为什么」， 因为每个词背后都藏着一个工程决策。

为什么先找 run，而不是直接分治？因为快排、归并这类分治算法对任何输入都做 O(n log n) 次比较，它们看不见输入里已经存在的秩序。 而真实数据几乎总带着秩序：按时间生成的日志、按自增 ID 写入的表、两个已排序数据源的拼接。 Timsort 先把这些天然有序的连续片段原样识别出来，复杂度于是降到 n·log(run 数)。

为什么降序必须写成「严格」递减？升序侧用非降序（a[i+1] >= a[i]）， 降序侧用严格递减（a[i+1] < a[i]）。若降序侧也允许相等，形如 [5, 5, 5] 的片段会被判成降序 run，反转后三个 5 的次序就颠倒了——稳定性当场丢失。 这与 12.9.4 节「跨越式交换必不稳定」是同一件事的两面。 minrun 则取 32～64：太小则 run 数暴涨，太大则插排的 O(k²) 抬头。

最关键的一点：run 不是随便合的，而是压进一个归并栈按不变量合。 这个栈就是第 03 讲讲的栈：每发现一个 run 就压栈，再检查栈顶三个 run 的长度 X, Y, Z（Z 最新）是否满足 Z > Y + X 且 Y > X； 违反就把 Y 与「X、Z 中较短的那个」合并——各 run 长度于是像斐波那契 一样增长，栈深只有 O(log n)。

下面这份代码可直接编译运行，把三件事（run 发现、插排补齐 minrun、归并栈合并）都写全了， 并在四种形态的 100 万条数据上与 std::sort 正面对比。

下面这份代码是一个可以直接编译运行的简化版 Timsort， 把上面讲的三件事（run 发现、插排补齐 minrun、归并栈合并）都写全了， 并在四种不同形态的 100 万条数据上与 std::sort 正面对比。 注意它不是标准库的 Timsort——真实的 Timsort 还额外做了 gallop 模式、 临时缓冲区复用等大量优化，但结构上与这份代码完全一致。

#include <bits/stdc++.h>
using namespace std;

/* ============================================================
   简化版 Timsort：run 发现 + 插入排序扩展 + 归并栈
   ① 扫描天然升序 run；严格降序的 run 就地反转成升序；
   ② 长度不足 minRun 的 run，用二分插入排序补齐；
   ③ 用归并栈按两条不变量合并相邻 run，最后收尾合并。
   最坏 O(n log n)（run 长 >= 16，run 数 <= n/16），最好 O(n)，空间 O(n)。
   数组依据：MAXN = 1000005，够放 100 万个元素。
   ============================================================ */

const int MAXN = 1000005;
const int STACK_MAX = 128;      /* 归并栈容量：n <= 1e6 时实际远用不到 40 */

int a[MAXN];                    /* 待排序数组 */
int src[MAXN];                  /* 原始数据副本，供两种排序各跑一遍 */
int buf[MAXN];                  /* 归并缓冲区 */

int runStart[STACK_MAX];        /* 归并栈：各 run 的起点 */
int runLen[STACK_MAX];          /* 归并栈：各 run 的长度 */
int runTop = 0;                 /* 栈中 run 的个数 */
int minRun = 16;                /* 最小 run 长度 */
int runCut = 0;                 /* 统计：本次切出的 run 总数 */

/* ---------- 二分插入：把 a[hi] 插进已有序的 a[lo, hi) ---------- */
void insertOne(int lo, int hi) {
    int key = a[hi];
    int l = lo, r = hi;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] <= key) l = mid + 1; else r = mid;
    }
    for (int i = hi; i > l; --i) a[i] = a[i - 1];
    a[l] = key;
}

/* ---------- ① run 发现：返回从 pos 起的 run 长度 ---------- */
int countRun(int pos, int n) {
    if (pos + 1 >= n) return 1;
    int hi = pos + 1;
    if (a[hi] < a[pos]) {                          /* 严格降序：反转为升序 */
        while (hi + 1 < n && a[hi + 1] < a[hi]) ++hi;
        reverse(a + pos, a + hi + 1);
    } else {                                       /* 非降序：一路吃到底 */
        while (hi + 1 < n && a[hi + 1] >= a[hi]) ++hi;
    }
    return hi - pos + 1;
}

/* ---------- ② 不足 minRun 的 run 用插入排序补齐 ---------- */
int nextRun(int pos, int n) {
    int len = countRun(pos, n);
    int want = minRun;
    if (want > n - pos) want = n - pos;
    if (len < want) {
        for (int i = pos + len; i < pos + want; ++i) insertOne(pos, i);
        len = want;
    }
    return len;
}

/* ---------- ③ 归并 [lo, mid) 与 [mid, hi)：只搬较短的一侧，搬运量减半 ---------- */
void mergeRuns(int lo, int mid, int hi) {
    if (a[mid - 1] <= a[mid]) return;              /* 天然接得上就整段跳过 */
    int n1 = mid - lo, n2 = hi - mid;
    if (n1 <= n2) {
        for (int i = 0; i < n1; ++i) buf[i] = a[lo + i];
        int i = 0, j = mid, k = lo;
        while (i < n1 && j < hi) {
            if (a[j] < buf[i]) a[k++] = a[j++];    /* 相等取左段，保证稳定 */
            else               a[k++] = buf[i++];
        }
        while (i < n1) a[k++] = buf[i++];
    } else {
        for (int i = 0; i < n2; ++i) buf[i] = a[mid + i];
        int i = mid - 1, j = n2 - 1, k = hi - 1;
        while (i >= lo && j >= 0) {
            if (buf[j] < a[i]) a[k--] = a[i--];    /* 从后往前填，同样保持稳定 */
            else               a[k--] = buf[j--];
        }
        while (j >= 0) a[k--] = buf[j--];
    }
}

/* ---------- 合并栈中第 i 与第 i+1 个 run ---------- */
void mergeAt(int i) {
    int lo = runStart[i], mid = lo + runLen[i];
    int hi = runStart[i + 1] + runLen[i + 1];
    mergeRuns(lo, mid, hi);
    runStart[i] = lo;
    runLen[i]   = hi - lo;
    for (int k = i + 1; k + 1 < runTop; ++k) {     /* 后面的 run 整体前移一格 */
        runStart[k] = runStart[k + 1];
        runLen[k]   = runLen[k + 1];
    }
    --runTop;
}

/* ---------- 归并栈的两条不变量（Timsort 原版规则）----------
   栈自底向上记作 ... X, Y, Z（Z 是栈顶）：① Z > Y + X  ② Y > X
   违反①合并 Y 与「X、Z 中较短的那个」，违反②合并 X 与 Y。
   各 run 长度于是像斐波那契一样增长，栈深只有 O(log n)。 */
void mergeCollapse() {
    while (runTop > 1) {
        int n = runTop - 2;
        if ((n > 0 && runLen[n - 1] <= runLen[n] + runLen[n + 1]) ||
            (n > 1 && runLen[n - 2] <= runLen[n] + runLen[n - 1])) {
            if (runLen[n - 1] < runLen[n + 1]) --n;
            mergeAt(n);
        } else if (runLen[n] <= runLen[n + 1]) {
            mergeAt(n);
        } else break;
    }
}

/* ---------- 主过程 ---------- */
void timSort(int n) {
    if (n < 2) return;
    int x = n, r = 0;                              /* minRun 取 n 的高位，落在 [16, 64] */
    while (x >= 64) { r |= (x & 1); x >>= 1; }
    minRun = x + r;
    if (minRun < 16) minRun = 16;

    runTop = 0; runCut = 0;
    int pos = 0;
    while (pos < n) {
        int len = nextRun(pos, n);
        runStart[runTop] = pos;
        runLen[runTop]   = len;
        ++runTop; ++runCut;
        pos += len;
        mergeCollapse();
    }
    while (runTop > 1) mergeAt(runTop - 2);        /* 收尾：把栈里剩下的全部合并 */
}

/* ============================================================
   数据生成、计时与对照实验
   ============================================================ */
unsigned long long seed = 88172645463325252ULL;
int rnd() {
    seed ^= seed << 13; seed ^= seed >> 7; seed ^= seed << 17;
    return (int)(seed >> 33);
}
double nowMs() {
    return (double)chrono::duration_cast<chrono::microseconds>(
               chrono::steady_clock::now().time_since_epoch()).count() / 1000.0;
}
void copyArr(int* dst, const int* s, int n) { for (int i = 0; i < n; ++i) dst[i] = s[i]; }

void genRandom(int n) { for (int i = 0; i < n; ++i) src[i] = rnd(); }
void genSorted(int n) { for (int i = 0; i < n; ++i) src[i] = i; }

/* 基本有序：整体升序，只有约 0.2% 的元素被随机交换过 */
void genNearlySorted(int n) {
    for (int i = 0; i < n; ++i) src[i] = i;
    int swaps = n / 500;
    for (int t = 0; t < swaps; ++t) {
        int i = rnd() % n, j = rnd() % n;
        int tmp = src[i]; src[i] = src[j]; src[j] = tmp;
    }
}

/* 分段有序：seg 段内部升序、段间随机 */
void genSegments(int n, int seg) {
    int len = n / seg;
    for (int s = 0; s < seg; ++s) {
        for (int i = 0; i < len; ++i) src[s * len + i] = rnd();
        sort(src + s * len, src + s * len + len);
    }
    for (int i = seg * len; i < n; ++i) src[i] = rnd();
}

/* 两段有序拼接：两个各自有序的数据源首尾相接 */
void genTwoRuns(int n) {
    int half = n / 2;
    for (int i = 0; i < half; ++i) src[i] = i * 2;
    for (int i = 0; i < n - half; ++i) src[half + i] = i * 2 + 1;
}

void report(const char* name, int n) {
    copyArr(a, src, n);
    double t0 = nowMs();
    timSort(n);
    double t1 = nowMs();
    int runs = runCut, mr = minRun;
    bool ok = true;
    for (int i = 1; i < n; ++i) if (a[i - 1] > a[i]) ok = false;

    copyArr(a, src, n);
    double t2 = nowMs();
    sort(a, a + n);
    double t3 = nowMs();

    printf("%s：简化 Timsort %8.2f ms | std::sort %8.2f ms | 切出 run %7d 个 | 平均 run 长 %8.1f | minRun %2d | %s\n",
           name, t1 - t0, t3 - t2, runs, (double)n / runs, mr, ok ? "有序 OK" : "排序错误");
}

int main() {
    int n = 1000000;
    printf("=== 简化版 Timsort 与 std::sort 对照（n = %d，单位 ms）===\n", n);

    genRandom(n);        report("完全随机", n);
    genTwoRuns(n);       report("两段拼接", n);
    genSegments(n, 256); report("分段有序", n);
    genNearlySorted(n);  report("基本有序", n);
    genSorted(n);        report("完全有序", n);
    return 0;
}

实测（同一台机器，多轮取量级）：完全随机时切出 16130 个 run、平均 run 长仅 62， 简化版 Timsort 约 78 ms 对 std::sort 约 50 ms，反而慢约 1.5 倍； 两段有序拼接只有 2 个 run，约 1.4 ms 对 31 ms，快 20 倍以上； 完全有序只有 1 个 run，约 0.8 ms 对 5.2 ms。结论很干脆： Timsort 的优势完全来自「输入里有多少现成的秩序」。顺带注意 std::sort 排已有序数据只要随机数据的十分之一时间——它已经在检测输入模式。

12.11.2 三段式设计的细节：内省排序为什么取 2⌊log₂ n⌋ 和 16

12.7.1 节已把内省排序（introsort）的三段结构讲透，这里只补三个「为什么恰好是这个数」， 因为工程实现里的魔数从来不是随手写的。

深度上限为什么是 2⌊log₂ n⌋ 而不是 ⌊log₂ n⌋？ 因为「深度 ≤ log₂ n」只在每次划分都恰好对半时才成立；真实快排即使枢轴选得不错， 划分比例也常在 1:3 与 3:1 之间摆动，实际深度会明显大于 log₂ n。留一倍的含义是： 只要平均划分不劣于约 1:3，就永远不会触发堆排；一旦超过一倍，几乎只可能是遭遇了 刻意构造的对抗输入。取 2 倍就是「宁可偶尔多做一次不必要的堆排，也绝不让最坏滑向 O(n²)」。

内省排序真正的遗产不是算法，而是范式：把一个「平均快但最坏会崩」的算法、一个 「最坏有保证但平均慢」的算法、外加一个「小规模无敌」的算法拼起来，让它们各在自己最擅长的区间出场。 这个「混合算法」范式后来被复制到字符串匹配、正则引擎、凸包等几乎所有性能敏感领域。 它留下的洞也很清楚——只看递归深度，不看输入是否已经有序，这正是 pdqsort 要补的那一刀。

小区间阈值为什么是 16？因为 缓存行是 64 字节，正好装 16 个 int； 而插排的 O(k²) 与快排递归的固定开销恰好在 k ≈ 8~32 之间交叉， 这段区间实测总时间几乎持平，16 只是「曲线平缓区间里最好记的那个数」。

12.11.3 pdqsort 与 BlockQuicksort：跟分支预测较劲

先看一个反直觉的事实：现代快排的主要开销不是「比较次数」，而是「分支预测失败」。 现代 CPU 流水线有十几到二十级，一次预测失败要清空整条流水线，代价约 15～20 个时钟周期， 而一次比较本身只要 1 个周期。快排内层是两个各带「跳不跳出去」分支的 while （while (a[++i] < pivot) {}），在随机数据上分支结果几乎无法预测， 于是分支代价能超过比较代价一个数量级——这就解释了为什么「比较次数相同」的两个快排， 实测速度能差一倍。

无分支划分（branchless partition）怎么把分支去掉？ BlockQuicksort（Edelkamp 与 Weiß，2016）把数组切成若干「块」（典型 64 个元素）， 先成批算出每块里「哪些位置该往左、哪些该往右」，写成两个小缓冲区里的下标偏移， 再按这两串偏移做交换。关键在于交换循环里「下一个待交换位置」是从缓冲区读出来的， 没有依赖数据的分支，CPU 能靠条件传送（cmov）与乱序执行满速跑下去。

pdqsort = 内省排序 + 四把补刀。它全名 pattern-defeating quicksort，「战胜模式」指的就是专治让快排难堪的输入：

1. 检测「已有序 / 逆序」并直接返回或反转。pdqsort 花 O(n) 扫一遍就收工， 而内省排序仍做满 n log n 次比较。这也是 第 11 讲快排那一节「已排序输入是最坏情况」的反面。
2. 用 ninther（九数取中）代替三数取中。取样更多，坏枢轴概率更低。
3. 大量重复键时切换成把「等于枢轴」的搬到中间的三路划分。 若键只有 3 种取值，普通二路快排要做 O(n²) 的活，三路划分一次就分完。
4. 深度超限时先「换个随机枢轴再试一次」，还不行才转堆排序， 以免被对抗输入直接骗到常数更大的堆排上。

落地情况：Rust 标准库的 slice::sort_unstable 明确写着自己是 pattern-defeating quicksort； Boost.Sort 直接提供 boost::sort::pdqsort；libstdc++ 的 std::sort 长期是内省排序，近年也已向「检测已有序 + 分块划分」的方向改造——上一小节最后那组数据就是证据。

12.11.4 多键排序的实现路线，与「不稳定」在生产里的真实代价

12.9.2 与 12.9.3 节讲清了「ORDER BY a, b 为什么需要稳定」及其证明。 这里往下走两步：工程上有哪几条实现路线，以及不稳定到底造成什么后果。

量级感受：1000 万行、每行 200 字节（约 2 GB）的数据走路线 B 约需 10⁷ × 24 ≈ 2.4×10⁸ 次比较，还要几百 MB 缓冲；路线 C 只是顺序扫一遍叶子链表。 加一个索引能把几十秒的查询变成几百毫秒，靠的就是把排序整个消灭掉。

不稳定的代价有四类，每一类都在生产里真实发生过：

• 分页错乱。ORDER BY score DESC LIMIT 20 OFFSET 20 在 score 大量并列且排序不稳定时，「哪些同分记录排在第 21~40 名」是未定义的。于是第 2 页会 重复出现第 1 页已展示过的记录，另一些记录永远看不到。
• 测试不稳定（flaky test）。同键记录的顺序取决于物理位置、分区方式、并行度， 于是「本地全过、CI 偶发失败、重跑又过」，失败不可复现。
• 多副本结果不一致。同一份数据在两个副本上分别排序结果就不同，比对工具报出的「差异」 其实数据没错，只是同键顺序不同。
• 让「先次后主」的优化失效。多趟外部排序里任何一趟用了不稳定排序， 前面几趟的成果就全部作废——而且不报错。

三招标准解法，按性价比排序：

1. 给排序键加「兜底唯一列」，把偏序补成全序。最常见的是在末尾追加主键： ORDER BY score DESC, id ASC。因为 id 唯一，比较结果不再相等， 排序结果就唯一确定了——代价只是每个元素多一次比较。
2. 该用稳定排序就明确用。Java 的对象数组 Arrays.sort 用 Timsort、 C++ 用 std::stable_sort、Python 的 sorted 天然稳定。
3. 分页改用游标分页（keyset pagination）。把 OFFSET 20 换成 WHERE (score, id) < (上一页末行的 score, id)。

12.11.5 并行与分布式排序：Amdahl 定律与 MapReduce 的 shuffle

并行排序有一个绕不过去的结构性问题：前半段完美并行，后半段几乎无法并行。 典型做法是「分块各自排 + 归并」：把数组切成 p 块各交给一个核，这一步加速比接近 p； 问题出在归并——2 路并行归并是「两两配对、逐轮减半」，并行度指数衰减， 最后一轮只剩一个线程做 n 次比较。这就是 Amdahl 定律的教科书案例： 若某阶段占总时间比例为 s 且无法并行，则无论加多少核，加速比上限都是 1/s。

核数翻 4 倍、加速比只涨 2.2 倍；若归并阶段完全无法并行（s = 0.4），上限就是 1/0.4 = 2.5 倍，再加核也没用。所以并行排序库都把主要精力花在 让归并阶段也并行上。

样本排序（sample sort）是经典答案：随机抽 p·k 个样本（k 常取 100 以上） 并排序；等间隔取 p−1 个作为分裂点，把值域切成 p 段； 各线程按分裂点把自己的块分到 p 个桶，最后各排各的桶。因为分裂点来自随机样本， 每个桶的大小以极高概率落在 n/p 的常数倍以内，不会出现负载倾斜。

把视野放大到集群：MapReduce 的 shuffle 本质上就是一次分布式归并排序。逐阶段对应：

1. map 端的局部排序。每个 map 把输出 (key, value) 攒在内存缓冲区里，满到某个比例 （Hadoop 默认 80%）就先按 key 排一次序（内部就是快排），再 spill 到本地磁盘； 多个 spill 文件最后被归并成一个「按 key 有序、且已按目标分区切好」的文件。 这就是 12.10.3 节的「生成初始归并段 + 多路归并」，只不过段落落在本地磁盘上。
2. 分区（partition）。按 hash(key) mod R 或按 key 的值域范围把记录分给不同 reduce； 值域分区的边界靠抽样确定——这正是样本排序的思路，目的是让各 reduce 的 key 区间互不重叠。
3. reduce 端的 k 路归并。每个 reduce 从所有 map 节点拉取（shuffle）属于自己的分区文件， 再做 k 路归并，k 等于 map 数、可达几百上千。每一路本身已有序，归并一次即得全局有序流 ——这正是 12.6.3 节败者树存在的理由：k 上千时朴素扫描每次要上千次比较， 而败者树（一棵完全二叉树，见第 07 讲）只要 ⌈log₂k⌉ ≈ 10 次。

代价在哪里？shuffle 的网络传输与磁盘落盘往往占整个作业总时间的一半以上。 所以 Hadoop / Spark 的调优手段——combiner 预聚合、map 端压缩、调大排序缓冲区—— 绝大多数是在减少 shuffle 的数据量或趟数：在分布式系统里，排序算法只是配角，数据搬运才是主角。

12.11.6 外部排序的生产形态：参数到底怎么定

12.6.3 节讲了败者树结构，12.10.3 节讲了置换选择的「平均 2m」结论，这里补最后一个工程问题： 真实排序引擎怎么定 k、怎么定缓冲区、怎么跟硬件打交道。

k 取多少？这是一道「用内存换 I/O」的算术题。归并趟数是 S = ⌈log_k m⌉， k 越大趟数越少，但每一路都要一块读缓冲区，所以 k 的上限是内存除以缓冲区大小。 生产实现里单路缓冲区常取 1～8 MB，于是 1 GB 内存可支撑 k = 128~1000——这解释了为什么 真实外排序的 k 常常是几百而不是教科书里的 2 或 4。

双缓冲与预读：让 CPU 和磁盘都不闲着。CPU 等磁盘说明 I/O 没跑满，磁盘等 CPU 说明 CPU 没跑满。 标准解法是给每一路配两块缓冲区（A/B）：用 A 做归并的同时后台把下一块读进 B。 这就是第 04 讲队列与流水线思想在 I/O 上的复用。

硬件变了，最优参数也跟着变。机械硬盘（HDD）随机访问约 1 ms 一次、顺序吞吐 200 MB/s 量级， 所以「减少趟数、把随机 I/O 变成顺序 I/O」是压倒性目标，k 越大越好。而 NVMe SSD 随机访问只要几十微秒，随机 I/O 已经不贵，瓶颈开始转向 CPU：败者树的每次重赛、 每条记录的比较与搬移都要花时间，于是引擎反而会主动减小 k。 这就是工程视角与理论视角最大的不同。

12.11.7 排序在数据库里的真实地位：ORDER BY 只是冰山一角

换个角度：真正的数据系统里排序出现在哪些地方，以及为什么「省掉一次排序」比 「把排序写得更快」更值钱。

索引本身就是「预先排好的序」。B+ 树的叶子按键值有序排列、叶子间还有链表，所以「按索引键顺序读」 等于「读一份已经排好序的数据」。这是查询优化器最重要的成本项之一：执行计划里出现 Using filesort（MySQL 的说法）就意味着真的要排序了——要分配排序缓冲、要比较， 数据量大了还要落盘做外部排序；而出现 Using index 或「索引有序扫描」则意味着 这次排序被省掉了。

但「走索引省排序」有严格前提，工程上最容易踩三个坑：

• 索引列顺序必须与排序键顺序一致，方向也要能对上。联合索引 (a, b) 能支持 ORDER BY a, b，支持不了 ORDER BY b, a； 而 ORDER BY a DESC, b ASC 这种「混合方向」在只有普通升序索引时也用不上。
• 排序列上套了函数，索引用不上。ORDER BY UPPER(name) 走不了 name 上的索引，这与 WHERE 里「列上套函数导致索引失效」是同一个道理。
• 加索引不是免费的。每个索引都要在每次写入时维护（写放大）、要占空间。 为一个低频查询加索引，可能让高频写入路径整体变慢——这就是「索引是拿写入换读取」。

12.11.8 「不要排序」往往是最好的优化

12.10.2 节的决策流程里有一句「只需要前 k 小：用 nth_element 或堆，别全排序」。 这句话值得单独展开，因为它是排序工程里回报率最高的一条经验：绝大多数真实需求其实 并不需要全序，只需要偏序、极值或去重；而「不需要全序」就意味着可以省掉一大截工作。

手段一：Top-K 用堆。要从 n 条数据里取最大的 k 条：

• 全排序需 O(n log n) 次比较。以 n = 10⁸、k = 100 为例， 约 10⁸ × log₂10⁸ ≈ 2.7×10⁹ 次比较，还必须把全部数据放进内存。
• 大小为 k 的最小堆：扫一遍数据，比堆顶大才替换并下沉，每次下沉 log₂k ≈ 7 次比较。 总数在 10⁸ 量级，比全排序少一个数量级以上；更关键的是只需 O(k) 内存。

但堆不是无条件的赢家：当 k 接近 n 时，堆要做 O(n log n) 次下沉，反而比一次全排序更慢；经验判据是 k 远小于 n / log n 时才用堆。

手段二：第 k 小 / 中位数用快速选择（quickselect）。它就是快排「只递归有答案的那一边」的版本： 一次划分后若枢轴正好落在 k，答案就找到了；否则只在含第 k 小的那一半里继续找。 因为每次丢掉一半，比较次数的期望值是 3.4n 量级——线性，而不是 n log n。 仍以 n = 10⁸ 为例：全排序约 2.7×10⁹ 次比较，快速选择只要 3.4×10⁸ 左右， 大约快 8 倍。C++ 的 std::nth_element 就是它。

代价与陷阱：快速选择的最坏仍是 O(n²)，实用实现必须配随机化枢轴；重复键多时还要三路划分。 若需要「前 k 小且有序」，正确组合是先用快速选择定位、再对小范围排序。

手段三：去重时，排序去重与哈希去重怎么选？这是一个「理论复杂度骗人」的典型例子。

经验法则：数据能全部装进内存、也不需要有序输出时用哈希去重； 反之（要落盘、要有序输出、要防冲突攻击）用排序去重。这里正是 第 10 讲哈希表那一节讲的「用空间换时间」在付账。 而当 n 达到 10⁸ 量级时，哈希去重虽然理论上是线性的， 却常常因为缓存未命中而并不比排序去重快。

12.11.9 工程选型对比表

把本节与 12.7 节讨论过的五种「生产级」排序放在一起比较。注意这张表不是12.10.1 节的 算法复杂度表：它比的是工程维度，而「是否稳定」「能否并行」「对真实数据的适应性」往往比复杂度更决定成败。

12.12 本章小结、易错点与自测题

12.12.1 必须记住的十件事

12.12.2 易错点清单

12.12.3 考点速记（note exam 合集）

12.12.4 自测题（答案折叠）

12.12.5 配套编程练习