8.5 外部排序

外部排序的基本方法与时间开销，多路平衡归并与败者树，置换-选择排序生成初始归并段，以及最佳归并树。

外部排序的基本概念

前面介绍过的排序方法都是在内存中进行的（称为内部排序）。而在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。这种排序算法就称为外部排序。

外部排序的方法

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

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

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

多路平衡归并与败者树

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

式中，$(k-1)/\lceil \log_2 k \rceil$ 随 $k$ 增长而增长，因此内部归并时间亦随 $k$ 的增长而增长。这将抵消由于增大 $k$ 而减少外存访问次数所得到的效益。为了使内部归并不受 $k$ 的增大的影响，引入了败者树。

败者树是树形选择排序的一种变体，可视为一棵完全二叉树。$k$ 个叶结点分别存放 $k$ 个归并段在归并过程中当前参加比较的元素，内部结点用来记忆左右子树中的”失败者”，而让胜者往上继续进行比较，一直到根结点。若比较两个数，大的为失败者、小的为胜利者，则根结点指向的数为最小数。

1void Adjust(int s) {         // 沿叶结点 b[s] 到根 ls[0] 的路径调整
2    int t = (s + k) / 2;         // ls[t] 是 b[s] 的双亲结点
3    while (t > 0) {
4        if (b[s] > b[ls[t]])     // s 输给了 ls[t] 所指的结点
5            swap(s, ls[t]);      // 败者留在 ls[t]，胜者 s 继续向上
6        t = t / 2;
7    }
8    ls[0] = s;                   // 冠军（最小关键字）记录在 ls[0]
9}
10void K_Merge() {
11    for (i = 0; i < k; i++) input(b[i]);   // 读入各段第一个记录
12    CreateLoserTree();
13    while (b[ls[0]] != MAXKEY) {
14        q = ls[0];               // q 指示当前最小值所在的归并段
15        output(q);               // 输出到归并后的有序段
16        input(b[q]);             // 从第 q 段读入下一个记录
17        Adjust(q);               // 调整败者树
18    }
19}

置换-选择排序（生成初始归并段）

从 $\lceil \log_k r \rceil$ 可知，减少初始归并段个数 $r$ 也可以减少归并趟数 $S$。若总的记录个数为 $n$，每个归并段的长度为 $\ell$，则归并段的个数 $r = \lceil n/\ell \rceil$。采用内部排序方法得到的各个初始归并段长度都相同（除最后一段外），它依赖于内部排序时可用内存工作区的大小。因此，必须探索新的方法，用来产生更长的初始归并段，这就是置换-选择算法。

设初始待排文件为 FI，初始归并段输出文件为 FO，内存工作区为 WA，FO 和 WA 的初始状态为空，WA 可容纳 $w$ 个记录。置换-选择算法的步骤如下：

1// 置换-选择排序生成初始归并段
2从 FI 输入 w 个记录到工作区 WA;
3while (WA 不空) {
4    从 WA 中选出关键字 >= MINIMAX 的最小记录 x;
5    if (找不到) {                 // WA 中所有记录都比 MINIMAX 小
6        输出归并段结束标志;        // 当前段结束，开始新的段
7        MINIMAX = -∞; continue;
8    }
9    将 x 输出到 FO;  MINIMAX = x.key;
10    若 FI 不空，则从 FI 输入下一个记录到 WA;
11}

最佳归并树

文件经过置换-选择排序后，得到的是长度不等的初始归并段。下面讨论如何组织长度不等的初始归并段的归并顺序，使得 I/O 次数最少。

在归并树中，各叶结点表示一个初始归并段，叶结点上的权值表示该归并段的长度，叶结点到根的路径长度表示其参加归并的趟数，各非叶结点代表归并成的新归并段，根结点表示最终生成的归并文件。归并树的带权路径长度 WPL 为归并过程中的总读记录数，故 I/O 次数 = 2 × WPL。

显然，归并方案不同，所得归并树亦不同，树的带权路径长度（I/O 次数）亦不同。为了优化归并树的 WPL，可将哈夫曼树的思想推广到 $m$ 叉树的情形。在归并树中，让记录数少的初始归并段最先归并，记录数多的初始归并段最晚归并，就可以建立总的 I/O 次数最少的最佳归并树。

例如：8 个初始归并段做 3 路归并，$(8 - 1) \bmod (3 - 1) = 1$，需补 $3 - 1 - 1 = 1$ 个虚段。

即时练习