了解一下什么是外部排序算法

以前我们学习的排序算法,比如冒泡排序、插入排序、快速排序等都是属于内部排序,即所有排序操作都是在内存中完成。然而如果需要排序的文件比整个内存还大时,这时就无法将文件一次性放到内存中,需要借助外部存储来进行排序,这就是外部排序。

外部排序有两个步骤,分别是

  • 分:首先将大文件分成n个小文件,每个小文件的大小需要小于内存的大小。然后依次将这些小文件放到内存中调用内排进行排序,处理完毕后会得到n个有序的小文件。

  • 合:有了n个有序的小文件,怎么合并成1个有序的大文件呢?我们可以进行归并排序。

    举个例子,我们有三个小文件,内存的大小为3:

     文件1:3, 6, 9
     文件2:2, 4, 8
     文件3:1, 5, 7
    

    首先比较每个文件中的最小值,得出最小值后写入大文件。第一步比较3、2、1,拿出了最小值1写入大文件,第二步比较3、2、5,拿出了最小值2写入大文件,第三步比较3、4、5,拿出了最小值3写入大文件……循环执行这个步骤,最后即可完成排序。

上面的这个步骤其实就是3路平衡归并。因此,对于实际的场景中,对于 k-路平衡归并中的 k 值得选择,增加 k 可以减少归并的次数,从而减少外存读写的次数。但 k 的值也不是越大越好,k越大,在内存中选择最小值的时候也会更加花费时间。一般情况下,对于具有 m 个初始归并段进行 k-路平衡归并时,归并的次数为$⌊log_k⁡m ⌋$。

从公式中可以看出,要想提高算法效率,可以从两个角度实现:

  • 一是增加 k-路平衡归并中的 k 值。
  • 二是尽量减少初始归并段的数量m,增加每个归并段的容量。

但其实这两个角度是有矛盾之处的,实际场景中需要就综合考虑,平衡这两者了。