外部排序

2026 大纲 七（十一）外部排序。

瓶颈换了地方，优化目标就整个换了

数据量大到内存一次装不下时，排序必须借用外存分批调入。它与内部排序的根本差别不在数据量，而在瓶颈换了地方：

	内部排序	外部排序
主要开销	关键字比较 + 记录移动	外存的读／写次数
优化目标	减少比较与移动次数	减少归并趟数（从而减少 I/O）
单次操作的代价	纳秒级	毫秒级，比内存操作慢几个数量级

流程分两个阶段：

• 阶段一：分批读入内存 → 内部排序 → 写回，得到 $m$ 个初始归并段（顺串）；
• 阶段二：逐趟 $k$ 路归并，段数 $m\to \lceil m/k\rceil \to \cdots \to 1$。

总时间可拆成三项：

$$T_{\text{外排}}=\underset{\text{生成初始归并段}}{\underbrace{m\times t_{IS}}}+\underset{\text{外存读写}}{\underbrace{d\times t_{IO}}}+\underset{\text{内部归并}}{\underbrace{S\times u\times t_{mg}}}$$

🔴 由于 $t_{IO}$ 远大于 $t_{mg}$，提高外排效率必须主要着眼于减少读写次数 $d$。 而 $d$ 与归并趟数 $S$ 成正比，所以整章的核心公式只有一条：

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

⚠️ $\log$ 里装的是"段数 $m$"，不是记录数 $n$。

先动手看一眼

加载可视化中...

把 I/O 账算清楚

文件含 10 000 条记录，内存一次装 1 000 条，于是通过 10 次内部排序得到 $m=10$ 个初始归并段。设每个物理块容纳 200 条记录，则整个文件占 50 块，每一趟归并都要把全部记录读一遍写一遍，每趟 I/O 固定为 $50+50=100$ 次。

方案	归并趟数 $S$	归并阶段 I/O	加上生成初始段的 100 次	总计
2 路平衡归并	$\lceil {\log }_{2}10\rceil =4$	$4\times 100=400$	$+100$	500 次
5 路平衡归并	$\lceil {\log }_{5}10\rceil =2$	$2\times 100=200$	$+100$	300 次

只是把路数从 2 提到 5，读写次数就少了 40%。这就是"多路归并"的全部动机。

趟数公式的来历：每趟把 $k$ 个段合成 1 个，段数 $m\to \lceil m/k\rceil \to \cdots \to 1$。要让 $m/k^S\le 1$，需 $k^S\ge m$，即 $S=\lceil {\log }_{k}m\rceil$。

由这条公式直接读出三条被真题考过的判断：

命题	真伪	理由
$k$ 越大，归并趟数 $d$ 越小	✅	$k$ 是对数的底数，底数越大值越小
初始归并段数不影响 $d$	❌	$m$ 是对数的真数，$m$ 变了 $d$ 当然变
内存大小限制初始归并段的最大长度	✅	用普通内部排序时段长恰等于工作区容量；即使用置换-选择，段长也受工作区规模制约

减少 $S$ 只有两条路（一条改底数、一条改真数）：

策略	手段	效果	代价
增大归并路数 $k$	多路平衡归并	$S$ 随 $k$ 增大而减小	每次选最小值的比较次数增加；需要更多输入缓冲区
减少初始归并段数 $m$	置换-选择排序	平均段长从 $w$ 提到 $2w$，$m$ 约减半	实现复杂，段长不等（引出最佳归并树）

⚠️ $k$ 并非越大越好：$k$ 增大意味着要同时打开 $k$ 个输入缓冲区，内存被切得更碎，每个缓冲区能装的块数变少，读盘次数可能反升。

增大 $k$ 的新矛盾，与败者树的解法

2 路归并每输出一条记录只需 1 次比较；$k$ 路归并每输出一条要从 $k$ 个段的当前首元素中选最小者，朴素做法需 $k-1$ 次比较。对 $n$ 条记录、$m$ 个初始段，内部归并总比较次数为

$$\lceil {\log }_{k}m\rceil (k-1)(n-1)\cdot t_{mg}=\frac{\lceil {\log }_{2}m\rceil (k-1)}{{\log }_{2}k}(n-1)\cdot t_{mg}$$

关键在 ${\displaystyle \frac{k-1}{{\log }_{2}k}}$ 这一项，它随 $k$ 单调增长：

$k$	2	4	8	16
$(k-1)/{\log }_{2}k$	1	1.5	2.33	3.75

单纯增大 $k$ 虽减少了外存读写时间，却把内部归并时间抬了上去。 要让增大 $k$ 真正划算，必须把"从 $k$ 个中选最小"的代价压下来——这就是败者树：

🔴 败者树把选最小值的比较次数从 $k-1$ 降到 $\lceil {\log }_{2}k\rceil$，使内部归并总时间变成 $\lceil {\log }_{2}m\rceil (n-1)t_{mg}$——这个式子里没有 $k$。

它的价值不是"快一点"，而是让内部归并时间与 $k$ 脱钩，于是增大 $k$ 的收益能完整兑现。

为什么叫"败者"树：内部结点里记的是刚打完这场比赛的败者（较大者），胜者继续往上打。这样设计的好处在调整时才看得出来——

新元素接下来要打的那一场，对手正是"上一次在这个位置输掉的那个人"（上次的胜者已经晋级走了）。败者树把这个对手直接存在双亲里，所以每上一层只访问双亲这一个结点；胜者树还得再去取兄弟结点的值。

⚠️ 还有一个容易答错的实现细节：

🔴 败者树的所有内部结点（包括存放冠军的顶结点）保存的都是"归并段号"，不是关键字本身。 关键字只存在外部结点（叶子）里。

这样设计的理由：冠军段输出一个元素后，要从同一个段补一个新元素进来再调整树；按段号能直接定位回对应的叶子继续操作。所以问"记录冠军的结点保存的是什么"，答的是"最小关键字所在的归并段号"——方向是"最小"（因为归并段升序、要输出最小的才能维持结果升序），存的是"段号"。

置换-选择：让段长突破工作区容量

$S=\lceil {\log }_{k}m\rceil$ 里的 $m=\lceil n/l\rceil$。用普通内部排序生成初始段时 $l$ 恰好等于工作区容量 $w$——因为内部排序必须把整段装进内存才能排。要减小 $m$，就得让 $l>w$。

置换-选择做到了这一点，它的关键在于选择标准：

🔴 每次选"最小的、且不小于上次输出的"那一条，而不是"最小的"。

比上次输出小的记录若进入当前段，会破坏段内有序，只能留给下一段；而比工作区里所有记录都大的新记录照样能进当前段——正是这种机制让段长突破了工作区容量。

数值演示：输入 17, 21, 5, 44, 10, 12, 56, 32, 29，工作区容量 $w=3$：

步	工作区 WA	上次输出（门槛）	选出输出	读入补位
1		$-\mathrm{\infty }$	5	44
2		5	17	10
3		17	21	12
4		21	44	56
5		44	56	32
6		56	全部小于 56，选不出 → 段 1 结束	—
7		$-\mathrm{\infty }$（新段）	10	29
8		10	12	（输入已空）
9		12	29	—
10		29	32	—

得到 段 1 = (5, 17, 21, 44, 56) 长 5、段 2 = (10, 12, 29, 32) 长 4。对照普通方法：9 条记录、工作区 3，每次只能产出长度 3 的段共 3 段；置换-选择只产出 2 段，且段 1 的长度 5 已超过工作区容量。

第 4 步最容易搞错：工作区里明明有更小的 10 和 12，却必须输出 44——标准是"最小的且不小于上次输出的 21"。 第 5 步是"续命"的现场：56 比工作区里原有的所有记录都大，照样能进当前段。

第一个初始归并段的长度能到多少？ 这是真题的一个分问，答案是一个区间：

	长度	取到时的输入
最大值	$n$	输入恰好升序——每次读入的新记录都不小于上次输出，永远不被冻结，全部 $n$ 条都进第一段
最小值	$w$	输入恰好降序——每读一条都比刚输出的小、立即冻结，$w$ 轮后工作区全冻结，第一段就此结束，长度恰为工作区容量

平均长度是 $2w$（Knuth 的结论），介于两者之间。理解了"为什么是 $[w,n]$ 区间"，自然就理解了平均值为什么比 $w$ 大。

扫雪机类比：平均段长为什么恰好是两倍工作区（想弄懂 2w 怎么来的就展开）

一台扫雪机在环形路上匀速扫雪，雪也匀速均匀地落在路面上。经过一段时间后系统达到平衡：路面上的积雪总量不变，且任何时刻积雪形成一个均匀的斜面——紧靠扫雪机前端的积雪最厚（深度 $h$），刚扫过的路面积雪为零。

设此刻路面积雪总体积为 $w$、环形路一圈长为 $l$。扫雪机任何时刻扫走的雪深都是 $h$，走一圈扫掉的积雪体积为 $l\cdot h$。而三角形斜面的体积是 $\frac{1}{2}l\cdot h=w$，所以 $l\cdot h=2w$——走一圈扫掉的雪量是路面存雪量的两倍。

扫雪机	置换-选择
路面的积雪	工作区里的记录
扫走的雪	输出的 MINIMAX 记录
新落的雪	新读入的记录
落在扫雪机前面的雪（这一圈能扫走）	关键字大于上次输出的新记录（属当前段）
落在扫雪机后面的雪（下一圈才扫）	关键字小于上次输出的新记录（属下一段）
扫雪机走一圈	生成一个初始归并段

关键字随机时，新记录比上次输出大或小的概率相等（对应雪均匀落在前后），系统平衡后走一圈扫掉 $2w$——所以初始归并段长度的期望值就是 $2w$。若不计输入输出时间，对 $n$ 条记录生成所有初始归并段所需时间为 $O(n{\log }_{2}w)$。

完整的算法步骤（输入文件 FI、输出文件 FO、内存工作区 WA 可容纳 $w$ 条记录）：

1. 从 FI 读入 $w$ 条记录填满 WA；
2. 从 WA 中选出关键字最小的记录，记为 MINIMAX 记录；
3. 把 MINIMAX 记录输出到 FO；
4. 若 FI 不空，则从 FI 读入下一条记录填补 WA 的空位；
5. 从 WA 中所有关键字比 MINIMAX 记录大的记录中，选出关键字最小者，作为新的 MINIMAX 记录；
6. 重复 3～5，直到 WA 中选不出新的 MINIMAX 记录为止——当前归并段结束；
7. 重复 2～6，直到 WA 为空。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 10.21，p469

图中每个记录都附带一个归并段号：新读入的记录若关键字不小于刚输出的记录，段号与当前段相同；若更小，段号加 1。选 MINIMAX 时先比段号（小者胜）、段号相同再比关键字——这样"选最小的且不小于上次输出的"就被统一成了一次普通的选最小值，可以直接复用败者树。

最佳归并树与虚段

置换-选择产出的段长不等，归并的次序就有讲究了。

设 9 个初始归并段长度为 9, 30, 12, 18, 3, 17, 2, 6, 24（合计 121），做 3 路归并。

平衡归并（按顺序每 3 个一组）：第 1 趟 $(9+30+12)=51$、$(18+3+17)=38$、$(2+6+24)=32$；第 2 趟合成 121。每条记录在每趟里读一次写一次，两趟共 $121\times 2\times 2=484$ 次读／写。

把归并段长度看成归并树中叶结点的权，这棵 3 叉树每个叶子深度都是 2，$\text{WPL}=2\times 121=242$，读写次数恰为 $2\times 242=484$。通用规律：

🔴 总读／写次数 $=2\times \text{WPL}$。 因为权为 $\omega$、深度为 $\ell$ 的叶结点，其记录要参与 $\ell$ 趟归并、每趟读写各一次，贡献 $2\omega \ell$。

既然读写次数正比于 WPL，让 WPL 最小的归并树就是最优方案——那正是 $k$ 叉哈夫曼树：每次挑权值最小的 $k$ 个结点合并，让权值大的归并段靠近树根（晚参与归并、少被搬运几趟）。

对上面 9 个段构造 3 叉哈夫曼树：

$$2+3+6=11\to 9+11+12=32\to 17+18+24=59\to 30+32+59=121$$$$\text{WPL}=11+32+59+121=223,\text{读／写次数}=2\times 223=446$$

比平衡归并的 484 次少 38 次。

虚段规则。 最佳归并树必须是一棵严格 $k$ 叉树（每个内部结点恰有 $k$ 个孩子）。若 $m$ 凑不齐，就要补长度为 0 的虚段。设叶结点数 $n_0$、度为 $k$ 的内部结点数 $n_k$：结点总数 $n=n_0+n_k$，边数一方面是 $k\cdot n_k$、另一方面是 $n-1$，联立得

$$n_k=\frac{n_0-1}{k-1}$$

$n_k$ 必须是整数，所以 $(n_0-1)$ 必须能被 $(k-1)$ 整除。于是判据是：

🔴 设 $u=(m-1)mod(k-1)$。$u=0$ 时不需补虚段；$u\ne 0$ 时需补 $k-u-1$ 个虚段（等价说法：第一次归并做 $u+1$ 路）。

⚠️ 分母是 $k-1$ 不是 $k$，这一处最容易记错。

三个算例：

$m$	$k$	$u=(m-1)mod(k-1)$	补几个虚段	第一次归并路数
8	3	$7mod2=1$	$3-1-1=1$	2
120	12	$119mod11=9$	$12-9-1=\mathbf{2}$	10
9	3	$8mod2=0$	0	3

虚段放在哪一层？ 权值为 0，按哈夫曼树的构造原则权最小的叶子离树根最远，所以虚段自动落到最底层、参加第一次归并。⚠️ 不能把虚段留到最后——那等于让某些真实归并段多搬运一趟。

败者树：建树与调整的全过程（第一次学、或要手工模拟一趟就展开）

先看胜者树：树形选择排序用一棵完全二叉树表示"选最小值"的比赛，叶结点是 $k$ 个参赛者，每个非终端结点存放它两个孩子中的胜者，根结点是冠军。输出冠军后把它所在叶结点换成同段下一个元素，从该叶结点向上重新比赛，路径长 $\lceil {\log }_{2}k\rceil$。

	胜者树	败者树
内部结点存的是	这场比赛的胜者	这场比赛的败者
叶结点更新后向上调整时	新值要与兄弟结点比较，每上一层访问两个结点	新值直接与双亲里记着的那个败者比较，每上一层只访问一个结点

一个 4 路归并的实例。设 4 个归并段的当前首元素为 $b_0=5$、$b_1=12$、$b_2=3$、$b_3=9$：

第 1 轮：b₀(5) vs b₁(12) → 胜者 b₀，败者 b₁ 存进 ls[2]
        b₂(3) vs b₃(9)  → 胜者 b₂，败者 b₃ 存进 ls[3]
第 2 轮：b₀(5) vs b₂(3)  → 胜者 b₂，败者 b₀ 存进 ls[1]
冠军：ls[0] = b₂（值 3）

                ls[0] = b₂(3)    ← 冠军，当前 4 段中的最小值
                    |
                ls[1] = b₀(5)    ← 记录败者的来源段号
               /            \
        ls[2] = b₁(12)   ls[3] = b₃(9)
          /      \         /      \
      b₀(5)   b₁(12)   b₂(3)   b₃(9)   ← 叶子：各段当前元素

输出冠军 3，从 $b_2$ 段读入下一个元素（设为 7），沿 $b_2$ 到根的路径调整：

从 b₂ 出发向上：
  ls[3] 记着败者 b₃(9)：7 vs 9 → 7 胜，b₃ 仍是败者留在 ls[3]，7 继续上行
  ls[1] 记着败者 b₀(5)：7 vs 5 → 5 胜，于是 b₂(7) 成为新败者留在 ls[1]，b₀ 继续上行
新冠军：ls[0] = b₀（值 5）

整个调整只做了 2 次比较（$=\lceil {\log }_{2}4\rceil$），而不是重新从 4 个里选最小的 3 次；路径上每层只访问了双亲那一个结点。

两个实现细节：

• 段变空怎么办：为防止某个归并段先变空，在每个归并段末尾附加一个关键字为最大值（$+\mathrm{\infty }$）的记录。当选出的冠军关键字为最大值时，说明所有段都已耗尽。
• 建树怎么初始化：先令所有非终端结点指向一个含最小关键字（$-\mathrm{\infty }$）的虚拟叶结点，然后把 $k$ 个段的首元素逐个"加入"并自下而上调整——每个新元素相对于 $-\mathrm{\infty }$ 都是败者，会被逐个填进各内部结点。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 10.19，p465

最佳归并树的另一个算例（想再看一遍 WPL 怎么算就展开）

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 10.25，p474

按图中次序算：$1+3+5=9$，$7+9+9=25$，$13+16+20=49$，$24+25+30=79$，$38+49+79=166$，故

$$\text{WPL}=9+25+49+79+166=328,\text{总读写次数}=2\times 328=656$$

若按最佳归并树方案在磁盘上做归并排序，还需在内存中建立一张索引表，记载各归并段的长度和它在磁盘上的物理位置。

考点速记

三条结论：

1. 归并趟数 $S=\lceil {\log }_{k}m\rceil$，$\log$ 里是段数；减少它只有"增大 $k$"和"减少 $m$"两条路。
2. 败者树把选最小从 $k-1$ 次降到 $\lceil {\log }_{2}k\rceil$ 次，使内部归并时间与 $k$ 脱钩；内部结点存的是归并段号，不是关键字。
3. 总读写次数 $=2\times$ 归并树的 WPL；虚段个数由 $u=(m-1)mod(k-1)$ 决定，分母是 $k-1$。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 求需要补充的虚段个数：给初始归并段数 $m$ 与路数 $k$。先算 $u=(m-1)mod(k-1)$，$u\ne 0$ 时补 $k-u-1$ 个。$m=120$、$k=12$ 时 $u=119mod11=9$，补 2 个。⚠️ 分母是 $k-1$，写成 $modk$ 或 $mmod(k-1)$ 都会算错。
• 败者树中记录"冠军"的结点保存的是什么：答"最小关键字所在的归并段号"。两个考点合在一起——方向是最小（归并段升序，要取最小才能维持输出升序），内容是段号（不是关键字本身，因为要按段号回到叶子补新元素）。
• 置换-选择生成初始归并段（大题）：① 给定序列和工作区容量 $m$，问能生成几个初始归并段、各是什么——逐步填表，标准是"最小的且不小于上次输出的"；② 问第一个初始归并段长度的最大值与最小值——最大 $n$（输入升序）、最小 $m$（输入降序）。
• 10TB 数据文件用什么方法排序：答归并排序。
• $k$、$d$、初始归并段与内存大小的关系判断：$k$ 越大 $d$ 越小 ✓、初始归并段数不影响 $d$ ✗、内存大小限制初始归并段的最大长度 ✓。

易错：虚段公式的分母是 $k-1$。 严格 $k$ 叉树的叶子数满足 $(n_0-1)mod(k-1)=0$，这才是判据的来源。

易错：败者树内部结点存段号不存关键字。 关键字只在叶子里。

易错：归并趟数公式里的对数真数是段数 $m$，不是记录数 $n$。

教材出处

• 外部排序的两个阶段、归并段（顺串）的概念、10 000 条记录 / 10 个初始归并段 / 每块 200 条记录的例子及 2 路归并 4 趟共 500 次读写（图 8.16）：严蔚敏《数据结构（C 语言版）》（第 2 版），p260
• 外部排序总时间的三项构成（式 8-4）、"提高外排的效率应主要着眼于减少外存信息读写的次数 $d$"、5 路平衡归并只需两趟、总读写降至 300 次（图 8.17）、归并趟数 $s=\lceil {\log }_{k}m\rceil$（式 8-5）、减少 $s$ 的两个途径：同书 p261
• $k$ 路归并朴素选最小需 $k-1$ 次比较、内部归并总比较次数式（8-6）、$(k-1)/{\log }_{2}k$ 随 $k$ 增长、"若利用败者树，则可使在 $k$ 个记录中选出关键字最小的记录时仅需进行 $\lceil {\log }_{2}k\rceil$ 次比较，从而使总的归并时间变为 $\lceil {\log }_{2}m\rceil (n-1)t_{mg}$，这个式子和 $k$ 无关"、败者树的定义（"在双亲结点中记下刚进行完的这场比赛中的败者，而让胜者去参加更高一层的比赛"）、5 路归并的败者树示例（图 8.18）、段变空时附加最大值记录、败者树初始化方法：同书 p262
• "$k$ 值的选择并非越大越好，如何选择合适的 $k$ 是一个需要综合考虑的问题"：同书 p263
• 置换-选择排序的动机、特点（"选择最小关键字和输入、输出交叉或平行进行"）、完整操作步骤、24 条记录 / 工作区 6 的对照例与过程表（表 8.1）：同书 p263–p264
• 用败者树实现 MINIMAX 选择的三个细节（记录附设归并段序号、先比段号后比关键字、建树从段号为零开始）：同书 p264
• "所得初始归并段的平均长度为内存工作区大小 $w$ 的两倍"及扫雪机类比（图 8.20）、生成所有初始归并段所需时间 $O(n{\log }_{2}w)$：同书 p265–p266
• 最佳归并树：9 个长度不等的初始归并段做 3 路平衡归并需 484 次读写、"若将初始归并段的长度看成归并树中叶子结点的权，则此 3 叉树的带权路径长度的两倍恰为 484"、构造哈夫曼树可使读写次数最少（图 8.21、图 8.22）：同书 p266
• 虚段规则："对 $k$ 路归并而言，若 $(m-1)mod(k-1)=0$，则不需加虚段，否则需附加 $k-(m-1)mod(k-1)-1$ 个虚段。换句话说，第一次归并为 $(m-1)mod(k-1)+1$ 路归并"、"权为零的叶子应离树根最远"、需在内存建立记载归并段长度与物理位置的索引表：同书 p267
• 图 10.19 利用败者树进行 5 路平衡归并的过程：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版），p465
• 图 10.21 利用败者树生成初始归并段的过程：同书 p469
• 图 10.25 构造 3 路归并树的过程：同书 p474

相关知识

二路归并排序（外部排序的内核）｜ 哈夫曼树与哈夫曼编码（最佳归并树就是 $k$ 叉哈夫曼树）｜ 堆（与败者树同属"用树保存比较结果"）｜ 堆排序（树形选择排序是共同前身）｜ 排序的基本概念（内、外排序的分界）｜ B+ 树（同样面向磁盘的设计思路）

相关文章

• 排序基本概念
• 直接插入排序
• 折半插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 基数排序
• 计数排序
• 由中间状态反推排序算法
• 排序算法对比与性能实测

交互体验

前往完整可视化页面 →

真题练习

相关真题（4题）

2024Q112分2023Q4210分2019Q112分2016Q112分