3．3外排序及广义斐波那契-Read.ppt

§3．3 外排序及广义斐波那契(FIBONACCI)数 当要排序的记录太多，所占的空间超出计算机内存允许的容量时， 须使用外排序法。 将要排序的记录放在外存(磁带、磁盘)里， 逐次将外存中的记录读入内存， 排序后的记录也存放在外存中。外存与内存的差别在于外存容量大、速度慢、价格低廉， 而内存容量小、速度快、价格高昂。 内排序算法运行所需时间主要消耗在比较操作上， 甚至时间复杂度可用比较次数表示，这是因为内排序的主要操作是比较。 外排序算法也有比较操作，但外排序更多的时间消耗于数据在内存、外存之间的数据传递： 将数据从外存读入内存，将数据从内存写到外存。 在外存上的读写动作包含了机械动作,因须将磁带、磁盘的某个部位移动到磁头的位置。 机械操作比电操作要缓慢得多。因此在设计外排序算法时要特别注意减少对外存的读写操作次数。 相比之下，“比较’’操作在机器内部进行，比较所化费的时间就显得不那么重要了。 对外存里的数据进行的操作主要是顺序操作，即按记录在外存中占据的物理位置的次序来处理这些记录, 因为不然的话需要对磁带进行回绕等操作，这些操作与外存的读写一样很化费时间。 外排序中使用的主要方法是归并。 设要对外存中的记录按关键字段KEY的值进行排序。 归并过程思路：要排序的记录在文件A、文件B上(文件A及文件B已经有序)，排序结果输出至文件C 比较文件A的第一个记录与文件B的第一个记录， 将KEY值小者输出至文件C，再从相应文件读进一个记录，替代已被输出的记录，再继续比较， 直至有一个文件的记录已被穷尽，即都已输出至文件C，然后再将未穷尽的文件上的所有记录拷贝到输出文件C上。 这个算法可以简化，如在文件A、B的末尾都放上一个虚记录，其KEY字段值为+∞ ， 意为大于任何可能的KEY字段值，当然在输出文件C的末尾也要放一个虚记录。 算法更动: 两个文件同时到达文件的尾部(文件的最后一个记录) 现在讨论下述问题：要排序的记录杂乱无章地在文件A上，如何对A的记录进行排序呢? 需要至少三个文件(如文件存在磁盘上，则要三个磁盘) 先引入名词“有序段”。有序段是文件具有下述性质的最大子序列：子序列是排好序的。 此即: 有序段若向前扩展一个记录, 有序性则被破坏;有序段若向后扩展一个记录, 有序性也被破坏 算法的思路如下： 设文件A有N个有序段，将这些有序段轮流分配到磁带B及C上， 如N为偶数, 则B、C含有的有序段数目相等 如N为奇数，则B、C含的有序段数目相差1. 令B、C回绕。 然后将B、C上的有序段归并到磁带A上。 B上的一个有序段与C上的一个有序段归并为一个大有序段，输出至磁带A 从而, A上的有序段数目约减半. 更详细说是这样的，从磁带B、C各读一个记录到B、C的缓存区． 将KEY字段值小的记录输出到磁带A， 再从相应的磁带读一个记录到缓存，替代那个被输出的记录， 如读进来的记录的KEY值比刚输出的记录的KEY小， 这意味着一个有序段的结束，新读进的记录不属于当前的有序段，应属于下一个有序段。 此时另一个文件的有序段尚未结束，须将这个有序段的其余记录拷贝到磁带A上 这样结束了A的一个有序段， 然后再开始下一个有序段， 如此循环，直至B和C上的记录都归并到A上。 可知A上的有序段数目减少了一半， 如N值原为奇数，则现在A上的有序段数目为(N+1)／2． 这个分配、归并的周期称为遍， 一遍结束，开始第二遍的分配、归并。 重复，直至磁带A上只有一个有序段，排序过程结束。 如N＝2m，则需m遍完成整个排序问题, 如N不是2的整次幂，则需 [log2 N]遍 在每一遍中每一个记录从一个磁带拷贝到另一个磁带两次， 一次从磁带A经由内存拷贝到磁带B或C，另一次从B或C经由内存拷贝到磁带A, 所以总共的拷贝次数为(设总共有M个记录) 2× M× log2 N 如有4个磁带，则拷贝次数减半。 令4个磁带为 A，B，C，D．要排序的记录在磁带A上。 四磁带外排序过程如下。将磁带A的有序段轮流分配到磁带C及磁带D上。 归并磁带C、D上的记录，归并得到的有序段轮流输出到A与B上， 即归并得到的第一个有序段送到A，然后将第二个有序段送到B，第三个有序段送到A，依此类推。 每遍归并使有序段数目减半，因此要log2N遍(其中N是开始时的有序段数目)。 每遍归并中，每个记录只被拷贝一次，从而总共需要拷贝的次数为 M · log2 n 排序所需时间的缩短是因为我们使用了四个磁带， 所以只在过程初始化时要将记录分配 到两个磁带上， 此后就再不需要分配，只需要归并了。 虽然遍数不变，但每遍所需时间只及原来的一半。 减少遍数的另一种方法: 过程开始时，按机器内存的容量，一次读入一批记录(例如256个记录，这决定于内存空间及记录的大小)， 用内排序法将这