第14周外排序第5讲-本周小结.pdf

《第14周外排序第5讲-本周小结.pdf》由会员分享，可在线阅读，更多相关《第14周外排序第5讲-本周小结.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1外排序概述 排序数据存放在外存上排序数据存放在外存上 排序结果存放在外存上排序结果存放在外存上 排序过程借助内存实现排序过程借助内存实现 存在内、外存数据交换（多）存在内、外存数据交换（多） 存在关键字比较（多）存在关键字比较（多） 存在元素移动（少）存在元素移动（少） 外排序时间外排序时间=内、外存数据交换内、外存数据交换 +关键字比较关键字比较 1/11 2磁 盘 排 序 通过分割要排序的文件，生成多个通过分割要排序的文件，生成多个初始归并段初始归并段 对初始归并段进行对初始归并段进行多路归并，多路归并，产生一个有序文件产生一个有序文件 2/11 常规方法：常规方法： 内存大小为内存大小

2、为w，每次从外存文件，每次从外存文件in.dat中读入中读入w个记录，采用某种个记录，采用某种 内排序方法进行排序来产生初始归并段，即产生内排序方法进行排序来产生初始归并段，即产生out1.dat、 outn.dat有序文件有序文件 置换置换- -选择算法选择算法 产生初始归并段个数为产生初始归并段个数为 n/w ，长度基本相同，长度基本相同 产生初始归并段个数产生初始归并段个数 n/w ，长度差异比较大长度差异比较大 3/11 多路平衡归并：多路平衡归并： k=2 记录读写次数记录读写次数 = WPL k越大越大WPL越小越小 4/11 k路归并中：大量的操作是从路归并中：大量的操作是从k个

3、记录中找出最小的记录个记录中找出最小的记录 采用简单比较实现采用简单比较实现 效率低效率低 采用类似堆的方式即采用类似堆的方式即败者树败者树 效率高效率高 归并中关键字比较次数与归并中关键字比较次数与k无关无关 尽可能增加尽可能增加k提高外排序效率提高外排序效率 5/11 按最佳归并树进行归并：按最佳归并树进行归并： 根据初始归并段（个数根据初始归并段（个数m和每个初始归并段中记录数）和每个初始归并段中记录数） 和和k构造最佳归并树。构造最佳归并树。 按照其过程进行归并。按照其过程进行归并。 6/11 设有设有11个初始归并段，它们所包含的记录个数为个初始归并段，它们所包含的记录个数为25，4

4、0， 16，38，77，64，53，88，9，48，98。试根据它们做。试根据它们做4路归路归 并，要求：并，要求： （1）指出采用）指出采用4路平衡归并时总的归并趟数。路平衡归并时总的归并趟数。 （2）给出采用）给出采用4路平衡归并时的归并过程。路平衡归并时的归并过程。 （3）构造最佳归并树。）构造最佳归并树。 （4）根据最佳归并树计算每一趟及总的读记录数。）根据最佳归并树计算每一趟及总的读记录数。 7/11 解：解：（1）采用采用4路平衡归并时，路平衡归并时，m=11，k=4，总的归并趟，总的归并趟 数数= logkm = log411 =2。 （2）采用采用4路平衡归并时路平衡归并时的归

5、并过程如下（归并段编号的归并过程如下（归并段编号111）：）： 1234567891011 没有考虑归并顺序没有考虑归并顺序 多路平衡归并适合长度相同的归并段多路平衡归并适合长度相同的归并段 8/11 （3）构造最佳归并树。）构造最佳归并树。 m=11，k=4，(m-1) % (k-1)=10，需要附加，需要附加k-1-(m-1) % (k-1)=2个个 长度为长度为0的虚归并段，最佳归并树如下。的虚归并段，最佳归并树如下。 91600 25 253840 128 48536477 2428898 556 9/11 91600 25 253840 128 48536477 2428898 55

6、6 （4）根据最佳归并树计算每一趟及总的读记录数：）根据最佳归并树计算每一趟及总的读记录数： 第第1趟的读记录数趟的读记录数=9+16=25 第第2趟的读记录数趟的读记录数=25+25+38+40+48+53+64+77=370 第第3趟的读记录数趟的读记录数=128+88+242+98=556 总的读记录数总的读记录数=25+370+556=951。 WPL最小最小 10/11 生成多个初始归并段采用常规方法，产生长度相同的归并段 宜 采用多路平衡归并（归并中用败者树） 生成多个初始归并段采用置换-选择算法，产生长度不相同的归并 段 宜采用最佳归并树方案（归并中用败者树） 归纳： 11/11