其实k路归并排序的用处还是很广的，最简单的，假设你要排序海量的数据，比如tb级别的数据（我们姑且说是tb级别的搜索关键字），但是我们的内存只有gb级别，我们没办法一次把所有的数据全部载入然后排序，但是我们的确最终要结果，那么怎么办呢？k路归并排序闪亮登场 ，其实这就是一个“分而治之”的思想，既然我们要排q个数，但是我们不能一次头全部排序完毕，这时候，我们把q分为k组，每组n 个数,（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; }}
然后我们定义一个最小堆，它是解决问题的关键，需要注意的是，它包含的元素应该是上述的值对象，当入堆，调整堆，基于的计算都是值对象的data字段。
package com.charles.algo.kwaymerge;/** * @author charles.wang * */public class minheap { // 最小堆的存储是一个数组,并且为了计算，我们第一个位置不放内容 private trackabledata[] data; // 堆的大小 private int heapsize; // 当前元素的数量 private int currentsize; public minheap(int maxsize) { heapsize = maxsize; // 创建一个比最大容纳数量多1的数组的作用是启用掉数组的头元素，为了方便运算，因为从1开始的运算更加好算 data = new trackabledata[heapsize + 1]; currentsize = 0; } /** * 返回当前的堆是否为空 * @return */ public boolean isempty(){ if(currentsize==0) return true; return false; } /** * 这里考察堆的插入，因为最小堆内部结构中数组前面元素总是按照最小堆已经构建好的，所以我们总从尾部插入 解决方法是： step * 1:先把当前的元素插入到数组的尾部 step 2:递归的比较当前元素和父亲节点元素， step * 3:如果当前的元素小于父亲节点的元素，那么就把当前的元素上移，直到移不动为止 * * @param value * @return */ public minheap insert(trackabledata value) { // 首先判断堆是否满了，如果满了就无法插入 if (currentsize == heapsize) return this; // 如果堆还没有满，那么说明堆中还有位置可以插入，我们先找到最后一个可以插入的位置 // currentpos表示当前要插入的位置的数组下标 int currentpos = currentsize + 1; // 先插入到当前的位置，因为是从1开始的，所以数组下标运算也要+1 data[currentpos] = value; // 然后比较当前元素和他的父亲元素 // 当前元素是data[currentpos] ，父亲元素是 data[(currentpos/2],一直遍历到根 trackabledata temp; // 如果currentpos为1，表明是插入的堆中第一个元素，则不用比较 // 否则， 如果插了不止一个元素，则用插入位置的元素和其父元素比较 while (currentpos > 1) { // 如果当前元素小于父亲元素，那么交换他们位置 if (data[currentpos].getdata() < data[currentpos / 2].getdata()) { temp = data[currentpos / 2]; data[currentpos / 2] = data[currentpos]; data[currentpos] = temp; // 更新当前位置 currentpos = currentpos / 2; } // 否则， 在假定已有的堆是最小堆的情况下，说明现在插入的位置是正确的，不用变换 else { break; } } // 插入完毕之后，吧当前的堆中元素的个数加1 currentsize++; return this; } /** * 这里考察堆的删除 因为是最小堆，所以肯定删除最小值就是删除堆的根元素，此外，还必须要调整剩余的堆使其仍然保持一个最小堆 * 因为有删除最小元素之后最小元素位置就有了个空位，所以解决方法是： step 1:吧堆中最后一个元素复制给这个空位 step * 2:依次比较这个最后元素值，当前位置的左右子元素的值，从而下调到一个合适的位置 step 3:从堆数组中移除最后那个元素 */ public trackabledata deletemin() { // 如果最小堆已经为空，那么无法删除最小元素 if (currentsize == 0) return null; // 否则堆不为空，那么最小元素总是堆中的第一个元素 trackabledata minvalue = data[1]; // 既然删除了最小元素，那么堆中currentsize的尺寸就要-1，为此，我们必须为数组中最后一个元素找到合适的新位置 // 堆中最后一个元素 trackabledata lastvalue = data[currentsize]; // 先将堆中最后一个元素移动到最小堆的堆首 data[1] = lastvalue; // 把堆内部存储数组的最后一个元素清0 data[currentsize] = null; // 并且当前的堆的尺寸要-1 currentsize--; // 现在开始调整堆结构使其仍然为一个最小堆 int currentpos = 1; // 当前位置设置为根，从根开始比较左右 int leftpos = currentpos * 2; trackabledata leftvalue; trackabledata rightvalue; trackabledata temp; // 如果左位置和当前堆的总容量相同，说明只有2个元素了，一个是根元素，一个是根的左元素 if (leftpos == currentsize) { // 这时候如果根左元素data[2]比根元素data[1]小，那么就交换二者位置 if (data[2].getdata() < data[1].getdata()) { temp = data[2]; data[2] = data[1]; data[1] = temp; } } else { // 保持循环的条件是该节点的左位置小于当前堆中元素个数，那么该节点必定还有右子元素并且位置是左子元素位置+1 while (leftpos < currentsize) { // 获取当前位置的左子节点的值 leftvalue = data[leftpos]; // 获取当期那位置的右子节点的值 rightvalue = data[leftpos + 1]; // 如果当前值既小于左子节点又小于右子节点，那么则说明当前值位置是正确的 if (data[currentpos].getdata() < leftvalue.getdata() && data[currentpos].getdata() < rightvalue.getdata()) { break; } // 否则，比较左子节点和右子节点 // 如果左子节点小于右子节点（当然了，同时小于当前节点），那么左子节点和当前节点互换位置 else if (leftvalue.getdata() < rightvalue.getdata()) { temp = data[currentpos]; data[currentpos] = leftvalue; data[leftpos] = temp; // 同时更新当前位置是左子节点的位置,并且新的左子节点的位置为左子节点的左子节点 currentpos = leftpos; leftpos = currentpos * 2; } // 如果右子节点小于左子节点(当然了，同时小于当前节点），那么右边子节点和当前节点互换位置 else { temp = data[currentpos]; data[currentpos] = rightvalue; data[leftpos + 1] = temp; // 同时更新当前位置是右子节点的位置,并且新的左子节点的位置为右子节点的左子节点 currentpos = leftpos + 1; leftpos = currentpos * 2; } } } return minvalue; }}
最后，我们来实现k路合并器，还是挺好实现的，不过涉及到一些下标运算必须特别小心。因为我们要通用，所以k和n都是传进来的，实际上，我们如果事先规划好k和n之后，完全不用在内部维护这些数，因为只要吧他们存入最小堆就行了。
package com.charles.algo.kwaymerge;import java.util.arraylist;import java.util.list;/** * * 这个类用于演示k路合并 * * @author charles.wang * */public class kwaymerger { private kwaymerger() { } /** * k路合并，这里的指导思想如下： * * (1)首先构造一个最小堆，其中堆中的元素初始值为每个数组中的最小元素 * (2)每次从最小堆中打印并且删除最小元素，然后把这个最小元素所在的数组中的下一个元素插入到最小堆中 (3)每次（2）结束后调整堆来维持这个最小堆 */ public static void mergekway(int k, int n, list<int[]> arrays) { // 这里存储了所有每个数组的当前的下标,在没有开始插入之前，每个数组的当前下标都设为0 int[] indexinarrays = new int[k]; for (int i = 0; i < k; i++) { indexinarrays[i] = 0; } // 首先构造一个最小堆,其大小为k minheap minheap = new minheap(k); // 第一步，依次吧每个数组中的第一个元素都插入到最小堆 // 然后把所有数组的下标都指向1 for (int i = 0; i < k; i++) { // 这里每个都构造trackabledata对象： // 其中：arrays.get(i)[0]表示它值为第i个数组的下标为0的元素（也就是第i个数组的第一个元素） // i表示这个对象来自于第i个数组 minheap.insert(new trackabledata(arrays.get(i)[0], i)); indexinarrays[i] = 1; } // 第二步，对最小堆进行反复的插入删除动作 trackabledata currentdeleteddata; trackabledata currentinserteddata; int arrayidfordeleteddata; int nextvalueindexinarray; // 循环的条件是k个数组中至少有一个还有值没有被插入到minheap中 while (true) { // 这个变量维护了有多少个数组当前下标已经越界，也就是数组所有元素已经被完全处理过 int noofarraysthatcompletelyhandled = 0; // 就是去查询维护所有数组当前下标的数组，如果都越界了，那么就说明都比较过了 for (int i = 0; i < k; i++) { if (indexinarrays[i] == n) noofarraysthatcompletelyhandled++; } // 如果所有的数组中的所有的值都比较过了，那么查看堆中内容是否为空。 if (noofarraysthatcompletelyhandled == k) { while (!minheap.isempty()) { currentdeleteddata = minheap.deletemin(); // 打印出当前的数 system.out.print(currentdeleteddata.getdata() + " "); } break; } currentdeleteddata = minheap.deletemin(); // 打印出当前的数 system.out.print(currentdeleteddata.getdata() + " "); // 获取当前的被删的数来自于第几个数组 arrayidfordeleteddata = currentdeleteddata.getcomefromarray(); // 获取那个数组的当前下标 nextvalueindexinarray = indexinarrays[arrayidfordeleteddata]; // 如果当前下标没有越界，说明当前数组中还有元素，则找到该数组中的下个元素 if (nextvalueindexinarray < n) { // 构造新的trackabledata，并且插入到最小堆 currentinserteddata = new trackabledata( arrays.get(arrayidfordeleteddata)[nextvalueindexinarray], arrayidfordeleteddata); minheap.insert(currentinserteddata); // 同时更新维护数组当前下标的数组，让对应数组的当前下标+1 indexinarrays[arrayidfordeleteddata]++; } // 如果当前下标已经越界，说明这个数组已经没有任何元素了，则找下一个有值的数组的最小元素 else { while (true) { arrayidfordeleteddata = (arrayidfordeleteddata + 1) % k; // 获取那个数组的当前下标 nextvalueindexinarray = indexinarrays[arrayidfordeleteddata]; if (nextvalueindexinarray == n) continue; else { // 构造新的trackabledata，并且插入到最小堆 currentinserteddata = new trackabledata( arrays.get(arrayidfordeleteddata)[nextvalueindexinarray], arrayidfordeleteddata); minheap.insert(currentinserteddata); // 同时更新维护数组当前下标的数组，让对应数组的当前下标+1 indexinarrays[arrayidfordeleteddata]++; break; } } } } } }
实验：
最后我们来演示下，假设我们有32个数，我们分为4路合并，每路8个数，并且这8个数是已经排序的。
然后我们用k路合并算法来对所有的32个数进行排序：
public static void main(string[] args) { // 我们来演示k路合并，假设我们有4组已经排序了的数组，每组有8个数，则n=8,k=4 int[] array1 = { 4, 5, 7, 8, 66, 69, 72, 79 }; int[] array2 = { 3, 9, 42, 52, 53, 79, 82, 87 }; int[] array3 = { 1, 17, 21, 31, 47, 55, 67, 95 }; int[] array4 = { 6, 28, 49, 55, 68, 75, 83, 94 }; system.out.println("这里演示k路合并，其中每个数组都事先被排序了，并且长度为8,我们分4路合并"); system.out.println("数组1为："); for(int i=0;i<array1.length;i++) system.out.print(array1[i]+" "); system.out.println(); system.out.println("数组2为："); for(int i=0;i<array2.length;i++) system.out.print(array2[i]+" "); system.out.println(); system.out.println("数组3为："); for(int i=0;i<array3.length;i++) system.out.print(array3[i]+" "); system.out.println(); system.out.println("数组4为："); for(int i=0;i<array4.length;i++) system.out.print(array4[i]+" "); system.out.println(); list<int[]> arraylists = new arraylist<int[]>(4); arraylists.add(0, array1); arraylists.add(1, array2); arraylists.add(2, array3); arraylists.add(3, array4); kwaymerger kwaymerger = new kwaymerger(4, 8, arraylists); system.out.println("排序后，结果为："); kwaymerger.mergekway(); system.out.println(); }
最后运行结果为：
显然结果是正确的，而且我们的方法是支持重复的值的。
以上就是详解k路归并排序（实战）的详细内容。