【精品】【考研计算机专业课】武汉大学数据结构PPT课件 第11章外排序精品ppt课件.ppt

《【精品】【考研计算机专业课】武汉大学数据结构PPT课件 第11章外排序精品ppt课件.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】武汉大学数据结构PPT课件 第11章外排序精品ppt课件.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【考研计算机专业课】武汉大学数据结构PPT课件 第11章 外排序11.1外排序概述外排序概述 文文件件存存储储在在外外存存上上,因因此此外外排排序序方方法法与与各各种种外外存存设设备备的的特特征征有有关关,外外存存设设备备大大体体上上可可分分为为两两类类,一一类类是是顺顺序序存存取取设设备备,例例如如磁磁带带,另另一一类类是是直直接接存存取取设设备备,例例如如磁磁盘盘,其其结结构构如下图所示。如下图所示。外排序的基本方法是归并排序法。它分为以下两个步骤：外排序的基本方法是归并排序法。它分为以下两个步骤：（1）生生成成若若干干初初始始归归并并段段（顺顺串串）：这这一一过过程程也也称称为为文文件预

2、处理：件预处理：把把含含有有n个个记记录录的的文文件件，按按内内存存大大小小分分成成若若干干长长度度为为L的子文件（归并段）；的子文件（归并段）；分分别别将将各各子子文文件件（归归并并段段）调调入入内内存存，采采用用有有效效的的内内排序方法排序后送回外存。排序方法排序后送回外存。（2）多多路路归归并并：对对这这些些初初始始归归并并段段进进行行多多遍遍归归并并，使使得得有有序序的的归归并并段段逐逐渐渐扩扩大大，最最后后在在外外存存上上形形成成整整个个文文件件的的单单一一归并段，也就完成了这个文件的外排序。归并段，也就完成了这个文件的外排序。内存内存abc.databc1.databc2.data

3、bcn.dat内存内存abc1.databc2.databcn.databc.dat第第1步步第第2步步有序有序均有序均有序某算法某算法某排序算法：只能是归并算法某排序算法：只能是归并算法11.2磁盘排序磁盘排序11.2.1磁盘排序过程磁盘排序过程磁磁盘盘是是直直接接存存取取设设备备,读读/写写一一个个数数据据块块的的时时间间与与当当前前读读/写头所处的位置关系不大。写头所处的位置关系不大。通通过过一一个个例例子子来来说说明明磁磁盘盘排排序序的的过过程程。设设有有一一个个文文件件，内内含含4500个个记记录录：A1,A2,A4500,现现在在要要对对该该文文件件进进行行排排序序，但但可可占占用

4、用的的内内存存空空间间至至多多只只能能对对750个个记记录录进进行行排排序序。输输入入文文件件（被被排排序序的的文文件件）放放在在磁磁盘盘上上，页页块块长长为为250个个记记录录。排序过程可如下进行：排序过程可如下进行：做做内内部部归归并并时时，在在k个个记记录录中中选选择择最最小小者者，需需要要顺顺序序比比较较k-1次次。每每趟趟归归并并u个记录需要做个记录需要做(u-1)*(k-1)次比较，次比较，s趟归并总共需要的比较次数为：趟归并总共需要的比较次数为：s*(u-1)*(k-1)=logkm*(u-1)*(k-1)=log2m*(u-1)*(k-1)log2k 其其中中，log2m*(u

5、-1)在在初初始始归归并并段段个个数数m与与记记录录个个数数u一一定定时时是是常常量量,而而(k-1)log2k 在在k增增大大时时趋趋于于无无穷穷大大。因因此此增增大大归归并并路路数数k，会会使使内内部部归归并并的的时时间间增增大大。若若k增增大大到到一一定定的的程程度度，就就会会抵抵消消掉掉由由于于减减少少读读写写磁磁盘盘次次数数而而赢赢得的时间。得的时间。u u个记录个记录 log2m 趟趟下面讨论利用下面讨论利用败者树败者树实现多路平衡归并。实现多路平衡归并。败者树是一棵有败者树是一棵有k个叶结点的完全二叉树，叶子结点存储个叶结点的完全二叉树，叶子结点存储记录，非叶结点可由关键字和它对

6、应的记录地址构成，为讨论记录，非叶结点可由关键字和它对应的记录地址构成，为讨论方便起见，设非叶结点的结构为：方便起见，设非叶结点的结构为：关键字关键字,输入有序段的路号输入有序段的路号对对k个输入有序段进行个输入有序段进行k路平衡归并的方法如下：路平衡归并的方法如下：（1）取取每每个个输输入入有有序序段段的的第第一一个个记记录录作作为为败败者者树树的的叶叶子子结结点点,建建立立初初始始败败者者树树：两两两两叶叶结结点点进进行行比比较较，在在双双亲亲结结点点中中记记录录比比赛赛的的败败者者（关关键键字字较较大大者者），而而让让胜胜者者去去参参加加更更高高一一层层的的比比赛，如此在根结点之上胜出的

7、赛，如此在根结点之上胜出的“冠军冠军”是关键字最小者。是关键字最小者。（2）胜胜出出的的记记录录写写至至输输出出归归并并段段，在在对对应应的的叶叶结结点点处处，补补充充其其输输入入有有序序段段的的下下一一个个记记录录，若若该该有有序序段段变变空空，则则补补充充一一个个大大关关键键字字（比比所所有有记记录录关关键键字字都都大大，设设为为kmax）的的虚虚记记录。录。（3）调调整整败败者者树树，选选择择新新的的关关键键字字最最小小的的记记录录：从从补补充充记记录录的的叶叶结结点点向向上上和和双双亲亲结结点点的的关关键键字字比比较较，败败者者留留在在该该双双亲结点，胜者继续向上，直至树根的双亲。亲结

8、点，胜者继续向上，直至树根的双亲。（4）若若胜胜出出的的记记录录关关键键字字等等于于kmax，则则归归并并结结束束；否否则则转（转（2）继续。）继续。例如例如,设有设有5个初始归并段，它们中各记录的关键字分别是：个初始归并段，它们中各记录的关键字分别是：R1:17,21,R2:5,44,R3:10,12,R4:29,32,R5:15,56,其中其中,是段结束标志。利用败者树进行是段结束标志。利用败者树进行5路平衡归并排序的路平衡归并排序的过程如下图所示。过程如下图所示。建建立立初初始始败败者者树树重购后的败者树（粗线部分结点发生改变）重购后的败者树（粗线部分结点发生改变）从从中中看看到到，k路

9、路平平衡衡归归并并的的败败者者树树的的深深度度为为 log2k，在在每每次次调调整整找找下下一一个个具具有有最最小小关关键键字字记记录录时时，最最多多做做 log2k 次次关关键键字字比比较较。因因此此利利用用败败者者树树在在k个个记记录录中中选选择择最最小小者者，只只需需要要进进行行O(log2k)次次关关键键字字比比较较，这时归并总共需要的比较次数为：这时归并总共需要的比较次数为：s*(u-1)*log2k=logkm*(u-1)*log2k=log2m*(u-1)*log2k log2k=log2m*(u-1)u u个记录个记录 logkm 趟趟这这样样，关关键键字字比比较较次次数数与与

10、k无无关关，总总的的内内部部归归并并时时间间不不会会随随k的的增增大大而而增增大大。因因此此只只要要内内存存空空间间允允许许，增增大大归归并并路路数数k，将将有有效效地地减减少少归归并并树树的的深深度度，从从而而减减少少读读写写磁磁盘盘次次数数，提提高高外外排排序的速度。序的速度。11.2.3初始归并段的生成初始归并段的生成采采用用上上一一章章中中介介绍绍的的常常规规内内排排序序方方法法,可可以以实实现现初初始始归归并并段段的的生生成成,但但所所生生成成的的归归并并段段的的大大小小正正好好等等于于一一次次能能放放入入内内存存中中的的记录个数。显然存在局限性。记录个数。显然存在局限性。如如果果采

11、采用用前前面面所所述述的的败败者者树树方方法法,可可以以使使初初始始归归并并段段的的长长度度增增大大。这这里里介介绍绍一一种种称称为为置置换换-选选择择排排序序方方法法用用于于生生成成初初始始归归并并段。段。置置换换-选选择择排排序序生生成成初初始始归归并并段段时时，内内部部排排序序基基于于选选择择排排序序，同同时时在在此此过过程程中中伴伴随随记记录录的的输输入入和和输输出出，生生成成的的初始归并段长度超过平均数，且长度可能各不相同。初始归并段长度超过平均数，且长度可能各不相同。（1）从从待待排排文文件件Fin中中按按内内存存工工作作区区WA的的容容量量w读读入入w个个记记录。设归并段编号录。

12、设归并段编号i=1。（2）使用败者树从）使用败者树从WA中选出关键字最小的记录中选出关键字最小的记录Rmin。（3）将）将Rmin记录输出到记录输出到Fout中中,作为当前归并段的一个成员。作为当前归并段的一个成员。（4）若若Fin不不空空,则则从从Fin中中读读入入下下一一个个记记录录x放放在在Rmin所所在在的的工作区位置代替工作区位置代替Rmin。（5）在在工工作作区区中中所所有有大大于于或或等等于于Rmin的的记记录录中中选选择择出出最最小小记录作为新的记录作为新的Rmin,转（转（3），直到选不出这样的），直到选不出这样的Rmin。（6）设）设i=i+1,开始一个新的归并段。开始一个

13、新的归并段。（7）若若工工作作区区已已空空,则则初初始始归归并并段段已已全全部部产产生生；否否则则转转（2）。）。例例11.1设磁盘文件中共有设磁盘文件中共有18个记录个记录,记录的关键字分别为：记录的关键字分别为：15,4,97,64,17,32,108,44,76,9,39,82,56,31,80,73,255,68若内存工作区可容纳若内存工作区可容纳5个记录，用置换个记录，用置换-选择排序可产生几选择排序可产生几个初始归并段，每个初始归并段包含哪些记录个初始归并段，每个初始归并段包含哪些记录?读入记录读入记录内存工作区状态内存工作区状态Rmin输出之后的初始归输出之后的初始归并段状态并段

14、状态15,4,97,64,1715,4,97,64,174(i=1)归并段归并段1:43215,32,97,64,1715(i=1)归并段归并段1:4,15108108,32,97,64,1717(i=1)归并段归并段1:4,15,1744108,32,97,64,4432(i=1)归并段归并段1:4,15,17,3276108,76,97,64,4444(i=1)归并段归并段1:4,15,17,32,44初始归并段的生成过程初始归并段的生成过程 读入记读入记录录内存工作区状态内存工作区状态Rmin输出之后的初始归并段状态输出之后的初始归并段状态9108,76,97,64,964(i=1)归并

15、段归并段:1:4,15,17,32,44,6439108,76,97,39,976(i=1)归并段归并段1:4,15,17,32,44,64,7682108,82,97,39,982(i=1)归并段归并段1:4,15,17,32,44,64,76,8256108,56,97,39,997(i=1)归并段归并段1:4,15,17,32,44,64,76,82,9731108,56,31,39,9108(i=1)归并段归并段1:4,15,17,32,44,64,76,82,97,108读入读入记录记录内存工作区状态内存工作区状态Rmin输出之后的初始归并段状输出之后的初始归并段状态态8080,56

16、,31,39,99(没没有有大大于于等等于于108的记录的记录,i=2)归并段归并段2:97380,56,31,39,7331(i=2)归并段归并段2:9,3125580,56,255,39,7339(i=2)归并段归并段2:9,31,396880,56,255,68,7356(i=2)归并段归并段2:9,31,39,5680,255,68,7368(i=2)归并段归并段2:9,31,39,56,68共产生两个初始归并段共产生两个初始归并段:1:4,15,17,32,44,64,76,82,97,108,2:9,31,39,56,68,73,80,255读入记录读入记录内存工作区状态内存工作区

17、状态Rmin输出之后的初始归并段状输出之后的初始归并段状态态80,255,7373(i=2)归并段归并段2:9,31,39,56,68,7380,255,80(i=2)归并段归并段2:9,31,39,56,68,73,80,255,255(i=2)归并段归并段2:9,31,39,56,68,73,80,25511.2.4最佳归并树最佳归并树 由由于于采采用用置置换换-选选择择排排序序的的方方法法生生成成的的初初始始归归并并段段长长度度不不等等，在在进进行行逐逐趟趟k路路归归并并时时对对归归并并段段的的组组合合不不同同，会会导导致致归归并过程中对外存的读写次数不同。并过程中对外存的读写次数不同。

18、为为提提高高归归并并的的时时间间效效率率，有有必必要要对对各各归归并并段段进进行行合合理理的的搭搭配配组组合合。按按照照最最佳佳归归并并树树的的设设计计可可以以使使归归并并过过程程中中对对外外存存的的读写次数最少。读写次数最少。最最佳佳归归并并树树是是带带权权路路径径长长度度最最短短的的k叉叉（阶阶）哈哈夫夫曼曼树树，构造步骤如下：构造步骤如下：（1）若若(n-1)Mod(k-1)0，则则需需附附加加(k-1)-(n-1)Mod(k-1)个长度为个长度为0的虚段，以使每次归并都可以对应的虚段，以使每次归并都可以对应k个段。个段。（2）按按照照哈哈夫夫曼曼树树的的构构造造原原则则（权权值值越越小

19、小的的结结点点离离根根结结点越远）构造最佳归并树。点越远）构造最佳归并树。例例11.2设文件经预处理后设文件经预处理后,得到长度为得到长度为47,9,39,18,4,12,23,7,21,16,26的的11个初始归并段，试为个初始归并段，试为4路归并设计一个读写文件次数最少路归并设计一个读写文件次数最少的归并方案。的归并方案。初始归并段的个数初始归并段的个数n=11，归并路数，归并路数k=4，由于，由于(n-1)Mod(k-1)=1，不为，不为0，因此需附加：，因此需附加：(k-1)-(n-1)Mod(k-1)=2个长度为个长度为0的虚段。根据集合：的虚段。根据集合：49,9,35,18,4,12,23,7,21,14,26,0,0构造构造4阶哈夫曼树，如下图所示。阶哈夫曼树，如下图所示。4 4路最佳归并树路最佳归并树 若若每每个个记记录录占占用用一一个个物物理理页页块块,则则此此方方案案对对外外存存的的读读写写次次数为：数为：2(4+7)3+(9+12+14+18+21+23+26)2+(35+49)1=726次。次。思考题：思考题：有一组数据（含有一组数据（含10亿个正整数），如何实现排序？亿个正整数），如何实现排序？华为招聘笔试题。华为招聘笔试题。