数据结构外部分类.ppt

第7章 外部分类 Slide. 7 - * D.S. A. 2010 ’秋 数据结构 哈尔滨工业大学软件与网络技术学院 D.S. Page. * 第一章 绪 论 7.1 磁盘文件的归并分类 7.2 磁带文件的归并分类 第7章 外部分类（Sorting） 归并方法：首先将文件中的数据输入到内存，采用内部分类 方法进行分类（归并段），然后将有序段写回外存；对多归 并段进行多遍归并，最后形成一个有序序列。 例：假设一个磁盘文件，由4500个记录组成，分别记为A1,A2,……,A4500 设系统提供容纳750个记录的内存共分类使用，每次磁盘读写250个 记录的数据块，则可设计分类过程如下： 7.1 磁盘文件的归并分类 (1)每次从文件中输入三个数据块（750个记录）到工作空间，进行内部分类。 分类结果写回磁盘，构成6个初始归并段：R1,R2,R3,R4,R5,R6 R1 R2 R3 R4 R5 R6 1-750 751-1500 1501-2250 2251-3000 3001-3750 3751-4500 （2）将内存空间三等分，每块250个记录，其中2块为输入缓冲区，1块为输出 缓冲区。 归并R1和R2，输出到输出缓冲区，若输出缓冲区满，则写盘。同样，若 R1和R2的缓冲区出现空，则继续读盘，直到归并结束为止。R12=R1+R2； 同样得到：R34=R3+R4, R56=R5+R6； R12、R34、R56分别都包含1500个记录。 （3）类似（2）的方法，可将R12和R34归并成R1234,，再将R1234和R56进行归并。 得到最后的排序结果。 R1 R2 R3 R4 R5 R6 R12 R34 R56 R1234 R1234 6×750记录 3×1500记录 12×250记录 18×250记录 K路归并 … … . . . 遍数 [log2m] 层数 [log2m]+1 M 个归并段的归并过程 R1 R1 Rm-1 Rm 2 … K K+1… 2K … … m . . . logkm +1 levers (1) 多路归并——减少归并遍数 并行操作的缓冲区处理——使输入、输出和CPU处理尽可能重叠 (3) 初始归并段的生成 讨论问题 logkm遍比较次数： (1) 多路归并——减少归并遍数 m个初始段进行 2 路归并，需要 log2m 遍归并; 一般地，m 个初始段，采用k路归并，需要 logkm 遍归并。 显然，k 越大，归并遍数越少，可提高归并的效率。 在 k 路归并时，从 k 个关键字中选择最小记录时，要比较 K-1 次。若记录总数为 n ，每遍要比较的次数为： n*(k-1)[ log2m/log2k ] 可以看出，随着k增大，(k-1)/log2k 也增大，当归并路数多时， CPU 处理的时间也随之增多。为此要选择好的分类方法，以 减少分类中比较次数。 6 10 9 20 6 8 9 90 17 9 6 8 17 6 8 15 16 20 38 20 30 15 25 15 50 11 16 100 110 18 20 选择树 ( Selection tree ) 或 败者树 ( tree of loser ) 分析： 第一次建立选择树的比较所花时间为: 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 无关 ) 最佳归并树 将哈夫曼树进行拓展，不仅对二叉树，同样可形成三叉、四叉、……、k叉树，亦称为哈夫曼树，同样可求得带权路径长度最小。 最佳归并树： 对长度不等的m个初始归并段，构造哈夫曼树作为归并树，便可使在进行外部归并时所需要对外存进行的读写次数达到最小。 最佳归并树中，并不只是只有度为k和0的结点，会有缺额。当初始归并段的数目不足时，需附加长度为0的虚段，按照哈夫曼树的构造原则，权为0的叶子结点应离树根最远。 若