引入：
其实K路归并排序的用处还是很广的，最简单的，假设你要排序海量的数据，比如TB级别的数据（我们姑且说是TB级别的搜索关键字），但是我们的内存只有GB级别，我们没办法一次把所有的数据全部载入然后排序，但是我们的确最终要结果，那么怎么办呢？K路归并排序闪亮登场 ，其实这就是一个“分而治之”的思想，既然我们要排Q个数，但是我们不能一次头全部排序完毕，这时候，我们把Q分为k组，每组n 个数,（k<n)并且假定这里的n个数据的排序在我们内存的容忍范围内，首先我们分别对于每组进行排序，这样得到了k个已经有序的数组(假设升序），那么我们最终只要吧这个k组数归并，这样得到的最后结果集就是已经排序了的结果集。
分析：
(1)如何合并k个已经排序了的数组呢？
因为我们以前讨论过堆，显然堆的排序效率是非常高的
，所以我们自然也考虑到用堆来实现，因为要升序排列，所以我们创建一个最小堆。因为最终排序结果的数总是小的在前面大的在后面，所以我们考虑先把所有的n个数组的第一个元素（最小数）都放入最小堆中，所以最小堆的大小为k。这样我们调整堆结构，那么它的第一个元素就是min( min(array1),min(array2)….min(arrayn))显然就是所有数中的最小元素。
(2)因为在任意数组中都是按照升序排列的，所以我们一旦从堆中删除了一个最小元素，就必须找一个元素来填这个坑。为此，我们需要找到删除元素所在的数组中的下一个元素然后将其填入堆。（这个有点像是吧全国的最精英的士兵都拉去精英团打仗，那么就是每个团的最强的都拉来，如果这个人不幸战死，那么从同团中找出仅次于它的继续顶这个精英团，这样永远保持精英团的战斗力最高） 所以，如何去根据被删除的堆元素找这个被删除的堆元素所在的数组呢？这就需要在我们新建一个复合类型，它既包括当前的值，也包含这个当前值所在的数组的id,
(3)因为每个排序了的数组，随着最小的元素的不断流失，它还没有参与排序的值是渐渐变少的，所以我们必须维护一个长度为k的数组，这个数组保留了每个数组中还没参与排序的当前位置。并且一旦这个数组中剩余的最小元素被添加到了堆，那么这个当前位置必须后移。
(4)随着每个数组的当前位置后移，总归最后会达到这个数组的末端，这时候，这个数组就不能再提供任何数了，（这个很正常，比如部队中有一个尖刀连，它包含了最杰出的人，那么最后选到精英团时，总从这个连队选，然后这个连队一定最后没人了） ，所以我们就无法从当前删除的数所在数组中找到下一个值了，这时候我们就必须选择下一个有值的数组id，并且挑选出其最小值，方法是arrayIdForDeletedData = (arrayIdForDeletedData + 1) % k 。
(5)最后总有所有的数组位置都到了末端，也就是所有数组都不能提供未参与排序的值，所以这时候我们就要判断当前的堆是否为空，如果不为空，那么他们就包含了n*k中的最大的几个数了，我们依次deleteMin()来吧最大的几个数按照最小顺序输出。如果当前的堆已经为空，那么直接跳出循环。
所以最终时间复杂仅为 O(n*logk)
代码：
想清楚了上述几个关键技术细节，这里代码就很好写了。
首先，我们定义一个值对象，它封装了某个整数以及这个整数来自于哪个数组.
package com.charles.algo.kwaymerge;
/**
*
* 这个对象表明是一个可以跟踪来自于哪个数组的数据对象
* @author charles.wang
*
*/
public class TrackableData {
//data表明具体的值
private int data;
//comeFromArray表明这个值来自于哪一个数组
private int comeFromArray;
public TrackableData(int data,int comeFromArray){
this.data = data;
this.comeFromArray=comeFromArray;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public int getComeFromArray() {
return comeFromArray;
}
public void setComeFromArray(int comeFromArray) {
this.comeFromArray = comeFromArray;
}
}
转载请注明原文链接：详解K路归并排序（实战）
