外部排序

概念

外部排序（external sorting）指待排序的记录数量太大，内存装不下，排序过程必须分多次把数据在内存与外存之间搬运。

这一换场景，整个优化目标就变了：

	内部排序	外部排序
瓶颈	比较次数（CPU 时间）	I/O 次数（磁盘读写时间）
主战场	算法本身	数据搬运的组织方式

磁盘访问一次的时间是内存访问的几万倍。所以外部排序的所有技巧——多路归并、败者树、置换-选择、最佳归并树——全部围绕"如何减少读写外存的次数"。

一句话记忆：内部排序比"谁比较得快"，外部排序比"谁能少搬几趟"。多路归并减少趟数，败者树让多路归并本身不变得太慢，置换-选择减少归并段个数，最佳归并树让归并顺序最省。

原理

一、外部排序的两个阶段

   阶段一：生成初始归并段（initial run）
        把大文件切成若干块，每块单独调入内存排序后写回外存

   ┌────────── 外存：N 个记录 ──────────┐
   │ 块1 │ 块2 │ 块3 │ ... │ 块 m │
   └──┬───┴──┬──┴──┬──┴─────┴──┬──┘
      ↓      ↓     ↓            ↓
   ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
   │排序后 │ │排序后 │ │排序后 │ │排序后 │      每段长度 = w（内存工作区能装的记录数）
   │ 段1  │ │ 段2  │ │ 段3  │ │ 段 m │
   └──────┘ └──────┘ └──────┘ └──────┘

   阶段二：多路归并（k-way merge）
        每趟把 k 个归并段合并成 1 个，重复到只剩 1 段

设总记录数 $N$，内存工作区可装 $w$ 个记录，则初始归并段个数

$$m=\lceil \frac{N}{w}\rceil$$

二、归并趟数：外部排序的核心公式

k 路归并：每趟把 $k$ 个归并段合并成一个。段数从 $m$ 变到 1 需要的趟数

$$S=\lceil {\log }_{k}m\rceil$$

减少趟数的两条路：增大 $k$（每趟多吃几段）或减少 $m$（把初始归并段做长）。

   m = 8 个归并段的两种做法（每趟读+写全部记录）

   二路归并  k=2：S = ⌈log2 8⌉ = 3 趟
      ○○○○○○○○ → ○○○○ → ○○ → ●         3 趟，每趟 I/O 2N 次
   四路归并  k=4：S = ⌈log4 8⌉ = 2 趟
      ○○○○○○○○ → ○○○○～(合并成2段) → ●    2 趟，少一趟 I/O

总 I/O 次数（以记录为单位，读写各算一次）：

$$\text{总 I/O}=2N\times (S+1)$$

其中"$+1$"是生成初始归并段那一次读写（读入 $N$ 个记录、写出 $N$ 个记录），$S$ 趟归并每趟也是一读一写。

若按"块"计更精确：每趟把全部块读一遍、写一遍，块数 = $\lceil N/\text{块大小}\rceil$。

三、增大 k 的代价与「败者树」

$k$ 路归并时，每输出一个记录都要在 $k$ 个归并段的当前首元素中挑出最小值，朴素做法需要 $k-1$ 次比较。$S$ 趟、每趟 $N$ 个记录，总比较次数

$$(k-1)\cdot N\cdot S=(k-1)\cdot N\cdot \lceil {\log }_{k}m\rceil$$

注意一个矛盾：$k$ 增大时，$\lceil {\log }_{k}m\rceil$ 减小（好），但 $(k-1)$ 增大（坏）。二者相乘后反而随 $k$ 上升！也就是说，单纯增大 $k$ 会让内部比较时间吃掉 I/O 省的收益。

破局办法：败者树（loser tree）。

                 ┌──────────┐
                 │ 全局胜者 │  ← 根的上方记录最终赢家
                 └────┬─────┘
            ┌─────────┴─────────┐
            │  0 号结点（败者）  │
            └───┬───────────┬───┘
         ┌──────┴────┐  ┌───┴──────┐
         │ 2 号结点   │  │ 3 号结点  │
         └─┬──────┬──┘  └─┬──────┬─┘
        ┌──┴─┐  ┌─┴──┐ ┌──┴─┐ ┌──┴─┐
        │段1 │  │段2 │ │段3 │ │段4 │      ← k = 4 个叶子 = 4 个归并段的当前元素
        └────┘  └────┘ └────┘ └────┘

• 结构：$k$ 个叶子（各归并段的当前元素）+ $k-1$ 个内部结点，共 $2k-1$ 个结点。
• 每个内部结点记录的是败者（输的一方），胜者继续往上比——所以叫"败者树"。
• 选出全局最小值后，只有参与的那个叶子发生了变化。重新比赛只需沿该叶子到根的路径重走一遍，比较 $\lceil {\log }_{2}k\rceil$ 次。
• 效果：总比较次数降到 $N\cdot S\cdot \lceil {\log }_{2}k\rceil$，$k$ 增大时增长极缓，I/O 收益可以完整拿到。

记忆点：败者树把"每选一个最小值的 $k-1$ 次比较"变成"$\lceil {\log }_{2}k\rceil$ 次比较"。$\lceil {\log }_{2}k\rceil$ 是路数 $k$ 的完全二叉树高度。

四、置换-选择排序：把初始归并段做长

前面是 $"m=\lceil N/w\rceil "$，段长固定为 $w$。置换-选择排序（replacement selection）用 $w$ 个记录的工作区，把段长做到平均 $2w$。

做法：

1. 从外存顺序读入 $w$ 个记录填满工作区，建成小根堆（或用败者树，$w$ 个叶子）。
2. 输出堆顶（当前最小值）为 $MIN$，写出到当前归并段。
3. 从外存读入下一个记录 $R$ 替换堆顶：
   • 若 $R\ge MIN$：$R$ 可以继续纳入当前归并段，下滤恢复堆序，继续输出；
   • 若 $R<MIN$：$R$ 不能纳入当前段（否则段内失序），把它暂存在堆的"冻结区"，不再参与本轮选取。
4. 当堆中只剩被冻结的元素时，当前归并段结束，把这些冻结元素重新建堆，开始下一段。

   工作区 w = 5，输入流 12 3 8 20 1 15 6 30 ...

   段1：输出 3, 8, 12, 15, ...（只要新读入的 ≥ 刚输出的，就继续排进本段）
        遇到 1 < 15 → 冻结；遇 6 < 15 → 冻结
   段1 结束后，用冻结的 1, 6 重新建堆，开段2

关键结论：对随机输入，初始归并段的平均长度约为 $2w$。段长翻倍 → $m$ 约减半 → 归并趟数少一趟。当输入已经正序时，置换-选择可以一次生成整表有序的归并段（长度 $N$）；当输入逆序时，退化为长度 $w$。

五、最佳归并树：让归并顺序最省 I/O

各初始归并段的长度不相等。归并顺序不同，同一段记录被重复搬运的次数就不同。

把每个归并段看作一个带权叶子（权 = 段长），归并过程构成一棵 k 叉树：

• 叶子 = 归并段，权 = 该段记录数；
• 内部结点 = 一次归并的结果，权 = 参与归并的记录总数；
• 带权路径长度 WPL = 所有记录被搬运的总次数；
• 每搬一次要读 + 写，所以 总 I/O 次数 = 2 × WPL。

要让 WPL 最小 → 这就是哈夫曼树问题，只不过从二叉树变成 k 叉树。

补虚段规则：k 叉哈夫曼树要求叶子数 $m$ 满足

$$(m-1)mod(k-1)=0$$

若不满足，需要补

$$\text{虚段个数}=(k-1)-((m-1)mod(k-1))$$

个长度为 0 的虚段（虚段不实际存在，因而不产生 I/O）。

为什么要补：k 叉树中每个内部结点恰好消耗 $k$ 个孩子，所以"叶子数 − 1"必须是"$k-1$"的倍数。缺的位置用权值为 0 的叶子填上，才能让每层都恰好"凑齐 k 个"。

示例

例 1：归并趟数计算

一个文件有 20000 个记录，内存工作区每次可容纳 1000 个记录。分别用 4 路归并和 8 路归并，需要几趟？各需多少次 I/O（以记录为单位）？

第一步，求初始归并段个数：

$$m=\lceil \frac{N}{w}\rceil =\lceil \frac{20000}{1000}\rceil =20$$

第二步，4 路归并的趟数：

$$S=\lceil {\log }_{4}20\rceil =\lceil 2.16\rceil =3$$

总 I/O：

$$2N\times (S+1)=2\times 20000\times 4=160000\text{次}$$

第三步，8 路归并的趟数：

$$S=\lceil {\log }_{8}20\rceil =\lceil 1.44\rceil =2$$

总 I/O：

$$2N\times (S+1)=2\times 20000\times 3=120000\text{次}$$

结论：$k$ 从 4 增到 8，趟数从 3 降到 2，I/O 减少 25%。但内部比较次数从 $(4-1)\cdot 20\cdot 1000\cdot 3$ 变为 $(8-1)\cdot 20\cdot 1000\cdot 2$，从 18 万涨到 28 万——这正是必须上败者树的原因。

例 2：最佳归并树（不需要补虚段）

有 9 个初始归并段，长度分别为 9, 30, 12, 18, 3, 17, 2, 6, 24。做 3 路归并，求最佳归并树的 WPL 与总 I/O 次数。

第一步，检查是否需要补虚段：

$$(m-1)mod(k-1)=8mod2=0$$

不需要补虚段（这也是这道经典题选 9 个段的原因）。

第二步，按 3 叉哈夫曼逐次合并最小的 3 个：

步骤	取出的 3 个权	合成	剩余权值集合
①	2, 3, 6	11	9, 11, 12, 17, 18, 24, 30
②	9, 11, 12	32	17, 18, 24, 30, 32
③	17, 18, 24	59	30, 32, 59
④	30, 32, 59	121	121（只剩根）

第三步，算 WPL（把每次合并产生的结点权值相加）：

$$WPL=11+32+59+121=223$$

第四步，转换 I/O 次数（读一次 + 写一次）：

$$\text{总 I/O}=2\times WPL=2\times 223=446\text{次}$$

对应的归并树：

                     121
              /        |        \
            30        32        59
                    /  |  \     / | \
                   9  11  12  17 18 24
                     /|\
                    2 3 6

验算 WPL（按层数 × 权值）：

$$30\times 1+(9+12)\times 2+(2+3+6)\times 3+(17+18+24)\times 2=30+42+33+118=223✅$$

例 3：需要补虚段的归并树

8 个初始归并段长度 10, 20, 30, 40, 50, 60, 70, 80，3 路归并，求补虚段个数与总 I/O。

第一步，补虚段：

$$(m-1)mod(k-1)=7mod2=1\ne 0$$$$\text{需补虚段}=(k-1)-1=2-1=1\text{个}$$

虚段长度为 0，加进去后叶子变为 0, 10, 20, 30, 40, 50, 60, 70, 80（9 个）。

第二步，3 叉哈夫曼合并：

步骤	取出的 3 个权	合成	剩余
①	0, 10, 20	30	30, 30, 40, 50, 60, 70, 80
②	30, 30, 40	100	50, 60, 70, 80, 100
③	50, 60, 70	180	80, 100, 180
④	80, 100, 180	360	360

第三步，求 WPL 与 I/O：

$$WPL=30+100+180+360=670$$$$\text{总 I/O}=2\times 670=1340\text{次}$$

注意第一个合成的 30 之所以能等于 30，正是因为那个**虚段（权 0）**参与凑数——它占了一位，但本身不贡献 I/O。

例 4：置换-选择排序的段长

内存工作区能容纳 1000 个记录，输入文件随机（无序）共 100000 个记录。

• 朴素法（每次排 1000 个直接写出）：段长 1000，需 $m=100$ 个初始归并段。
• 置换-选择法：平均段长 $2w=2000$，需 $m\approx \lceil 100000/2000\rceil =50$ 个初始归并段。

段数从 100 降到 50，若用 4 路归并：

方法	m	趟数 $\lceil {\log }_{4}m\rceil$
朴素	100	$\lceil 3.32\rceil =4$
置换-选择	50	$\lceil 2.82\rceil =3$

少一趟归并 = 少两遍全量 I/O。这就是置换-选择排序的价值。

C 语言：k 叉哈夫曼（最佳归并树 WPL 与补虚段）

#include <stdio.h>

/* 计算 k 路最佳归并树的「补虚段数」与 WPL。
   len[] 为各归并段长度，m 为段数，k 为归并路数。
   做法：每次取最小的 k 个合并（朴素实现：排序后取前缀，再插回并保持有序）。 */
void bestMergeTree(int len[], int m, int k) {
    int a[64], n = m;
    for (int i = 0; i < m; i++) a[i] = len[i];

    /* 1. 排序（升序） */
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; }

    /* 2. 补虚段：在头部插入 0，使 (n-1) % (k-1) == 0 */
    int r = (n - 1) % (k - 1);
    int pad = (r == 0) ? 0 : (k - 1 - r);
    for (int i = n - 1; i >= 0; i--) a[i + pad] = a[i];
    for (int i = 0; i < pad; i++) a[i] = 0;
    n += pad;

    printf("补虚段数 = %d, 总叶子数 = %d\n", pad, n);

    /* 3. 反复取前 k 个合并，把结果插回并保持升序 */
    int wpl = 0;
    while (n > 1) {
        int s = 0;
        for (int i = 0; i < k; i++) s += a[i];       /* 取最小 k 个 */
        for (int i = k; i < n; i++) a[i - k] = a[i]; /* 前移 */
        n -= k;
        /* 把 s 插入到有序位置 */
        int p = n; for (int i = 0; i < n; i++) if (s < a[i]) { p = i; break; }
        for (int i = n; i > p; i--) a[i] = a[i - 1];
        a[p] = s; n++;
        wpl += s;
        printf("  合并得 %4d, 当前 WPL 累计 = %d\n", s, wpl);
    }
    printf("最佳归并树 WPL = %d, 总 I/O 次数 = %d\n", wpl, 2 * wpl);
}

int main(void) {
    int seg1[9] = {9, 30, 12, 18, 3, 17, 2, 6, 24};
    printf("=== 例2: 9 段, 3 路 ===\n");
    bestMergeTree(seg1, 9, 3);      /* WPL 223, I/O 446 */

    int seg2[8] = {10, 20, 30, 40, 50, 60, 70, 80};
    printf("\n=== 例3: 8 段, 3 路 ===\n");
    bestMergeTree(seg2, 8, 3);      /* 补 1 虚段, WPL 670, I/O 1340 */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

Python 对照

import heapq, math

def best_merge_tree(lengths, k):
    """返回 (补虚段数, WPL)。heapq 的 nsmallest 直接支持 k 路取最小 k 个。"""
    a = sorted(lengths)
    m = len(a)
    r = (m - 1) % (k - 1)
    pad = 0 if r == 0 else (k - 1 - r)
    h = [0] * pad + a
    heapq.heapify(h)                       # 3 叉哈夫曼用堆最顺手
    wpl = 0
    while len(h) > 1:
        s = sum(heapq.heappop(h) for _ in range(k))
        wpl += s
        heapq.heappush(h, s)
    return pad, wpl

for segs, k in [([9,30,12,18,3,17,2,6,24], 3), ([10,20,30,40,50,60,70,80], 3)]:
    pad, wpl = best_merge_tree(segs, k)
    print(f"{len(segs)} 段 {k} 路 → 补虚段 {pad}, WPL = {wpl}, 总 I/O = {2*wpl}")

# —— 归并趟数 ——
for N, w, k in [(20000, 1000, 4), (20000, 1000, 8), (100000, 1000, 4)]:
    m = math.ceil(N / w)
    S = math.ceil(math.log(m, k))
    print(f"N={N}, w={w} → m={m}; {k} 路归并趟数 S={S}, 总 I/O = {2*N*(S+1)}")

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 必背公式

• 初始归并段个数 $m=\lceil N/w\rceil$（$w$ = 内存工作区可容纳的记录数）
• 归并趟数 $S=\lceil {\log }_{k}m\rceil$
• 总 I/O 次数 $=2N\times (S+1)$（生成初始段 + $S$ 趟归并，每趟一读一写）
• 朴素 k 路归并每输出一个记录的比较次数 $=k-1$；用败者树降到 $\lceil {\log }_{2}k\rceil$
• 置换-选择排序的平均初始归并段长度 = $2w$
• 最佳归并树：总 I/O $=2\times WPL$
• 补虚段个数 $=(k-1)-((m-1)mod(k-1))$，其中 $m$ 为归并段个数

2. 三个「为什么」（简答题常出）

• 为什么外部排序的主要时间是 I/O？ 因为内存与外存的访问速度差几个数量级，比较次数上的优化在 I/O 面前可以忽略，所以一切设计围绕减少磁盘读写趟数。
• 为什么不能无限制增大 k？ 因为朴素 k 路归并每选一个最小值要 $k-1$ 次比较，$(k-1)\lceil {\log }_{k}m\rceil$ 随 $k$ 增大反而上升，内部归并时间会吃掉省下的 I/O。用败者树把每趟的比较降到 $\lceil {\log }_{2}k\rceil$ 次，才能真正享受多路归并的好处。
• 为什么大根堆/小根堆（选择树）在外部排序里也用得上？ 置换-选择排序就是用小根堆（或败者树）在 $w$ 个记录中选择最小值输出，从而生成平均长度 $2w$ 的初始归并段。

3. 易错点

• $\lceil {\log }_{k}m\rceil$ 要用上取整。$m=20$、$k=4$ 时 ${\log }_{4}20=2.16$，趟数是 3 而不是 2。
• 补虚段补的是"长度 0 的段"，不是"把某个段拆开"。而且要补在最前面（权最小处），否则会改变哈夫曼树的形状。
• 补虚段公式中的 $m$ 是"归并段个数"，$k$ 是"归并路数"。$m=8$、$k=2$ 时 $(8-1)mod1=0$，永远不需要补虚段（二路哈夫曼不需要）。
• 置换-选择排序的 2w 是"平均值"，不是"保证值"。输入逆序时每段只有 $w$ 长，输入已正序时可以一次生成 $N$ 长的段。
• 最佳归并树是"读完再写"两遍 I/O，别只算 WPL 就结束，题目问"总读写次数"要 × 2。
• k 路归并的 k 越大越好是错的（见上文计算）；正确说法是"配合败者树时，k 越大趟数越少"。
• 外部排序的"路数"与"内存工作区"要分清：$w$ 决定生成初始归并段时的内存容量；$k$ 路归并则需要 $k$ 个输入缓冲区。若内存里同时只能开 $k$ 个缓冲，$k$ 的上限受内存限制。
• "内外存之间交换数据"总有多次：一次归并趟数都跑不掉，所以减小 $S$ 就是减小 I/O 总量，这是所有技巧的公共判据。

4. 与内部排序的对照

对比项	内部排序	外部排序
数据能否一次装入内存	能	不能
主要开销	比较 / 移动	I/O 次数
核心算法	快排 / 堆排 / 归并	多路平衡归并
关键优化点	枢轴选取、常数因子	增大 k + 败者树、置换-选择、最佳归并树

小结

• 外部排序 = 生成初始归并段 + 多路平衡归并，它的一切设计都是为了减少磁盘读写次数。
• 趟数 $S=\lceil {\log }_{k}m\rceil$：要么增大路数 $k$，要么减少段数 $m$。
• 增大 $k$ 有个陷阱——朴素做法要 $k-1$ 次比较，必须用败者树把每次选择降到 $\lceil {\log }_{2}k\rceil$ 次，多路归并的收益才拿得到。
• 置换-选择排序用小根堆边输出边补入，把初始归并段平均做到 $2w$，直接让 $m$ 减半。
• 最佳归并树把归并顺序化为 k 叉哈夫曼树：$WPL$ 最小则 I/O 最少，总 I/O $=2\times WPL$；叶子数不满足 $(m-1)mod(k-1)=0$ 时要补长度为 0 的虚段。
• 408 的排序部分到此收口。下一站回到整个数据结构的底层——算法复杂度分析，把"O 记号到底怎么算"一次讲透。

下一篇：算法复杂度分析基础