k路最佳归并,对n个初始归并并进行k路平衡归并
引入：其实K路归并排序很有用。最简单的就是，假设你要对海量数据进行排序，比如TB级的数据(姑且说是TB级的搜索关键词)，而我们的内存只有GB级。我们不能一次加载所有数据并对它们进行排序，但我们确实希望最终得到结果。那么我们该怎么办呢？k路合并排序登场。其实这是一种“分而治之”的思想。既然要给Q数排序，就不能一次全部排序。这时我们把Q分成K组，每组有N个数，(kn)并假设这里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中最大的数，我们依次删除Min()，按最小的顺序输出最大的数。如果当前堆为空，直接跳出循环。
因此，最终的时间复杂度仅为O(n*logk)
代码：
记住上面的关键技术细节，这里的代码很容易编写。
首先，我们定义一个value对象，它封装了一个整数，以及这个整数来自哪个数组。
package com . Charles . algo . kway merge；
/**
*
*这个对象表示它是一个可以跟踪它来自哪个数组的数据对象。
* @作者charles.wang
*
*/
公共类TrackableData {
//数据表示具体值。
私有int数据；
//comefromrarray指示该值来自哪个数组。
private int comeFromArray
public TrackableData(int data，int comeFromArray){
this.data=data
this . come from array=come from array；
}
public int getData() {
返回数据；
}
public void setData(int data) {
this.data=data
}
public int getcomefromrarray(){
返回comeFromArray
}
public void setcomefroarray(int comefroarray){
this . come from array=come from array；
}
}然后我们定义一个最小堆，这是解决问题的关键。需要注意的是，它包含的元素应该是上述的值对象。进入堆的时候，调整堆，基于堆的计算，都是值对象的数据字段。
package com . Charles . algo . kway merge；
/**
* @作者charles.wang
*
*/
公共类MinHeap {
//最小堆的存储是一个数组，为了计算，我们不把内容放在第一个位置。
私有TrackableData[]数据；
//堆的大小
private int heapSize
//当前元素的数量
private int currentSize
public MinHeap(int maxSize) {
heapSize=maxSize
//创建比最大数多1的数组的作用是启用数组的header元素。为了操作方便，从1开始的运算更容易计算。
data=new trackable data[heap size 1]；
currentSize=0；
}
/**
*返回当前堆是否为空。
* @返回
*/
public boolean isEmpty(){
if(currentSize==0)
返回true
返回false
}
/**
*这里我们检查堆的插入。因为最小堆内部结构中数组前面的元素总是按照最小堆来构建的，所以我们总是从尾部插入。解决方案是：步骤
* 1:首先将当前元素插入数组的末尾。步骤2:递归比较当前元素和父节点元素。步骤
* 3:如果当前元素小于父节点的元素，则向上移动当前元素，直到无法移动为止。
*
* @param值
* @返回
*/
public Minh EAP insert(trackable data值){
//首先判断堆是否已满，如果是，则不能插入。
if (currentSize==heapSize)
还这个；
//如果堆未满，则堆中仍有可插入的位置。让我们找到最后插入的地方。
//currentPos指示要插入的当前位置的数组下标。
int current pos=currentSize 1；
//先插入到当前位置，因为从1开始，所以数组下标操作也需要1。
data[current pos]=value；
//然后将当前元素与其父元素进行比较
//当前元素是data[currentPos]，父元素是data[(currentPos/2)，一直遍历到根。
TrackableData temp
//如果currentPos为1，表示是插入堆中的第一个元素，则不需要比较。
//否则，如果插入了多个元素，则将插入位置的元素与其父元素进行比较。
while (currentPos 1) {
//如果当前元素小于父元素，则交换它们的位置。
if (data[currentPos].getData() data[currentPos/2]。getData()) {
temp=data[current pos/2]；
data[current pos/2]=data[current pos]；
data[current pos]=temp；
//更新当前位置
current pos=current pos/2；
}
//否则，假设现有堆是最小堆，说明现在插入的位置是正确的，不需要转换。
否则{
打破；
}
}
//插入后，将当前堆中的元素数加1。
currentSize
还这个；
}
/**
*这里因为删除堆是最小堆，所以可以肯定删除最小堆就是删除堆的根元素。此外，必须调整剩余堆以保持最小堆。
*因为删除最小元素后最小元素位置有空位，所以解决方法是：步骤1:将堆中最后一个元素复制到这个空位步骤
* 2:依次比较这最后一个元素的值，当前位置的左右子元素的值，从而降低到合适的位置步骤3:从堆数组中移除最后一个元素。
*/
public trackable data delete min(){
//如果最小堆已经为空，则不能删除最小元素。
if (currentSize==0)
返回null
//否则堆不为空，那么最小的元素总是堆中的第一个元素
trackable data minValue=data[1]；
//由于最小的元素已被删除，堆中currentSize的大小将为-1。因此，我们必须为数组中的最后一个元素找到一个合适的新位置。
//堆中的最后一个元素
trackable data last value=data[currentSize]；
//首先将堆中的最后一个元素移动到最小堆的头部
data[1]=last value；
//将堆内部存储数组的最后一个元素清零
data[currentSize]=null；
//并且当前堆的大小应该是-1
currentSize-；
//现在开始调整堆结构，让它还是一个最小堆。
int current pos=1；//当前位置设置为根，从根开始比较左右两边
int left pos=current pos * 2；
TrackableData leftValue
TrackableData rightValue
TrackableData temp
//如果左侧位置与当前堆的总容量相同，则只有2个元素，一个是根元素，一个是根的左侧元素。
if (leftPos==currentSize) {
//此时，如果根左元素数据[2]小于根元素数据[1]，则交换两个元素的位置。
if(数据[2]。getData() data[1]。getData()) {
temp=data[2]；
数据[2]=数据[1]；
data[1]=temp；
}
}
否则{
//保持循环的条件是节点的左边位置小于当前堆中的元素个数，那么节点必须有右边的子元素，并且位置是左边的子元素位置1。
while (leftPos currentSize) {
//获取当前位置左侧子节点的值
left value=data[left pos]；
//获取当前周期中该位置的右子节点的值。
right value=data[left pos 1]；
//如果当前值小于左右两个子节点，则当前值位置是正确的。
if (data[currentPos].getData() leftValue.getData()
数据[当前位置]。get data()right value . get data()){
打破；
}
//否则，将左侧子节点与右侧子节点进行比较
//如果左子节点比右子节点小(当然也比当前节点小)，那么左子节点和当前节点交换位置。
else if(left value . get data()right value . get data()){
temp=data[current pos]；
data[current pos]=left value；
data[left pos]=temp；
//同时更新当前位置是左子节点的位置，新的左子节点的位置是左子节点的左子节点。
currentPos=leftPos
left pos=current pos * 2；
}
//如果右子节点比左子节点小(当然也比当前节点小)，那么右子节点和当前节点交换位置。
否则{
temp=data[current pos]；
data[current pos]=right value；
data[left pos 1]=temp；
//同时更新当前位置是右子节点的位置，新的左子节点是右子节点的左子节点。
current pos=left pos 1；
left pos=current pos * 2；
}
}
}
返回minValue
}
}最后，让我们实现K路合并器，这是相当容易实现的，但当涉及到一些下标操作时，我们必须特别小心。因为我们想通用，K和N都是导入的。事实上，如果我们预先计划好K和N，我们根本不需要在内部维护这些数字，因为我们只需要将它们存储在最小堆中。
package com . Charles . algo . kway merge；
导入Java . util . ArrayList；
导入Java . util . list；
/**
*
*这个类用于演示K路合并。
*
* @作者charles.wang
*
*/
公共类KWayMerger {
二等兵KWayMerger() {
}
/**
* k路合并，这里的指导思想如下：
*
* (1)首先构造一个最小堆，堆中元素的初始值是每个数组中最小的元素。
* (2)每次打印并删除最小堆中的最小元素，然后将这个最小元素所在数组中的下一个元素插入到最小堆中。(3)在每(2)个结束后，调整堆以保持这个最小的堆。
*/
public static void mergeKWay(int k，int n，Listint[] arrays) {
//每个数组的所有当前下标都存储在这里，在开始插入之前，每个数组的当前下标都设置为0。
int[]index inarrays=new int[k]；
for(int I=0；我k；i ) {
index inarrays[I]=0；
}
//首先构造一个最小堆，大小为k。
Minh EAP Minh EAP=new Minh EAP(k)；
//第一步，将每个数组的第一个元素依次插入到最小堆中。
//然后将所有数组的下标指向1
for(int I=0；我k；i ) {
//这里每个构造一个TrackableData对象：
//其中：arrays.get(i)[0]表示其值是第I个数组下标为0的元素(即第I个数组的第一个元素)
//i表示这个对象来自第I个数组。
minheap . insert(new trackable data(arrays . get(I)[0]，I))；
indexInArrays[I]=1；
}
//第二步，反复插入和删除最小堆。
trackable data currentDeletedData；
trackable data currentinsertddata；
int arrayIdForDeletedData
int nextValueIndexInArray
//循环的条件是K个数组中至少有一个数组的值没有插入到minHeap中。
while (true) {
//此变量维护有多少数组的当前下标越界，即数组的所有元素都已被完全处理。
int noOfArraysThatCompletelyHandled=0；
//是用所有数组的当前下标来查询和维护数组。如果它们出界了，就说明它们已经被比较过了。
for(int I=0；我k；i ) {
if (indexInArrays[i]==n)
noofarraysthatcompletely handled；
}
//如果已经比较了所有数组中的所有值，那么检查堆中的内容是否为空。
if(noOfArraysThatCompletelyHandled==k){
而(！minHeap.isEmpty()) {
currentDeletedData=min heap . delete min()；
//打印出当前号码
system . out . print(currentdeleteddata . get data() )；
}
打破；
}
currentDeletedData=min heap . delete min()；
//打印出当前号码
system . out . print(currentdeleteddata . get data() )；
//获取当前删除的数字来自哪个数组。
arrayIdForDeletedData=currentdeleteddata . getcomefromrarray()；
//获取该数组的当前下标
nextValueIndexInArray=indexInArrays[arrayIdForDeletedData]；
//如果当前下标没有越界，当前数组中还有元素，则查找数组中的下一个元素。
if (nextValueIndexInArray n) {
//构造一个新的TrackableData，插入到最小堆中。
currentInsertedData=新的可跟踪数据(
arrays . get(arrayIdForDeletedData)[nextValueIndexInArray]，
arrayIdForDeletedData)；
Minh EAP。insert(currentinsertddata)；
//同时更新维护数组当前下标的数组，让对应数组的当前下标一
indexInArrays[arrayIdForDeletedData]；
}
//如果当前下标已经越界，说明这个数组已经没有任何元素了，则找下一个有值的数组的最小元素
否则{
while (true) {
arrayIdForDeletedData=(arrayIdForDeletedData 1)% k；
//获取那个数组的当前下标
nextValueIndexInArray=indexInArrays[arrayIdForDeletedData]；
if (nextValueIndexInArray==n)
继续；
否则{
//构造新的TrackableData，并且插入到最小堆
currentInsertedData=新的可跟踪数据（
数组。get(arrayIdForDeletedData)[nextValueIndexInArray]，
arrayIdForDeletedData)；
Minh EAP。insert(currentinsertddata)；
//同时更新维护数组当前下标的数组，让对应数组的当前下标一
indexInArrays[arrayIdForDeletedData]；
打破；
}
}
}
}
}
}实验：
最后我们来演示下，假设我们有32个数，我们分为四路合并，每路8个数，并且这8个数是已经排序的。
然后我们用K路合并算法来对所有的32个数进行排序：
公共静态void main(String[] args) {
//我们来演示K路合并，假设我们有四组已经排序了的数组，每组有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,我们分四路合并);
System.out.println(数组一为：);
for(int I=0；IAR射线1。长度；我)
系统。出去。print(array 1[I] )；
系统。出去。println()；
System.out.println(数组2为：);
for(int I=0；IAR射线2。长度；我)
系统。出去。print(array 2[I] )；
系统。出去。println()；
System.out.println(数组3为：);
for(int I=0；IAR射线3。长度；我)
系统。出去。print(array 3[I] )；
系统。出去。println()；
System.out.println(数组四为：);
for(int I=0；IAR射线4。长度；我)
系统。出去。print(array 4[I] )；
系统。出去。println()；
listint[]arrayLists=new arraylistin[](4)；
arrayLists.add(0，数组1)；
arrayLists.add(1，array 2)；
arrayLists.add(2，array 3)；
arrayLists.add(3，array 4)；
KWayMerger KWayMerger=new KWayMerger(4，8，arrayLists)；
System.out.println(排序后，结果为：);
kwaymer ger。merge kway()；
系统。出去。println()；
}最后运行结果为：
写爬虫互联网协议(互联网协议)被封了怎么解决？立即使用
显然结果是正确的，而且我们的方法是支持重复的值的。以上就是详解K路归并排序（实战)的详细内容，更多请关注我们其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。