外部排序分析

   当对数据记录量巨大的数据文件进行排序时，由于受到内存容量的限制，无法将所有数据记录一次全部读入到内存进行。排序过程中需要多次进行内、外存之间的数据交换。利用外存对数据文件进行排序称为外部排序。
       外部排序最基本的方法是归并。这种方法是由两个相对独立的阶段组成：
① 按内存(缓冲区)的大小，将n个记录的数据文件分成若干个长度为l的段或子文件，依次读入内存并选择有效的内部排序方法进行排序；然后将排好序的有序子文件重新写入到外存。子文件称为归并段或顺串。
② 采用归并的办法对归并段进行逐趟归并，使归并段的长度逐渐增大，直到最后合并成只有一个归并段的文件—排好序的文件。

1 外部排序的简单方法
    归并排序有多种方法，最简单的就是2-路归并。
    设有一个磁盘上的数据文件，共有100,000个记录(A1， A2，…，A100000)，页块长为200个记录，供排序使用的缓冲区可提供容纳1000个记录的空间，现要对该文件进行排序，排序过程可按如下步骤进行：
        第一步：每次将5个页块(1000个记录)由外存读到内存，进行内排序，整个文件共得到10个初始顺串R1~R10 (每一个顺串占5个页块)，然后把它们写回到磁盘上去。
       第二步：然后两两归并，直到成为一个有序文件为止。


由图可知，每趟归并由m个归并段得到┌m/2┐个归并段。
2 外排序的时间分析
         外排序的时间消耗比内排序大得多，原因是：
● 外排序的数据量(记录)一般很大；
● 外排序涉及到内、外存之间的数据交换操作；
● 外存的操作速度远远比内存中的操作慢。
外排序的总时间由三部分组成：
外排序的时间=产生初始归并段的时间(内排序)m×tis
                          +I/O操作的时间d×tio
                          +内部归并的时间s×utmg
其中：
m：初始归并段数目；tis：得到一个归并段的内排序时间；
d：总的读、写次数；tio：一次读、写的时间；
s：归并的趟数；utmg：对u个记录进行一趟内部归并排序的时间。
        一般地，tio>>tis，tio>>tmg，tio而取决于所用外存,因此，影响外排序效率的主要原因是内、外存之间数据交换(读、写外存)。提高效率的主要方法(途径)有：
● 进行多路归并，减少文件归并的趟数；
● 增加归并段的长度，减少初始归并的数目；
● 根据不同归并段的长度，采取最佳归并方案。

补充：综合编程 , 其他综合 ,