九、外排序
9.1 外排序概述
1、什么是外排序
外排序是指数据存放在外存中，数据排序时涉及内、外存数据交换的排序方法。
存储在外存上的数据以文件为基本单位。
2、外排序的基本方法
外排序的基本方法时归并排序法。它分为以下两个步骤：
(1) 生成若干初始归并段(顺串)：这一过程也称为文件预处理。一种常规的方法如下：
① 把含有n个记录的文件，按内存大小w分成若干长度为w的子文件(归并段)；
② 分别将各子文件调入内存，采用有效的内排序方法排序后送回外存，产生n/2↑个初始归并段。
(2) 多路归并：对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。
详细的过程见PPT。
归并过程的性能与 记录读写次数、内存中归并时需要关键字比较次数 有关。
外排序方法与各种外存设备的特征有关。
外存设备大体上可分为两类：
- 顺序存取设备，例如磁带。
- 直接存取设备，例如磁盘。
9.2 磁盘排序
9.2.1 生成初始归并段
另一种方法：采用一种称为 置换–选择 排序方法用于生成初始归并段。
置换–选择排序方法:
（1）从待排文件Fin中按内存工作区WA的容量w读入w个记录。设归并段编号i=1。
（2）使用败者树从WA中选出关键字最小的记录Rmin。
（3）将Rmin记录输出到Fout中，作为当前归并段的一个成员。
（4）若Fin不空，则从Fin中读入下一个记录x放在Rmin所在的工作区位置代 替Rmin。
（5）在工作区中所有≥Rmin的记录中选择出最小记录作为新的Rmin，转 （3），直到选不出这样的Rmin。
（6）设i=i+1，开始一个新的归并段。
（7）若工作区已空，则初始归并段已全部产生；否则转（2）。
置换–选择排序中关键字比较次数分析：
共有n个记录，内存工作区WA的容量为w：
- 若在w各记录中选取最小关键字采用简单比较方法，每次需要w-1次比较。
- 总的时间复杂度为O(nw)。
9.2.2 多路平衡归并
1、k路平衡归并概述
(1) 什么是k路平衡归并
2路平衡归并：每一趟从m个归并段得到m/2↑个归并段。
一般地，2路平衡归并的前提：初始归并段的记录个数都相同。→可以推广到k路平衡归并
(2) 影响k路平衡归并的因素
影响k路平衡归并效率的因素：
- 归并时需要读写磁盘的次数
- 归并时需要关键字比较的次数
(3) k路平衡归并时读写磁盘次数的计算
例如，m=8，假设每个归并段4个记录，k=2。
读记录次数=WPL=8*4*3=96.(如果每个记录占用一个物理块，读写磁盘次数=96*2=192次)
采用k路平衡归并时，通常k越大，读写磁盘次数会减少。
(4) k路平衡归并时关键字比较次数的计算
结论：
增大归并路数k，读写磁盘次数减少，而关键字比较次数会增大。若k增大到一定的程度，就会抵消掉由于减少读写磁盘次数而赢得的时间，
2、利用败者树实现k路平衡归并过程
败者树用于在k各记录中选取最小关键字的记录。败者树类似于堆排序中的堆。
利用败者树实现k路平衡归并的过程是：
- 先建立败者树，每个叶子结点对应一个归并段。（详细步骤及图示见PPT）
- 然后对k个输入有序段进行k路平衡归并。
调整产生冠军(最小值)的过程：将当前节点的关键字与父节点比较，将大的(败者)放在父节点中，小者(胜者)继续进行，直到根节点。最后将胜者放在冠军节点中。然后将冠军放入文件中，取其所在归并段下一个元素之前步骤。
结论：
关键字比较次数与k无关 → 总的内部归并时间不会随k的增大而在增大。
利用败者树实现k路平衡归并。
只要内存空间允许，尽可能增大归并路数k。
采用败者树，置换–选择排序中关键字比较次数分析
共有n个记录，内存空间WA的容量为w：
- 若在w各记录中选取最小关键字的采用败者树方法，每次需要log2 w 次比较。
- 总的时间复杂度为O(nlog2 w)。
9.2.3 最佳归并树
最佳归并树（m个初始归并段）是带权路径长度最短的k叉 （阶）哈夫曼树，构造步骤如下：
(1) 若x=(m-1) Mod (k-1)≠0，则需附加(k-1)-x个虚段，以使每次归并都可以对应k个段。
(2) 按照哈夫曼树的构造原则（权值越小的节点离根节点越远）构造最佳归并树。
有关最佳归并树的详细介绍见PPT。
归纳：
(1) 生成多个初始归并段采用常规方法，产生长度相同的归并段 → 宜采用多路平衡归并（归并中用败者树）
(2) 生成多个初始归并段采用置换-选择算法，产生长度不相同的归并段 → 宜采用最佳归并树方案（归并中用败者树）