数据基础及教程 9

10.8外排序外排序：指数据存放在外存中，数据排序时涉及内、外存数据交换的排序方法。存储在外存上的数据以文件为基本单位。文件内存数据交换1/41外排序基本过程

（1）生成初始归并段（顺串）：将一个文件（含待排序数据）中的数据分段读入内存，每个段在内存中进行排序，并将有序数据段写到外存文件上，从而得到若干初始归并段。

（2）多路归并：对这些初始归并段进行多路归并，使得有序归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。2/41文件内存数据交换外排序的时间是上述两个阶段的时间和。主要包含内外存数据交换时间和元素比较时间（元素移动次数相对较少）。3/41外存设备大体上可分为两类：外排序方法与各种外存设备的特征有关。顺序存取设备，例如磁带。直接存取设备，例如磁盘。仅仅讨论磁盘排序4/41文件abc.dat：5，6，3，4，9，8，1，7，10，2进行递增排序应用程序可用的内存空间大小w=2。示例5/415，6，3，4，9，8，1，7，10，2外排序过程w=2内存abc.dat（1）生成5个初始归并段abc1.dat：5，6abc2.dat：3，4abc3.dat：8，9abc4.dat：1，7abc5.dat：2，106/41k=2内存abc1.databc2.databc12.dat：3，4，5，6

（2）多路归并：w=2

2路归并（k=2）abc1.dat：5，6abc2.dat：3，47/41w=2内存abc3.databc4.databc34.dat：1，7，8，9abc3.dat：8，9abc4.dat：1，7abc3.dat和abc4.dat中每个元素读一次写一次（写入abc34.dat）8/41w=2内存abc3.databc4.databc34.dat：1，7，8，9abc3.dat：8，9abc4.dat：1，7abc3.dat和abc4.dat中每个元素读一次写一次（写入abc34.dat）9/41k=2内存abc12.databc34.databc1234.dat：1，3，4，5，6，7，8，9abc12.dat：3，4，5，6abc34.dat：1，7，8，9abc12.dat和abc34.dat中每个元素读一次写一次（写入abc1234.dat）10/41k=2内存abc1234.databc5.databc.dat：1，2，3，4，5，6，7，8，9，10abc1234.dat：1，3，4，5，6，7，8，9abc5.dat：2，10abc1234.dat和abc5.dat中每个元素读一次写一次（写入abc.dat）11/41归并过程对应的归并树5，6abc1.dat3，4abc2.dat3，4，5，6abc12.dat8，9abc3.dat1，7abc4.dat1，7，8，9abc34.dat1，3，4，5，6，7，8，9abc1234.dat1，2，3，4，5，6，7，8，9，10abc.dat2，10abc5.databc1.dat中每个元素读一次写一次（写入abc12.dat）12/4110.8.1生成初始归并段的方法1.常规方法内存FinF1F2…Fm均有序某内排序算法得到m个有序文件F1～Fm初始归并段，显然m=

n/w

。通常前m-1个有序文件的长度均为w，最后一个有序文件的长度小于等于w。WA为w13/412.置换-选择排序方法

（1）从待排文件Fin中按内存工作区WA的容量w读入w个元素。设归并段编号i=1。

（2）从WA中选出关键字最小的元素Rmin。

（3）将Rmin元素输出到当前归并段Fi。

（4）若Fin不空，则从Fin中读入下一个元素x放在Rmin所在的工作区位置代替Rmin。

（5）在工作区中所有≥Rmin的元素中选择出最小元素作为新的Rmin，转（3），直到选不出这样的Rmin。

（6）设i=i+1，开始一个新的归并段。

（7）若工作区已空，则初始归并段已全部产生；否则转（2）。14/41

【例10.11】设磁盘文件中共有18个元素，元素的关键字分别为：

（15，4，97，64，17，32，108，44，76，9，39，82，56，31，80，73，255，68）

若内存工作区可容纳5个元素，用置换－选择排序可产生几个初始归并段，每个初始归并段包含哪些元素?15/41173294476108398256318073154976425568∞18个元素（w=5）：内存工作区w=5归并段1：归并段2：Rmin=415173244647682971089依次类推，产生归并段2：9，31，39，56，68，73，80，25516/4110.8.2多路归并方法1.k路平衡归并方法2路平衡归并：每一趟从m个归并段得到

m/2

个归并段。m=8，k=2例如：

log2m=3遍

什么是k路平衡归并17/412路平衡归并：每一趟从m个归并段得到

m/2

个归并段。m=6，k=2，增加两个长度为0的虚段

log2m=3遍

可以推广到k路平衡归并18/41归并时需要读写磁盘的次数归并时需要关键字比较的次数。影响k路平衡归并的效率的因素：

影响k路平衡归并的因素19/41m=8，假设每个归并段4个元素：k=2读元素次数=WPL=8×4×3=96（如果每个元素占用一个物理块，读写磁盘次数=96×2=192次）例如

k路平衡归并时读写磁盘次数的计算采用k路平衡归并时，通常k越大，读写磁盘次数会减少。20/41

采用k路平衡归并时，则相应的归并树有

logkm

+1层，要对数据进行

logkm

趟扫描。m=8k=2

logkm

趟

k路平衡归并时关键字比较次数的计算21/41

logkm

×(u-1)×(k-1)=

log2m/

log2k

×(u-1)×(k-1)=

log2m

×(u-1)×(k-1)／

log2k

u个元素

logkm

趟每一趟需(u-1)×(k-1)次关键字比较总共需要的关键字比较次数为：22/41总共需要的关键字比较次数：

结论：增大归并路数k，读写磁盘次数减少，而关键字比较次数会增大。若k增大到一定的程度，就会抵消掉由于减少读写磁盘次数而赢得的时间。

log2m×(u-1)×(k-1)／

log2k

在初始归并段个数m与元素个数u确定时是常量(k-1)／

log2k

在k增大时会增大23/41利用败者树实现k路平衡归并的过程：

利用败者树实现k路平衡归并过程败者树用于在k个元素中选取最小关键字的元素。败者树类似于堆排序中的堆。先建立败者树。然后对k个输入有序段进行k路平衡归并。24/41

【例10.12】设有5个初始归并段，它们中各元素的关键字分别是：

F0：{17，21，∞}

F1：{5，44，∞}

F2：{10，12，∞}

F3：{29，32，∞}

F4：{15，56，∞}其中，∞是段结束标志。说明利用败者树进行k=5路平衡归并排序的过程。25/41

构建败者树29F315F417F05F110F2冠军（最小者）k=5：创建含有k个叶子结点的完全二叉树（结点个数最少）。n2=n0-1=k-1，n=n0+n1+n2=2k-1+n1，让n1=0，总共2k-1=9个结点，另外添加一个冠军结点。26/4129F315F417F05F110F25(-∞)5(-∞)5(-∞)5(-∞)冠军（最小者）每个叶子结点对应一个归并段，段号为0～4。初始时每个分支结点取值“5(-∞)”，5表示段号（此时为虚拟段号），-∞表示最小关键字。例如，某结点取值为“4(15)”，表示结点值来自4号段的关键字15对应的元素。27/4129F315F417F05F110F2冠军（最小者）5(-∞)5(-∞)5(-∞)5(-∞)5(-∞)4(15)3(29)4(15)2(10)1(5)0(17)4(15)1(5)败者树构建完毕调整产生冠军（最小者）的过程从F4F0操作：将当前结点的关键字与父结点比较，将大的（败者）放在父结点中，小者（胜者）继续进行，直到根结点。最后将胜者放在冠军结点中。28/4121∞29F315F417F05F110F2冠军（最小者）5(-∞)

用败者树进行归并5(-∞)5(-∞)5(-∞)5(-∞)4(15)3(29)4(15)2(10)1(5)0(17)4(15)1(5)44∞12∞15∞32∞归并文件：51(44)2(10)10依此进行，直到冠军为∞才结束。每次产生一个冠军，比较次数约为log2k。过程：取出的冠军为1(5)，从1号段中取下一个元素，沿着个分支向上操作，产生次小的元素。…29/41

logkm

×(u-1)×

log2k

=

log2m

×(u-1)×

log2k

/

log2k

=

log2m

×(u-1)利用败者树实现k路平衡归并时，总共需要的关键字比较次数为：结论：关键字比较次数与k无关

总的内部归并时间不会随k的增大而增大。

只要内存空间允许，尽可能增大归并路数k。利用败者树实现k路平衡归并30/41k路平衡归并适合初始归并段中的元素个数相同的情况，当初始归并段中的元素个数不同时，怎么办？

当初始归并段和k已确定的情况时哪些初始归并段先归并，哪些后归并的问题。归并方案转化为2.最佳归并树31/41例如：k=2，4个初始归并段含元素个数分别是4、6、3、8。4610381121

归并方式1WPL=(4+6+3+8)*2=42归并方式2346871321WPL=(3+4)*3+6*2+8=41显然采用k叉哈夫曼树的归并方案。32/41采用k叉哈夫曼树的归并方案

最佳归并树。剩下只有2个归并段了，怎么办？

存在的问题（假设k=3）：WPL最小在内存中归并时，利用败者树减少关键字比较次数33/41解决的方法是加虚段（长度为0的段），每次恰好k个段进行归并！应加(k-1)-(m-1)

Mod

(k-1)个虚段前面问题的解决方法：加上1个虚段：加多少个虚段呢？34/41

若x=(m-1)%(k-1)≠0，则需附加(k-1)-x个虚段，以使每次归并都可以对应k个段。

按照哈夫曼树的构造原则（权值越小的结点离根结点越远）构造最佳归并树。

最佳归并树（m个初始归并段）是带权路径长度最短的k叉（阶）哈夫曼树，构造步骤如下：k=2时，x=(m-1)%1=0，所以二路归并（哈夫曼树构造中）不需要增加虚段35/41

【例10.13】

设文件经预处理后，得到长度为

(49，9，35，18，4，12，23，7，21，14，26)的11个初始归并段，试为4路归并设计一个读写文件次数最少的归并方案（假如每个元素占用一个物理块）。各个初始归并段中的元素个数，而非关键字序列36/41初始归并段个数m=11，k=4。x=(m-1)%(k-1)=1≠0，因此需附加：

(k-1)-x=2个长度为0的虚