数据结构-第11章--外排序PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,11,章 外 排 序,11.1,外排序概述,11.2,磁盘排序,11.3,磁带排序,1,11.1,外排序概述,文件存储在外存上,因此外排序方法与各种外存设备的特征有关,外存设备大体上可分为两类,一类是顺序存取设备,例如磁带,另一类是直接存取设备,例如磁盘,其结构如下图所示。,2,外排序的基本方法是归并排序法。它分为以下两个步骤：,（,1,）生成若干初始归并段（顺串）：这一过程也称为文件预处理：,把含有,n,个记录的文件，按内存大小分成若干长度为,L,的子文件（归并段）；,分别将各子文件（归并段）调入内存，采用有效的内排序方法排序后送回外存。,（,2,）多路归并：对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。,3,内存,abc.dat,abc,1,.dat,abc,2,.dat,abc,n,.dat,内存,abc,1,.dat,abc,2,.dat,abc,n,.dat,abc.dat,第,1,步,第,2,步,有序,均有序,某算法,某排序算法：只能是归并算法,4,11.2,磁盘排序,11.2.1,磁盘排序过程,磁盘是直接存取设备,读,/,写一个数据块的时间与当前读,/,写头所处的位置关系不大。,通过一个例子来说明磁盘排序的过程。设有一个文件，内含,4500,个记录：,A,1,A,2,A,4500,现在要对该文件进行排序，但可占用的内存空间至多只能对,750,个记录进行排序。输入文件（被排序的文件）放在磁盘上，页块长为,250,个记录。排序过程可如下进行：,5,6,个归并段的归并过程,6,11.2.2,多路平衡归并,图中的归并过程基本上是,2,路平衡归并的算法。一般说来，如果初始归并段有,m,个，那么这样的归并树就有,log,2,m,+1,层，要对数据进行,log,2,m,遍扫描。采用,k,路平衡归并时，则相应的归并树有,log,k,m,+1,层，要对数据进行,log,k,m,遍扫描。,7,做内部归并时，在,k,个记录中选择最小者，需要顺序比较,k-1,次。每趟归并,u,个记录需要做,(u-1)*(k-1),次比较，,s,趟归并总共需要的比较次数为：,s*(u-1)*(k-1)=,log,k,m,*(u-1)*(k-1),=,log,2,m,*(u-1),*(k-1),log,2,k,其中，,log,2,m,*(u-1),在初始归并段个数,m,与记录个数,u,一定时是常量,而,(k-1),log,2,k,在,k,增大时趋于无穷大。因此增大归并路数,k,，会使内部归并的时间增大。若,k,增大到一定的程度，就会抵消掉由于减少读写磁盘次数而赢得的时间。,u,个记录,log,2,m,趟,8,下面讨论利用,败者树,实现多路平衡归并。,败者树是一棵有,k,个叶结点的完全二叉树，叶子结点存储记录，非叶结点可由关键字和它对应的记录地址构成，为讨论方便起见，设非叶结点的结构为：,关键字,输入有序段的路号,对,k,个输入有序段进行,k,路平衡归并的方法如下：,（,1,）取每个输入有序段的第一个记录作为败者树的叶子结点,建立初始败者树：两两叶结点进行比较，在双亲结点中记录比赛的败者（关键字较大者），而让胜者去参加更高一层的比赛，如此在根结点之上胜出的“冠军”是关键字最小者。,9,（,2,）胜出的记录写至输出归并段，在对应的叶结点处，补充其输入有序段的下一个记录，若该有序段变空，则补充一个大关键字（比所有记录关键字都大，设为,k,max,）的虚记录。,（,3,）调整败者树，选择新的关键字最小的记录：从补充记录的叶结点向上和双亲结点的关键字比较，败者留在该双亲结点，胜者继续向上，直至树根的双亲。,（,4,）若胜出的记录关键字等于,k,max,，则归并结束；否则转（,2,）继续。,10,例如,设有,5,个初始归并段，它们中各记录的关键字分别是：,R,1,:17,21,R,2,:5,44,R,3,:10,12,R,4,:29,32,R,5,:15,56,其中,是段结束标志。利用败者树进行,5,路平衡归并排序的过程如下图所示。,11,建立初始败者树,12,重购后的败者树（粗线部分结点发生改变）,13,从中看到，,k,路平衡归并的败者树的深度为,log,2,k,，,在每次调整找下一个具有最小关键字记录时，最多做,log,2,k,次关键字比较。因此利用败者树在,k,个记录中选择最小者，只需要进行,O(,log,2,k,),次关键字比较，这时归并总共需要的比较次数为：,s*(u-1)*,log,2,k,=,log,k,m,*(u-1)*,log,2,k,=,log,2,m,*(u-1)*,log,2,k,log,2,k,=,log,2,m,*(u-1),u,个记录,log,k,m,趟,14,这样，关键字比较次数与,k,无关，总的内部归并时间不会随,k,的增大而增大。因此只要内存空间允许，增大归并路数,k,，将有效地减少归并树的深度，从而减少读写磁盘次数，提高外排序的速度。,15,11.2.3,初始归并段的生成,采用上一章中介绍的常规内排序方法,可以实现初始归并段的生成,但所生成的归并段的大小正好等于一次能放入内存中的记录个数。显然存在局限性。,如果采用前面所述的败者树方法,可以使初始归并段的长度增大。这里介绍一种称为置换,-,选择排序方法用于生成初始归并段。,16,置换,-,选择排序生成初始归并段时，内部排序基于选择排序，同时在此过程中伴随记录的输入和输出，生成的初始归并段长度超过平均数，且长度可能各不相同。,17,（,1,）从待排文件,F,in,中按内存工作区,WA,的容量,w,读入,w,个记录。设归并段编号,i=1,。,（,2,）使用败者树从,WA,中选出关键字最小的记录,R,min,。,（,3,）将,R,min,记录输出到,F,out,中,作为当前归并段的一个成员。,（,4,）若,F,in,不空,则从,F,in,中读入下一个记录,x,放在,R,min,所在的工作区位置代替,R,min,。,（,5,）在工作区中所有大于或等于,R,min,的记录中选择出最小记录作为新的,R,min,转（,3,），直到选不出这样的,R,min,。,（,6,）设,i=i+1,开始一个新的归并段。,（,7,）若工作区已空,则初始归并段已全部产生；否则转（,2,）。,18,例,11.1,设磁盘文件中共有,18,个记录,记录的关键字分别为：,15,4,97,64,17,32,108,44,76,9,39,82,56,31,80,73,255,68,若内存工作区可容纳,5,个记录，用置换,-,选择排序可产生几个初始归并段，每个初始归并段包含哪些记录,?,19,读入记录,内存工作区状态,R,min,输出之后的初始归并段状态,15,4,97,64,17,15,4,97,64,17,4(i=1),归并段,1:4,32,15,32,97,64,17,15(i=1),归并段,1:4,15,108,108,32,97,64,17,17(i=1),归并段,1:4,15,17,44,108,32,97,64,44,32(i=1),归并段,1:4,15,17,32,76,108,76,97,64,44,44(i=1),归并段,1:4,15,17,32,44,初始归并段的生成过程,20,读入记录,内存工作区状态,R,min,输出之后的初始归并段状态,9,108,76,97,64,9,64(i=1),归并段,:,1:4,15,17,32,44,64,39,108,76,97,39,9,76(i=1),归并段,1:4,15,17,32,44,64,76,82,108,82,97,39,9,82(i=1),归并段,1:4,15,17,32,44,64,76,82,56,108,56,97,39,9,97(i=1),归并段,1:4,15,17,32,44,64,76,82,97,31,108,56,31,39,9,108(i=1),归并段,1:4,15,17,32,44,64,76,82,97,108,21,读入记录,内存工作区状态,R,min,输出之后的初始归并段状态,80,80,56,31,39,9,9(,没有大于等于,108,的记录,i=2),归并段,2:9,73,80,56,31,39,73,31(i=2),归并段,2:9,31,255,80,56,255,39,73,39(i=2),归并段,2:9,31,39,68,80,56,255,68,73,56(i=2),归并段,2:9,31,39,56,80,255,68,73,68(i=2),归并段,2:9,31,39,56,68,22,共产生两个初始归并段,:,1:4,15,17,32,44,64,76,82,97,108,2:9,31,39,56,68,73,80,255,读入记录,内存工作区状态,R,min,输出之后的初始归并段状态,80,255,73,73(i=2),归并段,2:9,31,39,56,68,73,80,255,80(i=2),归并段,2:9,31,39,56,68,73,80,255,255(i=2),归并段,2:9,31,39,56,68,73,80,255,23,11.2.4,最佳归并树,由于采用置换,-,选择排序的方法生成的初始归并段长度不等，在进行逐趟,k,路归并时对归并段的组合不同，会导致归并过程中对外存的读写次数不同。,为提高归并的时间效率，有必要对各归并段进行合理的搭配组合。按照最佳归并树的设计可以使归并过程中对外存的读写次数最少。,24,最佳归并树是带权路径长度最短的,k,叉（阶）哈夫曼树，构造步骤如下：,（,1,）若,(n-1)Mod(k-1)0,，则需附加,(k-1)-(n-1)Mod(k-1),个长度为,0,的虚段，以使每次归并都可以对应,k,个段。,（,2,）按照哈夫曼树的构造原则（权值越小的结点离根结点越远）构造最佳归并树。,25,例,11.2,设文件经预处理后,得到长度为,47,9,39,18,4,12,23,7,21,16,26,的,11,个初始归并段，试为,4,路归并设计一个读写文件次数最少的归并方案。,26,初始归并段的个数,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,阶哈夫曼树，如下图所示。,27,4,路最佳归并树,28,若每个记录占用一个物理页块,则此方案对外存的读写次数为：,2(4+7)3+,(9+12+14+18+21+23+26)2+(35+49)1,=726,次。,29,思考题：,有一组数据（含,10,亿个正整数），如何实现排序？,华为招聘笔试题。,30,