考研笔记

外部排序与败者树

8.7 是全章唯一在算法竞赛里完全没有对应物的一节——它的优化目标是磁盘 I/O，不是 CPU 时间。

教材开门见山给了考查范围和全节的五条线索：

外部排序可能会考查相关概念、方法和排序过程，外部排序的算法比较复杂，不会在算法设计上进行考查。 本节的主要内容有： ① 外部排序指的是大文件的排序，即待排序的记录存储在外存中，待排序的文件无法一次性装入内存，需要在内存和外存之间进行多次数据交换，以达到排序整个文件的目的。 ② 为减少平衡归并中外存读/写次数所采取的方法：增大归并路数和减少归并段个数。 ③ 利用败者树增大归并路数。 ④ 利用置换-选择排序增大归并段长度来减少归并段个数。 ⑤ 由长度不等的归并段进行多路平衡归并，需要构造最佳归并树。

「不会在算法设计上进行考查」——这一节不用背代码，全部精力放在「数出趟数和 I/O 次数」。

机制

基本概念与代价模型

文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读/写的。因为磁盘读/写的机械动作所需的时间远远超过在内存中进行运算的时间（相比而言可以忽略不计），因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即 I/O 次数。

外部排序的总时间内部排序的时间外存信息读写的时间内部归并的时间

显然，外存信息读/写的时间远大于内部排序和内部归并的时间，因此应着力减少 I/O 次数。

归并段与两个阶段

外部排序通常采用归并排序算法，包括两个阶段：

  1. 根据内存缓冲区大小，将外存上的文件分成若干长度为 的子文件，依次读入内存并利用内部排序算法对它们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串。
  2. 对这些归并段进行逐趟归并，使归并段（有序子文件）逐渐由小到大，直至得到整个有序文件为止。

教材的例子：一个含有 2000 个记录的文件，每个磁盘块可容纳 125 个记录，首先通过 8 次内部排序得到 8 个初始归并段 ，每段都含 250 条记录。

内存工作区等分为三个缓冲区：两个输入缓冲区，一个输出缓冲区。从两个输入归并段中分别读入一个块，在内存中进行二路归并，归并后的对象顺序存放在输出缓冲区中；若输出缓冲区存满，则将其顺序写到输出归并段中，再清空输出缓冲区；若某个输入缓冲区取空，则从对应的输入归并段中再读取下一块。

归并趟数与 I/O 次数

一般地，对 个初始归并段，做 路归并（每趟将 个或 个以下的有序子文件归并成一个有序子文件）。第一趟可将 个初始归并段归并为 个归并段，以后每趟归并将 个归并段归并成 个归并段，直至最后形成一个大的归并段为止。

归并趟数

「只要增大归并路数 ，或减少初始归并段个数 ，都能减少归并趟数 ，进而减少读/写磁盘的次数，达到提高外部排序速度的目的。」

教材的算例（必须会数）：2000 个记录、每块 125 个记录 共 块。

方案趟数总读/写次数
二路归并（）每趟 16 读 + 16 写；
四路归并（）

末尾那个 是内部排序时所需进行的读/写（把 16 块读进来、写回去）。这一项与归并趟数无关，容易漏掉。

为什么不能无限增大 ：败者树

增加归并路数 能减少归并趟数 ，进而减少 I/O 次数。然而，增加归并路数 时，内部归并的时间将增加。 做内部归并时，在 个元素中选择关键字最小的元素需要 次比较，每趟归并 个元素需要做 次比较， 趟归并总共需要的比较次数为

式中， 随 增长而增长，因此内部归并时间亦随 的增长而增长。这将抵消因增大 而减少外存访问次数所得到的效益。因此，不能使用普通的内部归并排序算法。

为了使内部归并不受 的增大的影响，引入了败者树。

败者树

败者树是树形选择排序的一种变体，可视为一棵完全二叉树。

  • 个叶结点分别存放 个归并段在归并过程中当前参加比较的元素；
  • 内部结点用来记忆左右子树中的「失败者」，而让胜利者往上继续进行比较，一直到根结点；
  • 若比较两个数，大的为失败者、小的为胜利者，则根结点指向的数为最小数。

教材图 8.17（5 路归并）的过程： 与 比较， 是败者，将段号 4 写入父结点 ls[4]。 与 比较， 是败者，将段号 2 写入 ls[3]。 与 的胜者 与 比较， 是败者，将段号 0 写入 ls[2]。最后两个胜者 与 比较， 是败者，将段号 1 写入 ls[1]；而将胜者 的段号 3 写入 ls[0]。此时，根结点 ls[0] 所指的段的关键字最小。

  • 对于 路归并，初始构造败者树需要 次比较。
  • 中的元素输出后，将下一关键字填入 ，继续比较。
  • 因为 路归并的败者树深度为 ，所以从 个记录中选择最小关键字，仅需进行 次比较。因此总的比较次数约为

「可见，使用败者树后，内部归并的比较次数与 无关了。」

边界辨析：

ls[0] 存的是「冠军」的段号，不是败者。 内部结点 ls[1]~ls[k-1] 存的才是各次比较的败者， ls[0] 单独存最终胜者。这是败者树最容易记反的一处。 「败者树」这个名字说的是内部结点存败者，而不是根存败者。

边界辨析：

归并路数 并不是越大越好（教材原话）： 「归并路数 增大时，相应地需要增加输入缓冲区的个数。若可供使用的内存空间不变，势必要减少每个输入缓冲区的容量，使得内存、外存交换数据的次数增大。当 值过大时，虽然归并趟数会减少，但读/写外存的次数仍会增加。」

所以「增大 一定更快」是错的。 败者树解决的只是内部比较的瓶颈，没有解决缓冲区变小的瓶颈。

手算模板

算归并趟数与 I/O 次数：

  1. 数块数 总记录数每块记录数。
  2. 数初始归并段个数 和路数 。
  3. 趟数 。
  4. 归并阶段的读/写 （每趟把所有块读一遍、写一遍）。
  5. 加上内部排序阶段的读/写 。
  6. 总计 。

验算教材例子：，。二路：，总 ✅；四路：，总 ✅。

败者树的一次调整：

  1. 输出根 ls[0] 所指段的当前元素。
  2. 该段补入下一个元素到对应叶结点 。
  3. 从 沿到根的路径逐层与 ls[] 中的败者比较：败者留在该结点，胜者继续往上。
  4. 最后把胜者的段号写入 ls[0]。
  5. 共比较 次（树高减 1）。

边界

说法判断说明
「外部排序会考算法设计」❌教材明说不会在算法设计上进行考查
「外部排序的时间主要是内部排序时间」❌主要是 I/O 次数
「归并趟数 」❌， 是路数
「总 I/O 次数 」❌还要加内部排序阶段的
「增大 一定更快」❌缓冲区变小会使交换次数增大， 过大时读/写反而增加
「用普通内部归并即可」❌内部比较随 增长，会抵消 I/O 的收益，所以要用败者树
「败者树的内部结点存胜者」❌存败者；ls[0] 存最终胜者
「 路归并败者树有 个内部结点」❌ 个叶结点， 个内部结点（加 ls[0]）
「初始构造败者树需要 次比较」❌ 次
「每次选最小需要 次比较」❌用败者树只需 次
「败者树深度为 」❌
「内存分两个缓冲区」❌二路归并要三个：两输入 + 一输出

口径差异：

算竞里没有「外部排序」这个概念——数据总在内存里，sort() 就够了。 8.7 因此是整章唯一「必须从零学」的部分，也是有算竞背景的人最容易低估的一节。 好消息是它不考代码，只考数数：趟数、比较次数、I/O 次数、缓冲区个数。 把上面那个 的模板背下来，这一节的计算题就基本拿下了。

对照速查

量式子
归并趟数
总 I/O 次数
普通内部归并总比较
用败者树后总比较，与 无关
败者树深度
选一次最小的比较次数
初始建败者树 次比较
缓冲区个数（ 路） 个输入 + 1 个输出
减少 I/O 的两条路手段
增大归并路数 败者树（8.7.3）
减少归并段个数 置换-选择排序（8.7.4）

考点

  • 对大文件排序时使用的排序算法（2016 命题追踪）：归并排序。
  • 归并趟数 与总 I/O 次数的计算。
  • 败者树的实现原理（2024 命题追踪）：内部结点存败者、ls[0] 存冠军、深度 。
  • 使用败者树后内部比较次数与 无关。
  • 不是越大越好及其理由。
  • 三个缓冲区（两输入一输出）。

链接

反向链接