外排序(转)

今天忙里偷闲，看了下外排序，转一篇文章

l         简单外归并排序

把文件分解成尽可能大的若干初始顺串

1.       根据内排序可以处理的最大数据区大小

2.        可以用任何内排序算法

–     快速排序

–     堆排序

设置两个输入缓冲区和两个输出缓冲区 同时用到4个缓冲区

A. 把原来的文件分成两个大小相等的文件，每个文件中一个记录就作为一个顺串

B. 从每个文件读入一个块（block或sector），分别放在两个输入缓冲区 一个基本的I/O操作是读/写一块。

C. 从每一个输入缓冲区中取出第一个记录，然后把它们以排好的次序写入一个输出缓冲中

D. 从每块中取出第二个（下一个）记录，比较其大小，然后把它们以排好的次序写入下一个输出缓冲区中

E. 重复这些步骤，在两个输出缓冲区之间交替输出，直到结束。当一个输入块用完时，从相应的输入文件读出第二个块。当一个输出顺串缓冲区已满时，把它写回相应的输出文件。

F. 使用原来的输出文件作为输入文件，重复第2步到第5步。在第二趟归并中，每个文件中两个有序记录作为一个顺串。这样，就可以把这两个顺串归并成一个四个元素的顺串而输出。

G. 每一趟归并的顺串越来越大（子顺串数目越来越少），直到最后只剩下一个顺串。

一般说来，外排序算法都基于下面两步：

1. 把文件分解成大的初始顺串。

2. 把所有顺串归并到一起，形成一个排序的文件。

 

今天看了一个题目“提高外排序效率的方法”。

（1）通过置换-选择方法减少初始归并段的个数，可以降低一半。

        例如：若一组排序码K1>K2>...Kn,缓冲区可容纳M个排序码，如果用内排序，则可以产生n/M个归并段。

       若采用置换-选择方法，可以产生n/2M个归并段。

（2）通过败者数进行多路归并减少归并趟数，即降低归并树高度。

（3）利用缓存提高IO和CPU的并行性

 特别想提一下其中置换-选择方法中，如果缓冲可容纳M个排序码，则可以得到2M的归并段，书中给出了扫雪机的一个类比证明，其实可以这样看：

由于在置换-选择中，当提取一个排序码ki1（第i段提取的第一个关键词）时，将会从文件中读取一个ki2，如果ki2

1 + 1/2 + 1/4 + 1/8 +... = 1/(1-1/2) = 2

如果有M个段（缓冲可容纳M个排序码，因此可以看做是M个段），则最终可以选拔出的记录数为2*M个。

证明方法比扫雪机的证明方法更加直观，今天想来，写下来，供大家看看。

http://blog.csdn.net/pennyliang/archive/2010/02/07/5297136.aspx

http://hi.baidu.com/sophiaandphilem/blog/item/04c8e411a1f509c5a7ef3f57.html