外部排序

外部排序的基本概念

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

外部排序的方法

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

外部排序通常采用归并排序法。它包括两个相对独立的阶段：

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

一般地，对 个初始归并段，做 路平衡归并：

1. 最多只能有 个段归并为一个；
2. 每一趟归并中，若有 个归并段参与归并，则经过这一趟处理得到 个新的归并段。

第一趟可将 个初始归并段归并为 个归并段，以后每趟归并将 个归并段归并成 个归并段，直至最后形成一个大的归并段为止。树的高度 = = 归并趟数 。可见，只要增大归并路数 ，或减少初始归并段个数 ，都能减少归并趟数 ，进而减少读写磁盘的次数，达到提高外部排序速度的目的。

多路归并带来的负面影响：

1. 路归并时，需要开辟 个输入缓冲区，内存开销增加
2. 每挑选一个关键字需要对比关键字 次，内部归并所需时间增加

   多路平衡归并与败者树

   增加归并路数 能减少归并趟数 ，进而减少 I/O 次数。然而，增加归并路数 时，内部归并的时间将增加。做内部归并时，在 个元素中选择关键字最小的记录需要比较 次。每趟归并 个元素需要做 (k-%201)#card=math&code=%28n-%201%29%28k-%201%29&id=HjutT) 次比较， 趟归并总共需要的比较次数为

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

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

因为 路归并的败者树深度为 ， 因此 个记录中选择最小关键字，最多需要 次比较。所以总的比较次数为：

可见，使用败者树后，内部归并的比较次数与 无关了。因此，只要内存空间允许，增大归并路数 将有效地减少归并树的高度，从而减少 I/O 次数，提高外部排序的速度。

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

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

减少初始归并段个数 也可以减少归并趟数 。若总的记录个数为 ，每个归并段的长度为 ，则归并段的个数 。采用内部排序方法得到的各个初始归并段长度都相同（除最后一段外），它依赖于内部排序时可用内存工作区的大小。因此，必须探索新的方法，用来产生更长的初始归并段。

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

1. 从 FI 输入 个记录到工作区 WA。
2. 从 WA 中选出其中关键字取最小值的记录，记为 MINIMAX 记录。
3. 将 MINIMAX 记录输出到 FO 中去。
4. 若 FI 不空，则从 FI 输入下一个记录到 WA 中。
5. 从 WA 中所有关键字比 MINIMAX 记录的关键字大的记录中选出最小关键字记录，作为新的 MINIMAX 记录。
6. 重复 3~5，直至在 WA 中选不出新的 MINIMAX 记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到 FO 中去。
7. 重复 2~6，直至 WA 为空。由此得到全部初始归并段。

上述算法，在 WA 选择 MINIMAX 记录的过程需利用败者树来实现

最佳归并树

归并过程中的磁盘 I/O 次数 = 归并树的 WPL * 2

要让磁盘 I/O 次数最少，就要使归并树 WPL 最小，即哈夫曼树

将哈夫曼树的思想推广到 叉树的情形，在归并树中，让记录数少的初始归并段最先归并，记录数多的初始归并段最晚归并，就可以建立总的 I/O 次数最少的最佳归并树。

若初始归并段不足以构成一棵严格 叉树时，需添加长度为 0 的“虚段”，按照哈夫曼树的原则，权为 0 的叶子应离树根最远。

如何判定添加虚段的数目

设度为 0 的结点有 #card=math&code=n_0%20%28%3Dn%29&id=DYkxS) 个，度为 的结点有 个，则对严格 叉树有 n_k%2B1#card=math&code=n_0%3D%28k-1%29n_k%2B1&id=CQTnY)，由此可得 %7D%7B(k-1)%7D#card=math&code=n_k%3D%5Cfrac%7B%28n_0-1%29%7D%7B%28k-1%29%7D&id=VT5gh)。

• 若 ，则说明这 个叶结点（初始归并段）正好可以构造 叉归并树。此时，内结点有 个。
• 若 %20%5Cbmod%20(k-1)%20%3Du%20%20%5Cne%200#card=math&code=%28n_0-1%29%20%5Cbmod%20%28k-1%29%20%3Du%20%20%5Cne%200&id=xMwOa) ，则说明对于这 个叶结点，其中有 个多余，不能包含在 叉归并树中。为构造包含所有 个初始归并段的 叉归并树，应在原有 个内结点的基础上再增加 1 个内结点，即再加上 个空归并段，就可以建立归并树。