6.外部排序

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

外部排序的方法

• 外部排序过程中的时问代价主要考虑访问磁盘的次数,即I/O次数。
• 外部排序通常采用归并排序法

在外部排序中实现两两归并时,由于不可能将两个有序段及归并结果段同时存放在内存中, 因此需要不停地将数据读出、写入磁盘,而这会耗费大量的时间,一般情况下:

外部排序的总时间=内部排序所需的时问 +外存信息读写的时间+内部归并所需的时间

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

一般地, 对 $r$ 个初始归并段, 做 $k$ 路平衡归并, 归并树可用严格 $k$ 叉树 (即只有度为 $k$ 与度为 0 的 结点的 $k$ 叉树）来表示。第一趟可将 $r$ 个初始归并 段归并为 $\left\lceil r / k \right\rceil$ 个归并段, 以后每趟归并将 $m$ 个归并 段归并成 $\left\lceil m / k \right\rceil$ 个归并段, 直至最后形成一个大的归并段为止。

$$\text{树的高度}-1=\left\lceil \log _{k}r\right\rceil= \text{归并趟数} S$$

可见, 只要增大归并路数 $k$, 或减少初始归并段个数 $r$, 都能减少归并趟数 $S$, 进而减少读写磁盘的次数, 达到提高外部排序速度的目的。

多路平衡归并与败者树

提示

做内部归并时, 在 $k$ 个元素中选择关键字最小的记录需 要比较 $k-1$ 次。每趟归并 $n$ 个元素需要做 $(n-1)(k-1)$ 次比较, $S$ 趟归并总共需要的比较次 数为

$$S(n-1)(k-1)=\left\lceil\log _{k} r\right\rceil(n-1)(k-1)=\left\lceil\log _{2} r\right\rceil(n-1)(k-1) /\left\lceil\log _{2} k\right\rceil$$

式中, $(k-1)\left\lceil\log _{2} k\right\rceil$ 随 $k$ 增长而增长, 因此内部归并时间亦随 $k$ 的增长而增长。这将抵消由于增 大 $k$ 而减少外存访问次数所得到的效益。因此, 不能使用普通的内部归并排序算法。

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

败者树实例

若比较两个数, 大的为失败者、小的为胜利者, 则根结点指向的数为最小数。

image.png

之所以在父节点中存储的是失败者的段号，是因为这样当新加入一个元素时，就可以直接通过父节点中的段号与上一轮的失败者比较

因为 $k$ 路归并的败者树深度为 $\left\lceil\log _{2} k\right\rceil$, 因此 $k$ 个记录中选择最小关键字, 最多需要 $\left\lceil\log _{2} k\right\rceil$ 次 比较。所以总的比较次数为

$$\left.S(n-1)\left\lceil\log _{2} k\right\rceil=\left\lceil\log _{k}\right\rceil\right\rceil(n-1)\left\lceil\log _{2} k\right\rceil=(n-1)\left\lceil\log _{2} r\right\rceil$$

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

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

败者树和传统简单选择比较次数对比

例题

置换-选择排序

设初始待排文件为 FI, 初始归并段输出文件为 FO, 内存工作区为 WA, FO 和 WA 的初始状 态为空, 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 记录为止, 由此得到一个初始归并段, 输出一个归并段的结束标志到 FO 中去。
7. 重复 2）～6), 直至 WA 为空。由此得到全部初始归并段。

算法实例

设待排文件 $\mathrm{FI}=\{17,21,05,44,10,12,56,32,29\}$, WA 容量为 3 。排序过程如表所示。

image.png

在WA 中选择MINIMAX 记录的过程需利用败者树来实现

最佳归并树

置换置换置换置换置换置换置换置换置换-选择排序)后,得到的是长度不等的初始归并段

叶结点到根的路径长度表示其参加归并的趟数,各非叶结点代表归并成的新归并段,根结点表示最终生成的归并段。树的带权路径长度 WPL 为归并过程中的总读记录数，故

$$\text{I/O次数}=2\times WPL$$

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

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

🤔如何判定添加虚段的数目?

$k$ 叉的最佳归并树一定是一棵严格的 $k$ 叉树, 即树中只包含度为 $k$ 、度为 0 的结点。 设度为 $k$ 的结点有 $n_{k}$ 个, 度为 0 的结点有 $n_{0}$ 个, 归并树总结点数 $=n$ 则:

$$\begin{cases} n=n_{0}+n_{k} \\ kn_{k}=n-1 \end{cases} \implies n_{0}=(k-1)n_{k}+1\implies n_{k}=\frac{n_{0}-1}{k-1}$$

• 若 $\left(n_{0}-1\right) \%(k-1)=0$ ， 则说明这 $n_{0}$ 个叶结点（初始归并段）正好可以构 造 $k$ 叉归并树。此时, 内结点有 $n_{k}$ 个。
• 若 $\left(n_{0}-1\right) \%(k-1)=u \neq 0$, 则说明对于这 $n_{0}$ 个叶结点, 其中有 $u$ 个多余, 不能包含在 $k$ 叉 归并树中。为构造包含所有 $n_{0}$ 个初始归并段的 $k$ 叉归并树, 应在原有 $n_{k}$ 个内结点的基础 上再增加 1 个内结点。它在归并树中代替了一个叶结点的位置, 被代替的叶结点加上刚才 多出的 $u$ 个叶结点, 即再加上 $k-u-1$ 个空归并段^[1], 就可以建立归并树。

---

1. 就是让上面那个式子可以整除即可 ↩︎