多路归并算法

多路归并是外部排序(External Sort)的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k。

算法简介(1)假设有K路数据流，流内部是有序的，且流间同为升序或降序；

(2)首先读取每个流的第一个数，如果已经EOF，pass；

(3)将有效的k(k可能小于K)个数比较，选出最小的那路mink，输出，读取mink的下一个；

(4)直到所有K路都EOF。

多路归并方法一：循环遍历首先，我们比较所有k个数组的头一个元素，找到最小的那一个，然后取出来。我们在该最小元素所在的数组取下一个元素，然后重复前面的过程去找最小的那个。这样依次循环直到找到所有的元素。

代码如图：

用一个notEmpty来标志所有序列是否已经遍历完了。每次遍历所有序列的当前元素，找到最小的。这样每次找一个元素都要比较k次，假设所有n个元素，其总体时间复杂度就达到了O(nk)。

方法二：最小堆K路归并排序首先从k路序列中都取一个元素出来。因为所有的都是已经按照从小到大排序的，不需要考虑其他的。每个序列里取出来的肯定是这个序列里最小的，在这些最小元素里找到全局最小的那个。针对这个序列后面是否还有元素的问题，可以通过以下两种方法处理：

1. 假定在处理元素的过程中，某个序列的元素取光了。我们可以在开始的时候针对所有序列的最后都加一个表示无穷大的数值。这样如果取完这个序列之后可以保证它后续肯定不会被选择到。

2. 我们将该元素用堆最后的元素替换，然后调整堆的属性并将堆的大小减1。这样我们这个大小为k的堆慢慢会变成k-1, k-2,1这些个长度的堆。一直到我们把这些堆里序列的元素处理完1。

方法三：胜者树K路并归排序首先，胜者树的形式如图：

几乎堆的每个叶节点对应一个输入序列，将其构成一个完全二叉树，进行一轮胜者的选择之后，对结构如下：

可以看出最终在堆顶的那个元素是最小的，而且有一条路径从叶节点到堆的根。

通过在原来序列里取后续的元素，然后像胜者树调整一样向上，符合条件的元素放上面，然后一直比较到根。这样就找到了下一个最小的元素。这样一直循环下去。如果一个序列处理完了我们可以采用在末尾增加一个无穷大的值。

总的来说，这个方法和普通的最小堆调整差不多，就是调整的方式不一样而已1。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所