外部排序

一般讨论的排序都是内部排序，所谓外部和内部，是针对排序时的条件而言的，内部指所有的数据都可以直接拿到，而外部就是每次只能拿到一部分数据，最典型的现实场景

  • 对数组进行排序，整个数组当然都是在内存里的，可以直接拿到
  • 而对磁盘数据（比如文件）进行排序，要先把数据读进内存，而且限于内存的大小，内存中在某一时刻只能有一部分数据

外部排序的限制在于从磁盘读数据是一件很麻烦的事情，因为在磁盘上的数据存储并不是和在内存中那样是连续的，有个地址就可以直接访问，而是分散的，而且每次找一个数据都得寻道，旋转，再数据传输，排序的结果还得再写回磁盘，实际磁盘I/O的时间会远超在内存上操作的时间，所以要尽可能减少对磁盘的访问，I/O次数也成为外部排序时主要考虑的代价

这时候可以选什么排序算法来进行外部排序呢，很明显，选择排序，冒泡排序，这种每一趟都得把数据基本过一遍的算法是不行的，实际上可以想到，归并排序是个不错的选择

例如，一个有2000个记录的文件，每个磁盘块可以容纳125个记录，首先通过8次内部排序得到8个初始归并段R1到R8，每个段有250个记录，然后对该文件做两两归并，直至得到一个有序的文件

把内存分出三个缓冲区，两个输入一个输出，从R1和R2分别读一个磁盘块到输入缓冲区，归并到输出缓冲区，钥匙其中一个缓冲区空了就再读一个，然后把输出写到磁盘，再归并R3和R4，R5和R6，R7和R8，分别得到R1’-R4’

R1--R2      R3--R4      R5--R6      R7--R8
  ｜           ｜          ｜          ｜
  R1' ------- R2'         R3' ------- R4'
         |                       |
        R1'' ------------------ R2''
                    |
                    R

这样的话，一躺归并要读16个磁盘块，写16个磁盘块，内部排序也要读16次，写16次，总共的I/O次数：
$$
32\times 3 + 32=128
$$
如果改成四路归并，就只需要2趟归并：

R1--R2--R3--R4      R5--R6--R7--R8
       |                   |
      R1' --------------- R2'
                |
                R

这样外部排序的I/O次数就少了，但这样需要内存提供更多的缓冲区

败者树

增加归并排序的路数k固然可以减少I/O次数，但是内部归并的时间却增加了，因为在k个元素中选一个最小的需要做k-1次比较，每趟归并n个元素，要比较$(n-1)(k-1)$次，r个初始归并段，S趟归并总共需要的比较次数为：
$$
S(n-1)(k-1)=\log_k r(n-1)(k-1)=\frac{\log r}{\log k}(n-1)(k-1)
$$
可以看到随着k的增大，内部归并的时间也变多了，这时候就不能用普通的内部归并算法了

败者树主要用于选出k个元素里最小的那个，比如有8个元素，先两两比较，选出4强，再半决赛，在决赛，最后胜利的一定是冠军，但是只比了3次

               a
               |
      a ------------- e
      |               |
  a ----- c       e ----- g
  |       |       |       |
a---b   c---d   e---f   g---h

显然败者树是一颗完全二叉树，k路归并的话，从k个数据里选最小的，比较的次数为$\log k$，总的比较次数为
$$
S(n-1)\log k=(\log_k r)(n-1)\log k=(n-1)\log r
$$
这样内部归并比较的次数就与k无关了

但即使是这样，k也不是越大越好，k增大时，内存要提供更多个数的缓冲区，每个缓冲区的容量就会变小，内外存交换的次数会增加，因此当k过大时，归并趟数会减少，但外存I/O次数还是会增加

置换-选择排序

还有什么优化的方向呢，减少初始归并段的个数$r$也开始减少归并趟数S，内部排序在生成初始归并段的时候，依赖于内存工作区，只能生成相当于内存工作区大小的初始归并段，有什么操作可以跳出这个限制呢

基本思路是这样的

  1. 一个工作区，大小为w，先从文件读w个记录进去
  2. 从工作区里选一个最小的，输出并把值记录下来
  3. 往工作区里补一个记录，再找一个最小的但是比已经输出的值要大的，输出
  4. 重复，直到找不到比已经输出的值要大的
  5. 结束，一个初始归并段生成了

其中“从工作区里的w个记录里找一个最小的”的操作是基于败者树的

最佳归并树

置换-选择排序后，产生了一系列不等长的初始归并段，那么如何安排归并顺序呢，显然不同的顺序开销是不同的

比如，有9个初始归并段，长度为9，30，12，18，3，17，2，6，24

[9]-[30]-[12]   [18]-[3]-[17]   [2]-[6]-[24]
     |                |              |
    [51] ---------- [38] ---------- [32]
                      |
                    [121]

归并树的带权路径长度（WPL）为归并过程中的总读记录数，在上面的归并树中，WPL=242

实际上，可以用Huffman树的思想来优化归并树，将比较小的归并段先归并

     [2]-[3]-[6]
          |
     [9]-[11]-[12]  [17]-[18]-[24]
          |                |
[30]-----[32]------------[59]
          |
        [121]

这样的话，WPL只有223（把除了根节点的每个节点的值都加起来）

其实上图中的Huffman树是一颗严格的三叉树，即节点的度要么是0要么是3，但实际场景中这种刚刚好的场景是很少的，比如缺一个30，这时候构造Huffman时最后一次归并将是2路归并，WPL为193，但这并不是最优的

正确的做法应该是：补上1个值为0的节点

[0]-[2]-[3]
     |
    [5]-[6]-[9]             [12]-[17]-[18]
         |                        |
        [20]--------[24]---------[47]
                     |
                    [91]

那么如何确定应该补几个0节点呢？

  • 设度为0的节点有$n_0$个，度为k的节点有$n_k$个，如果是严格k叉树，有$n_0=(k-1)n_k+1$
  • 也就是$n_k=(n_0-1)/(k-1)$
    • 如果$k-1|n_0-1$，说明刚好
    • 如果$n_0-1\equiv u \mod k-1$，说明多出来$u$个，补上$k-1-u$个就好了

注意，初始节点全是度为0的节点

比如，8个初始节点，3路归并，$8-1\equiv1\mod 3-1$，多1个，补1个

总结

外部排序相较于内部排序，很重要的一点是考虑了实际环境的限制，而且外部排序的过程中也涉及到了内部排序

在外部排序的优化过程中，除去优化的方法，优化的思路更值得关注