数据结构第12章外排序

1、第第1212章章 外外 排排 序序 12.1 12.1 外排序概述外排序概述12.2 12.2 磁盘排序磁盘排序12.3 12.3 磁带排序磁带排序本章小结本章小结12.1 12.1 外排序概述外排序概述 文件存储在外存上文件存储在外存上, ,因此外排序方法与各种因此外排序方法与各种外存设备的特征有关外存设备的特征有关, ,外存设备大体上可分为两外存设备大体上可分为两类类, ,一类是顺序存取设备一类是顺序存取设备, ,例如磁带例如磁带, ,另一类是直另一类是直接存取设备接存取设备, ,例如磁盘例如磁盘, ,其结构如下图所示。其结构如下图所示。 柱面 磁道 盘片 读写头 主轴 外排序的基本方法是

2、归并排序法。它分为以下外排序的基本方法是归并排序法。它分为以下两个步骤：两个步骤： (1) 生成若干初始归并段生成若干初始归并段(顺串顺串),这一过程也称为这一过程也称为文件预处理：文件预处理： 把含有把含有n个记录的文件个记录的文件,按内存大小分成若干按内存大小分成若干长度为长度为l的子文件的子文件(段段)； 分别将各子文件分别将各子文件(段段)调入内存调入内存,采用有效的内采用有效的内排序方法排序后送回外存。排序方法排序后送回外存。 (2) 多路归并：对这些初始归并段进行多遍归并多路归并：对这些初始归并段进行多遍归并,使得有序的归并段逐渐扩大使得有序的归并段逐渐扩大,最后在外存上形成整个最

3、后在外存上形成整个文件的单一归并段文件的单一归并段,也就完成了这个文件的外排序。也就完成了这个文件的外排序。12.2 12.2 磁盘排序磁盘排序12.2.1 12.2.1 磁盘排序过程磁盘排序过程 磁盘是直接存取设备磁盘是直接存取设备,读读/写一个数据块的时间写一个数据块的时间与当前读与当前读/写头所处的位置关系不大。写头所处的位置关系不大。 我们通过一个例子来说明磁盘排序的过程。设我们通过一个例子来说明磁盘排序的过程。设有一个文件有一个文件,内含内含4500个记录：个记录：a1,a2,a4500,现在现在要对该文件进行排序要对该文件进行排序,但可占用的内存空间至多只但可占用的内存空间至多只能

4、对能对750个记录进行排序。输入文件个记录进行排序。输入文件(被排序的文件被排序的文件)放在磁盘上放在磁盘上,页块长为页块长为250个记录。排序过程可如下个记录。排序过程可如下进行：进行： r1 r2 r3 r4 r5 r6 r1 r2 r3 r1 r1 6个归并段的归并过程个归并段的归并过程 12.2.2 12.2.2 多路平衡归并多路平衡归并 上上图所示的归并过程基本上是图所示的归并过程基本上是2路平衡归并的算路平衡归并的算法。一般说来法。一般说来,如果初始归并段有如果初始归并段有m个个,那么这样的归那么这样的归并树就有并树就有 log2m +1层层,要对数据进行要对数据进行 log2m

5、遍扫描。遍扫描。采用采用k路平衡归并时路平衡归并时,则相应的归并树有则相应的归并树有 logkm +1层层,要对数据进行要对数据进行 logkm 遍扫描。遍扫描。 做内部归并时做内部归并时,在在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-1)在初始归并段个数在初始归并段个

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

7、讨论方便起见为讨论方便起见,设非叶结点的结构为：设非叶结点的结构为： 关键字关键字,输入有序段的路号输入有序段的路号 对对k个输入有序段进行个输入有序段进行k路平衡归并的方法如下：路平衡归并的方法如下： (1) 取每个输入有序段的第一个记录作为败者树的取每个输入有序段的第一个记录作为败者树的叶子结点叶子结点,建立初始败者树：两两叶结点进行比较建立初始败者树：两两叶结点进行比较,在在双亲结点中记录比赛的败者双亲结点中记录比赛的败者(关键字较大者关键字较大者),而让胜者而让胜者去参加更高一层的比赛去参加更高一层的比赛,如此在根结点之上胜出的如此在根结点之上胜出的“冠冠军军”是关键字最小者。是关键字

8、最小者。 (2) 胜出的记录写至输出归并段胜出的记录写至输出归并段,在对应的叶结点在对应的叶结点处处,补充其输入有序段的下一个记录补充其输入有序段的下一个记录,若该有序段变空若该有序段变空,则补充一个大关键字则补充一个大关键字(比所有记录关键字都大比所有记录关键字都大,设为设为kmax)的虚记录。的虚记录。 (3) 调整败者树调整败者树,选择新的关键字最小的记录：从选择新的关键字最小的记录：从补充记录的叶结点向上和双亲结点的关键字比较补充记录的叶结点向上和双亲结点的关键字比较,败败者留在该双亲结点者留在该双亲结点,胜者继续向上胜者继续向上,直至树根的双亲。直至树根的双亲。 (4) 若胜出的记录

9、关键字等于若胜出的记录关键字等于kmax,则归并结束；则归并结束；否则转否则转(2)继续。继续。 例如例如,设有设有5个初始归并段个初始归并段,它们中各记录的关键字分它们中各记录的关键字分别是：别是： r1:17,21, r2:5,44, r3:10,12, r4:29,32, r5:15,56, 其中其中,是段结束标志。利用败者树进行是段结束标志。利用败者树进行5路平衡归路平衡归并排序的过程如下图所示。并排序的过程如下图所示。 5,2 15,5 10,3 17,1 29 32 15 56 冠军（最小者冠军（最小者） (a) 5 路归并败者树路归并败者树 (b) 重购后的败者树（标重购后的败者

10、树（标*结点发生改变）结点发生改变） 17 21 5 44 10 12 4 5 1 2 3 5 17 29,4 29 10 15 10,3 15,5 17,1 44,2 29 32 15 56 冠军（最小者）冠军（最小者） 17 21 44 10 12 4 5 1 2 3 44 17 29,4 29 10 15 * * * * 从上例看到从上例看到,k路平衡归并的败者树的深度为路平衡归并的败者树的深度为 log2k ,在每次调整找下一个具有最小关键字记录时在每次调整找下一个具有最小关键字记录时,最多做最多做 log2k 次关键字比较。因此次关键字比较。因此,利用败者树在利用败者树在k个个记录中

11、选择最小者记录中选择最小者,只需要进行只需要进行o( log2k )次关键字比次关键字比较较,这时归并总共需要的比较次数为：这时归并总共需要的比较次数为： s*(u-1)* log2k = logkm *(u-1)* log2k = log2m *(u-1)* log2k log2k = log2m *(u-1) 这样这样,关键字比较次数与关键字比较次数与k无关无关,总的内部归并时总的内部归并时间不会随间不会随k的增大而增大。因此的增大而增大。因此,只要内存空间允许只要内存空间允许,增大归并路数增大归并路数k,将有效地减少归并树的深度将有效地减少归并树的深度,从而减从而减少读写磁盘次数少读写磁

12、盘次数,提高外排序的速度。提高外排序的速度。12.2.3 12.2.3 初始归并段的生成初始归并段的生成 采用上一章中介绍的常规内排序方法采用上一章中介绍的常规内排序方法,可以实现初可以实现初始归并段的生成始归并段的生成,但所生成的归并段的大小正好等于一但所生成的归并段的大小正好等于一次能放入内存中的记录个数。显然存在局限性。如果次能放入内存中的记录个数。显然存在局限性。如果采用前面所述的败者树方法采用前面所述的败者树方法,可以使初始归并段的长度可以使初始归并段的长度增大。这里介绍一种称为置换增大。这里介绍一种称为置换-选择排序方法用于生成选择排序方法用于生成初始归并段。初始归并段。 置换置换

13、-选择排序选择排序生成初始归并段时生成初始归并段时,内部排序基内部排序基于选择排序于选择排序,同时在此过程中伴随记录的输入和同时在此过程中伴随记录的输入和输出输出,生成的初始归并段长度超过平均数生成的初始归并段长度超过平均数,且长度且长度可能各不相同。可能各不相同。 (1) 从待排文件从待排文件fin中按内存工作区中按内存工作区wa的容量的容量w读读入入w个记录。设归并段编号个记录。设归并段编号i=1。 (2) 使用败者树从使用败者树从wa中选出关键字最小的记录中选出关键字最小的记录rmin。 (3) 将将rmin记录输出到记录输出到fout中中,作为当前归并段的作为当前归并段的一个成员。一个

14、成员。 (4) 若若fin不空不空,则从则从fin中读入下一个记录中读入下一个记录x放在放在rmin所在的工作区位置代替所在的工作区位置代替rmin。 (5) 在工作区中所有大于或等于在工作区中所有大于或等于rmin的记录中选择的记录中选择出最小记录作为新的出最小记录作为新的rmin,转转(3),直到选不出这样的直到选不出这样的rmin。 (6) 设设i=i+1,开始一个新的归并段。开始一个新的归并段。 (7) 若工作区已空若工作区已空,则初始归并段已全部产生；否则则初始归并段已全部产生；否则转转(2)。 例例12.1 设磁盘文件中共有设磁盘文件中共有18个记录个记录,记录的关键字记录的关键字

15、分别为：分别为：15,4,97,64,17,32,108,44,76,9,39,82,56,31,80,73,255,68 若内存工作区可容纳若内存工作区可容纳5个记录个记录,用用置换置换-选择排序选择排序可产生几个初始归并段可产生几个初始归并段,每个初始归并段包含哪些记每个初始归并段包含哪些记录录? 读入记录读入记录内存工作区状态内存工作区状态rmin输出之后的初输出之后的初始归并段状态始归并段状态15,4,97,64,17 15,4,97,64,174(i=1)归并段归并段1:43215,32,97,64,1715(i=1)归并段归并段1:4,15108108,32,97,64,1717(

16、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) 归并段归并段: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)

17、归并段归并段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,31,39,99(没有大于等没有大于等于于 1 0 8 的 记的 记录录,i=2)归并段归并段2:97380,56,31,39,7331(i=2)归并段归并段2:9,31 25580,56

18、,255,39,7339(i=2)归并段归并段2:9,31,39 6880,56,255,68,7356(i=2)归并段归并段2:9,31,39,56 80,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读入记录读入记录 内存工作区状内存工作区状态态rmin输出之后的初始归并输出之后的初始归并段状态段状态80,255,7373(i=2)归并段归并段2:9,31,39,56,68,73 80,255,80(i

19、=2)归并段归并段2:9,31,39,56,68,73,80 ,255,255(i=2)归并段归并段2:9,31,39,56,68,73,80,255 12.2.4 12.2.4 最佳归并树最佳归并树 由于采用置换由于采用置换-选择排序的方法生成的初始归并选择排序的方法生成的初始归并段长度不等段长度不等,在进行逐趟在进行逐趟k路归并时对归并段的组合路归并时对归并段的组合不同不同,会导致归并过程中对外存的读写次数不同。会导致归并过程中对外存的读写次数不同。为提高归并的时间效率为提高归并的时间效率,有必要对各归并段进行合理有必要对各归并段进行合理的搭配组合。按照最佳归并树的设计可以使归并过的搭配组

20、合。按照最佳归并树的设计可以使归并过程中对外存的读写次数最少。程中对外存的读写次数最少。 最佳归并树是带权路径长度最短的最佳归并树是带权路径长度最短的k叉叉(阶阶)哈夫哈夫曼树曼树,构造步骤如下：构造步骤如下： (1) 若若(n-1)%(k-1)0,则需附加则需附加(k-1)-(n-1)%(k-1)个长度为个长度为0的虚段的虚段,以使每次归并都可以对应以使每次归并都可以对应k个段。个段。 (2) 按照哈夫曼树的构造原则按照哈夫曼树的构造原则(权值越小的结点离权值越小的结点离根结点越远根结点越远)构造最佳归并树。构造最佳归并树。例例12.2 设文件经预处理后设文件经预处理后,得到长度为得到长度为

21、 47,9,39,18,4,12,23,7,21,16,26的的11个初始归并段个初始归并段,试为试为4路归并设计一个读写文件次路归并设计一个读写文件次数最少的归并方案。数最少的归并方案。 初始归并段的个数初始归并段的个数n=11,归并路数归并路数k=4,由于由于(n-1)%(k-1)=1,不为不为0,因此需附加：因此需附加： (k-1)-(n-1)%(k-1)=2个长度为个长度为0的虚段。根据集合：的虚段。根据集合： 49,9,35,18,4,12,23, 7,21,14,26,0,0构造构造4阶哈夫曼树阶哈夫曼树,如下图所示。如下图所示。 49 35 26 23 18 21 14 12 9

22、 7 4 0 0 88 218 11 46 4 4路最佳归并树路最佳归并树 若每个记录占用一个物理页块若每个记录占用一个物理页块, ,则此方案对外存则此方案对外存的读写次数为：的读写次数为： 2(4+7)3+ (9+12+14+18+21+23+26)2+(35+49)1 =726次。次。12.3 12.3 磁带排序磁带排序 由于磁带的特性不同于磁盘的特性由于磁带的特性不同于磁盘的特性,所以两者采用所以两者采用的外排序方法也不尽相同。的外排序方法也不尽相同。12.3.1 12.3.1 多路平衡归并排序多路平衡归并排序 磁带多路平衡归并排序过程与磁盘的多路平衡归磁带多路平衡归并排序过程与磁盘的多

23、路平衡归并排序过程基本上相同。先对输入文件的各段进行并排序过程基本上相同。先对输入文件的各段进行内排序内排序,生成初始归并段生成初始归并段,再把它们写到磁带上再把它们写到磁带上,然后再然后再把这些归并段进行反复的归并把这些归并段进行反复的归并,直到只剩下一个归并直到只剩下一个归并段段(即为排好序的文件即为排好序的文件)为止。为止。 我们先看一个我们先看一个2路归并磁带排序的例子路归并磁带排序的例子,了解磁带了解磁带排序所涉及的各种因素。排序所涉及的各种因素。 设有一个文件包含设有一个文件包含4500个记录个记录,现在要对其进行排现在要对其进行排序序,可供使用的磁带有四台可供使用的磁带有四台t1