数据结构 外部分类

第一页，共二十页，编辑于2023年，星期三例：假设一个磁盘文件，由4500个记录组成，分别记为A1,A2,……,A4500

设系统提供容纳750个记录的内存共分类使用，每次磁盘读写250个记录的数据块，则可设计分类过程如下：7.1磁盘文件的归并分类(1)每次从文件中输入三个数据块（750个记录）到工作空间，进行内部分类。分类结果写回磁盘，构成6个初始归并段：R1,R2,R3,R4,R5,R6R1R2R3R4R5R61-750751-15001501-22502251-30003001-37503751-4500（2）将内存空间三等分，每块250个记录，其中2块为输入缓冲区，1块为输出缓冲区。归并R1和R2，输出到输出缓冲区，若输出缓冲区满，则写盘。同样，若

R1和R2的缓冲区出现空，则继续读盘，直到归并结束为止。R12=R1+R2；同样得到：R34=R3+R4,R56=R5+R6；

R12、R34、R56分别都包含1500个记录。第二页，共二十页，编辑于2023年，星期三（3）类似（2）的方法，可将R12和R34归并成R1234,，再将R1234和R56进行归并。得到最后的排序结果。R1R2R3R4R5R6R12R34R56R1234R12346×750记录3×1500记录12×250记录18×250记录第三页，共二十页，编辑于2023年，星期三K路归并……...遍数[log2m]层数[log2m]+1M个归并段的归并过程R1R1Rm-1Rm第四页，共二十页，编辑于2023年，星期三2…KK+1…2K……m...logkm+1levers(1)多路归并——减少归并遍数并行操作的缓冲区处理——使输入、输出和CPU处理尽可能重叠(3)初始归并段的生成讨论问题logkm遍比较次数：第五页，共二十页，编辑于2023年，星期三(1)多路归并——减少归并遍数m个初始段进行2路归并，需要log2m遍归并;一般地，m个初始段，采用k路归并，需要logkm遍归并。显然，k越大，归并遍数越少，可提高归并的效率。在k路归并时，从k个关键字中选择最小记录时，要比较K-1次。若记录总数为n，每遍要比较的次数为：

n*(k-1)[log2m/log2k]可以看出，随着k增大，(k-1)/log2k也增大，当归并路数多时，CPU处理的时间也随之增多。为此要选择好的分类方法，以减少分类中比较次数。第六页，共二十页，编辑于2023年，星期三610920689901796817681516203820301525155011161001101820选择树(Selectiontree)或败者树(treeofloser)分析：第一次建立选择树的比较所花时间为:O(k-1)=O(k)而后每次重新建造选择树所需时间为：

O(log2k)n个记录处理时间为初始建立选择树的时间加上n-1次重新选择树的时间：

O((n-1)·

log2k)+O(k)=O(n·

log2k)这就是k路归并一遍所需的CPU处理时间。归并遍数为logkm，总时间为：

O(n·

log2k·

logkm)=O(n·log2m)(k路归并CPU时间与k无关)第七页，共二十页，编辑于2023年，星期三最佳归并树将哈夫曼树进行拓展，不仅对二叉树，同样可形成三叉、四叉、……、k叉树，亦称为哈夫曼树，同样可求得带权路径长度最小。最佳归并树：对长度不等的m个初始归并段，构造哈夫曼树作为归并树，便可使在进行外部归并时所需要对外存进行的读写次数达到最小。最佳归并树中，并不只是只有度为k和0的结点，会有缺额。当初始归并段的数目不足时，需附加长度为0的虚段，按照哈夫曼树的构造原则，权为0的叶子结点应离树根最远。若(m-1)%(k-1)==0

则不需要附加虚段；否则需要附加：

k-(m-1)%(k-1)-1

个虚段。第一次归并的路数为：(m-1)%(k-1)+1第八页，共二十页，编辑于2023年，星期三并行操作的缓冲区处理——使输入、输出和CPU处理尽可能重叠----1324ou(1)ou(2)iu(1)iu(2)----iu(3)iu(4)12---3-457--34----57615归并到ou(1)输入到in(3)归并到ou(2)输入到in(4)输出ou(1)(a)(b)(c)56

89---7-15

78-92025---159-

--2025

-15归并到ou(1)输入到in(1)归并到ou(1)输入到in(3)输出ou(2)(d)(e)(f)归并到ou(2)输入到in(2)输出ou(1)输出ou(2)对k个归并段进行k路归并至少需要k个输入和1个输出缓冲区，要使输入、输出和归并同时进行，k+1个缓冲区是不够的，需要2k个输入缓冲区实现并行操作。135789246152025第九页，共二十页，编辑于2023年，星期三(3)初始归并段的生成步12345678910111213…缓冲区内容151515(11)(11)(11)(11)(11)(11)1111(06)……1919191925(16)(16)(16)(16)161616……04122727272734(26)(26)262626……8383838383838383(07)109090……输出结果041215192527348307101116…R1R2(a)初始归并段的长度≥缓冲区的长度(b)任何内部分类算法都可作为生成初始归并段的算法(c)例如：缓冲区的长度为4，输入序列为：

151904831227112516342607109006…

新输入记录.key小于当前记录.key，等待下一个归并段采用选择树法生成初始归并段的长度平均是缓冲区长度的两倍。第十页，共二十页，编辑于2023年，星期三7.2磁带文件的归并分类（外部）存储设备——纸带、磁鼓、磁带、磁盘等第十一页，共二十页，编辑于2023年，星期三与磁盘不同，磁带是顺序存储设备，读取信息块的时间与信息块的位置有关。研究磁带分类，需要了解信息块的分布。K路平衡归并分类磁带机数量：2k输入：T1,T2,……,Tk

输出输出：Tk+1,Tk+2,……,T2k

输入磁带机T1T2…Tk归并段R1R2…RkRk+1Rk+2…R2k…………Rmk+1………T1:R1(1000),R3(1000),R5(1000)T2:R2(1000),R4(1000),R6(1000)T3:ØT4:ØT1:ØT2:ØT3:

R1(2000),R3(2000)T4:R2(2000)T1:R1(4000)T2:

R2(2000)T3:ØT4:ØT1:ØT2:ØT3:R1(6000)

T4:Ø第十二页，共二十页，编辑于2023年，星期三i遍后t1t2t3开始13(1L)21(L)空1空8(1L)13(2L)28(3L)空5(2L)33(3L)5(5L)空4空2(5L)3(8L)52(13L)空1(8L)61(13L)1(21L)空7空空1(34L)步t1t2t3总段数n0011n-11102n-22013n-30235n-43508n-580513n-6081321n-71321034多阶段归并分类K+1台磁带机，实现k路归并K阶Fibonacci数列tji表示第j步中逻辑上第i台磁带机。n-j步归并段分布规则第十三页，共二十页，编辑于2023年，星期三空磁带机台号=K+1当j=0或k+1的整数倍j%(k+1)j不为上述值注：在多路归并中，若要求归并的文件其初始归并段总数不是K阶Fibonacci数，则需附加一些虚的归并段数，以凑成k阶Fibonacci数，同时还应该将虚归并段适当地分布在k路归并的k台磁带上。第十四页，共二十页，编辑于2023年，星期三例1：设有磁盘文件中记录的关键字分别为：

10,20,15,25,12,13,21,30,8,16,10

用置换-选择排序法产生初始归并段，问可产生几个初始归并段？每个初始归并段包含哪些记录（设工作区能容纳4个记录）。解：内存缓冲区可容纳4个记录，采用4路归并的置换-选择排序方法生成初始归并段，如表所示。步1234567891011缓冲区内容101213212121(16)(16)16162020202020(8)(8)(8)151515153030303025252525252525(10)10输出结果

101213152021253081016

生成的第一个初始归并段第二个初始归并段第十五页，共二十页，编辑于2023年，星期三例2：给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),设内存工作区可容纳4个记录，写出用置换-选择排序得到的全部初始归并段。解：初始归并段1：2,8,12,16,28,30

初始归并段2：4,6,10,18,20第十六页，共二十页，编辑于2023年，星期三例3：设有13个初始归并段，其长度分别为：28,16,37,42,5,9,13,14,20,17,30,12,18。试画出4路归并时的最佳排序树，并计算它的带权路径长度。解：n=13,k=4

因为(n-1)%(k-1)=0,所以不需要加虚段。WPS=(5+9+12+13+14+16+17+18+20+28+30+37)×2+42=4805912131416171820283037651154226139最佳归并树第十七页，共二十页，编辑于2023年，星期三例：假设4个初始归并段如下：

R1:15,16,25,32R2:3,22,28,45R3:1,12,30,42R4:33,60给出进行4路归并的过程。(1)输出1R1:15,16,25,32R2:3,22,28,45R3:12,30,42R4:33,60(2)输出1,3R1:15,16,25,32R2:22,28,45R3:12,30,42R4:33,60(3)输出1,3,12R1:15,16,25,32R2:22,28,45R3:30,42R4:33,60(4)输出1,3,12,15R1:16,25,32R2:22,28,45R3:30,42R4:33,60(5)输出1,3,12,15,16R1:25,32R2:22,28,45R3:30,42R4:33,60(6)输出1,3,12,15,16,22R1:25,32R2:28,45R3:30,42R4:33,60(7)输出1,3,12,15,16,22,25R1:32R2:28,45R3:30,42R4:33,60第十八页，共二十页，编辑于2023年，星期三(8)输出1,3,12,15,16,22,25,28R1:32R2:45R3:30,42R4:33,60(9)输出1,3,12,15,16,22,25,28,30R1:32R2:45R3:42R4:33,60(10)输出1,3,12,15,16,22,25,28,30,32R1:R2:45R3:42R4:33,60(11)输出1,3,12,15,16,22,25,28,30,3