外部排序

热门标签

排序 外部

生成合并段(run):读入文件的部分记录到内存->在内存中进行内部排序->将排好序的这些记录写入外存,形成合并段->再读入该文件的下面的记录,往复进行,直至文件中的记录全部形成合并段为止。

外部合并:将上一阶段生成的合并段调入内存,进行合并,直至最后形成一个有序的文件。

外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行多路归并排序

不管初始序列是否有序, 冒泡、选择排序时间复杂度是O(n^2),归并、堆排序时间复杂度是O(nlogn)

外部排序的总时间 = 内部排序(产出初始归并段)所需时间 + 外存信息读取时间 + 内部归并所需的时间

外排中使用置换选择排序的目的,是为了增加初始归并段的长度。减少外存读写次数需要减小归并趟数

根据内存容量设若干个输入缓冲区和一个输出缓冲区。若采用二路归并,用两个输入缓冲。

归并的方法类似于归并排序的归并算法。增加的是对缓冲的监视,对于输入,一旦缓冲空,要到相应文件读后续数据,对于输出缓冲,一旦缓冲满,要将缓冲内容写到文件中去。

外排序和内排序不只是考虑内外排序算法的性能,还要考虑IO数据交换效率的问题,内存存取速度远远高于外存。影响外排序的时间因素主要是内存与外设交换信息的总次数

特别声明:文章多为网络转载,资源使用一般不提供任何帮助,特殊资源除外,如有侵权请联系!

评论 (0)