多路归并算法(K-Way Merge Algorithm)

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

(1)假设有K路数据流,流内部是有序的,且流间同为升序或降序

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

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

(4)直到所有K路都EOF

代码如下:

输出:

Leave a Reply

Your email address will not be published.