外排序学习笔记

l         简单外归并排序

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

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

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

–     快速排序

–     堆排序

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

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

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

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

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

个输出缓冲区中

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

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

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

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

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

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

l         置换选择排序

问题： 怎样为一个文件创建尽可能长的初始顺串 ?

环境限制：一个input buffer ， 一个 output buffer ,一个能存放M个记录的RAM内存块。只能在内存中进行排序。

算法名称： replacement selection 置换选择

效率：平均情况下，这种算法可以创建长度为2M个记录的顺串。 I/O时间是外排序的决定性时间

关联算法：该算法是堆排序算法的一个微小变种。

处理过程： 输入文件 -输入缓存区 – 内存处理 – 输出缓存区- 输出文件的大致过程这里不再赘述 。 下面只介绍下核心排序过程，该过程利用了最小值堆，最小值堆是每个节点的关键码值都小于其子孙节点的关键码值的完全二叉树。  堆的大小是正好为RAM的大小M，下标[0,M-1].

     假设在某个状态下堆的规模为size，形成堆后根[rootKey]马上被输出。 接下来要处理输入缓冲区 紧接着的输入记录关键码 closeKey .

    If(closeKey >= rootKey) then

        Add the colse element to the heap ,located at heap[0] .

        Make heap[0,size-1] again.

  Else if(closeKey < rootKey) then

        Heap[0] = heap[size-1]

        Heap[size-1] = closeElement from input buffer.

        Make heap[0,size-2] again.

        [note:这种情况下，堆会缩小一个单位，直至为空。此时，我们完成了一个顺串，而Ram中也充满了不能处理的数据，对这种数据建堆，重复上述过程，就可以得到第二个顺串。]

   End if.

l         多路归并  ---- 选择树   二路归并需要4个缓冲区，那么多路归并时，缓冲区的要求？

两种类型：

1.         Winer Tree

2.         Loser Tree

其中，Loser Tree 可以简化重构的过程，减少重构选择树的代价。 所谓Loser Tree，就是在选择树中，每个非叶结点均存放其两个子节点中的败方所对应叶节点的索引值。【It is ambiguous in words.See the graph below.】

顶端的 index = 4 表示是 底部的 6 被选择.

       效率分析： 初始化包含k个选手的败者树，需要O (K) 的时间，把最小值输出到缓冲区，读入下一个新值并重构败者树的时间是O（logk） .因此，最后产生一个大小为n的顺串的总时间为O(k + nlogk) 。而如果采用原始的顺序扫描方法，扫描一遍求出一个最小值的方法，效率是O(kn).

最佳归并树

       如果在进行多路归并的时候，各初始顺串的长度不同，对外存扫描的次数【即执行时间】会产生影响。

最佳归并树实际是一个Huffman编码的问题，k路归并对应一棵K叉Huffman树。

通过最佳归并树进行多路归并可以使对外存的I/O降到最少，提高归并执行效率。