《数据结构域算法设计-第十七讲-外部排序 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第十七讲-外部排序 课件（8页珍藏版）》请在金锄头文库上搜索。
1、第十一章 外部排序n外存信息的存取 n外部排序的方法 n多路平衡归归并的实现实现 n置换换 - 选择选择 排序 n最佳归归并树树 教学内容教学要求及重难难点教学要求n了解外存储储器及文件的基本知识识 n了解外排序的定义义和基本方法 n掌握磁盘盘排序和磁带带排序两种外排序的基本思路 重难难点n外部排序的方法 n多路平衡归归并的实现实现 外部排序 是指在排序的过过程中，数据的主要 部分存放在外存储储器上，借助内存储储器(作为为工作 单单元)，来调调整外存储储器上数据的位置。归归并方法的一般过过程：分两个阶阶段。第一阶阶段：首先，将文件中的数据分段输输入到内存 ，在内存中采用内部排序方法对对其进进行
2、排序（排 序完的文件段，称为归为归 并段)，然后将有序段写回 外存。 整个文件经过经过 在内存逐段排序又逐段写回 外存，这样这样 外存中形成多个初始的归归并段。第二阶阶段：对这对这 些初始归归并段采用某种归归并排序方 法，进进行多遍归归并，最后形成整个文件的单单一归归 并段(整个文件有序）。外部排序磁盘盘文件的归归并排序n示例：设设有一个包含4500个记录记录 的输输入文件。现现用一台其内 存至多可容纳纳750个记录记录 的计计算机对该对该 文件进进行排序。输输入 文件放在磁盘盘上,磁盘盘每个页块页块 可容纳纳250个记录记录 , 这样这样 全部 记记可存储储在 4500 / 25018 个页
3、块页块 中。输输出文件也放在磁盘盘 上,用以存放归归并结结果。n由于内存中可用于排序的存储储区域能容纳纳750 个记录记录 , 因此 内存中恰好能存3个页块页块 的记录记录 。n在外部排序一开始, 把18块记录块记录 , 每3块块一组组, 读读入内存。利用 某种内部排序方法进进行内部排序, 形成初始归归并段, 再写回外 存。总总共可得到6个初始归归并段。然后一趟一趟进进行归归并排 序。磁盘盘文件的归归并排序n若把内存区域等份地分为为 个缓缓冲区。其中的两个为输缓为输缓 冲区，一个为输为输 出缓缓冲区，可以在内存中利用简单简单 归归并 函数 （ ）实现实现 路归归并。n首先，从参加归归并排序的两
4、个输输入归归并段 和 中分 别读别读 入一块块，放在输输入缓缓冲区和输输入缓缓冲区中。然后 在存中进进行 路归归并，归归并结结果顺顺序存放到输输出缓缓冲区中 。n当输输出缓缓冲区装满满2个记录时记录时 ，就输输出到磁盘盘。n如果归归并期间间某个输输入缓缓冲区空了，就立即向该缓该缓 冲区继继 续续装入所对应归对应归 并段的一块记录块记录 信息，使之于另一个输输入 缓缓区的剩余记录归记录归 并，直到和归归并为为、 和归归并、和归归并为为为为止。n再把和归归并为为，最后把 和归归并为为。磁盘盘文件的归归并排序多路归归并排序 m个初始段进进行 2 路归归并，需要 log2m 遍归归并;一般地，m 个初
5、始段，采用K路归归并，需要 logKm 遍归归并。显显然，K 越大，归归并遍数越少，可提高归归并的效率。在 K路归归并时时，从 K 个关键键字中选择选择 最小记录时记录时 ，要比较较K-1 次 。若记录总记录总 数为为 n ，每遍要比较较 n*(K-1)次， logKm 遍要比较较 的次数为为： n*(K-1) logKm = n*(K-1) log2m/log2K n*(K-1) log2 n/l /log2K可以看出，随着K增大，(K-1)/log2K 也增大，当归归并路数多时时， CPU处处理的时间时间 也随之增多。当K值值增大到一定程度时时，可能使 CPU处处理时间时间 大于因K值值增
6、大而减少归归并遍数所节节省的时间时间 。为为提高分类类的效率可以 (1) 选择选择 好的分类类方法，以减少分类类中比较较次数；(2) 选择选择 好的初始归归并段形成方法，增大归归并段长长度；K 路平衡归归并与败败者树树选择树选择树 或 败败者树树 分析：第一次建立选择树选择树 的比较较所花时间为时间为 :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 无关，选择树选择树 很 好
