第十一章 外部排序

本文格式为Word版，下载可任意编辑——第十一章外部排序

第十一章外部排序外存信息的存取外部排序的方法多路平衡归并的实现置换——选择排序最正确归并树

11.1外部信息的存取计算机一般有两种存储器：内存储器(主存)和外存储器(辅存)。内存的信息可随机存取，且存取速度快，但价格贵。容量小。外存储器包括磁带和磁盘(或磁鼓),前者为顺序存取的设备，后者为随机存取的设备。1.磁带信息的存取2.磁盘信息的存取3.光盘信息的存取

11.2外部排序的方法外部排序基本上由两个相对独立的阶段组成。

1.按可以用内存大小，将外存上含n个记录的文件分成若干长度为L的子文件或段(segment),依次读入内存并利用有效的内部排序方法对它们进行排序，2.将排序后得到的有序子文件重新写入外存，寻常称这些有序子文件为归并段或顺串(run);然后，对这些归并进行逐趟归并，使归并段(有序的子文件)逐渐有小变大，直至得到整个有序文件为止。

11.2外部排序的方法一般状况下，外部排序所需总的时间

=内部排序所需的时间+外存信息读写的时间+内部归并所需的时间

m*tisd*tIOs*utmg

其中：tis是为得到一个初始归并段进行排序所需时间的均值；tIO是进行一次外存读/写时间的均值；

utmg是对u个记录进行内部归并所需时间；m为经过内部排序之后得到的初始归并段的个数；s为归并的趟数；d为总的读/写次数。

11.2外部排序的方法例:有10000条记录,通过10次内部排序得到10个初始归并段R1-R10,每段有1000条记录.

R1

R2R3R4R5R6R7R8R9R10R2’R1’’R1’’’有序文件R3’R2’’R4’R5’R3’’R2’’’

R1’

11.2外部排序的方法从上例中我们可以得到:一共归并了4趟

外存信息读写500次问题:是否可以改进减少外存信息读写?可以采用多路归并即:R1R2R3R4R5R6R7R8R9R10R1’有序文件R2’

一共归并了2趟,外存读写300次

11.2外部排序的方法结论:对同一文件,进行外部排序时所需读写外存的次数和归并趟数s成正比.对m个初始归并段进行k-路平衡归并时,归并趟数为:s=向上取整(logkm)显然:增加k可以减少s

11.3多路平衡归并的实现为了减少归并趟数,我们增大k.问题:增大了k又会出现新的问题.增加内部归并所需的时间,由于比较的元素多了,比较的次数也就多了.为减少比较次数,解决方法我们引出:败者树.败者树：在双亲结点中记录下来刚进行完的这场比赛中的败者，而让胜者去参与更高一层的比赛，便可得到一棵“败者树〞。

11.3多路平衡归并的实现例:31

胜利者

失败者0b0b3661525.

2b1991820.b

220

4

b412123748.

10

101516.

202240.

11.3多路平衡归并的实现例:1301

胜利者

失败者40b0b3151525.

2b1991820.b220

34

b412123748.

10

101516.

202240.

11.4置换-选择排序问题:是否可以不用内部排序构造初始归并段?例:若初始文件含有24个记录，其的关键字为:51,49,39,46,38,29,14,61,15,1,48,52,3,63,27,4,1389,24,46,58,33,76。假设内存工作区可容纳6个记录，则可得如下4个初始归并段：RUN1:29,38,39,46,49,51RUN2:1,14,15,30,48,61RUN3:3,4,13,27,52,63RUN4:24,33,46,58,76,89

11.4置换-选择排序置换-选择排序就是新的构造方法:上例用此法,可求得如下3个初始归并段：RUN1:29,38,39,46,49,51,61RUN2:1,3,14,15,27,30,48,52,63,89RUN3:4,13,24,33,46,58,76

问题:怎样构造呢?

置换-选择排序算法思想:初始化:输入文件FI,输出文件FO,内存工作区为WA.FO和WA置空，内存工作区为空，WA的容量可容纳w个记录.(1)从FI输入w个记录到工作区WA。(2)从WA中选出最小关键字记录，记MIN记录。(3)将MIN输出到FO中去。(4)若FI不为空，则从FI输入下一个记录到WA中。(5)从WA中所有关键字比MIN大的记录中选出最小关键字记录，作为新的MIN记录。(6)重复(3)—(5),直至在WA中选不出新的MIN为止，则得一初始归并段，输出之。(7)重复(2)—(6),直至WA为空。则得全部初始归并段。

FO空空292929,3829,38

WA空51,49,39,46,38,2951,49,39,46,3851,49,39,46,38,1451,49,39,46,,1451,49,39,46,61,14

FI51,49,39,46,38,29,14,61,15,30,1,48,52,…14,61,15,30,1,48,52,3,63,27,4,…14,61,15,30,1,48,52,3,63,27,4,…61,15,30,1,48,52,3,63,27,4,…61,15,30,1,48,52,3,63,27,4,…15,30,1,48,52,3,63,27,4,…

29,38,3929,38,3929,38,39,4629,38,39,4629,38,39,46,4929,38,39,46,49,51

51,49,,46,61,1451,49,15,46,61,1451,49,15,,61,1451,49,15,30,61,1451,1,15,30,61,1448,1,15,30,61,14

15,30,1,48,52,3,63,27,4,…30,1,48,52,3,63,27,4,…30,1,48,52,3,63,27,4,…1,48,52,3,63,27,4,…48,52,3,63,27,4,…52,3,63,27,4,…

FO29,38,39,46,49,51,61

WA48,1,15,30,52,143,63,27,4,…

FI3,63,27,4,…63,27,4,…27,4,…4,……………

29,38,39,46,49,51,6148,1,15,30,52,1411,31,3,141,3,14,15……

48,3,15,30,52,1448,63,15,30,52,1448,63,15,30,52,2748,63,4,30,52,27……

RUN1:29,38,39,46,49,51,61

结论:

RUN2:1,3,14,15,27,30,48,52,63,89RUN3:4,13,24,33,46,58,76

11.5最正确归并树问题:由置换-选择生成所得的初始归并段，其各段长度不等对平衡归并有何影响？假设由置换-选择得到9个初始归并段，其长度(即记录数)依次为：9,30,12,18,3,17,2,6,24。现作3-路平衡归并，其归

并树如下图：93012183172624

51

38

32

121

假设每个记录占一个物理块，则两趟归并所需对外存进行的读/写次数为(9+30+12+18+3+17+2+6+24)*2*2=484显然，归并方案不同，所得归并树亦不同，树的带权路径长度(或外存读/写次数)亦不同。回想在第六章中哈夫曼树构造方法。可得如下图所示：3-路平衡归并的最正确归并树(446次读/写)29311612171824

30