如何使用归并排序对K个已排序数组进行排序

Question

我知道这个问题已经被问过了，并且有一个非常好的优雅的解决方案，使用了最小堆。

我的问题是如何使用归并排序的合并函数来完成此操作。

您已经有了一组排序后的数组。因此，您应该能够在O（nlog K）时间内将它们全部合并为一个数组，对吗？

我只是想不出如何做到这一点！

比如我有

[ [5,6], [3,4], [1,2], [0] ]

步骤1：[ [3,4,5,6], [0,1,2] ]

步骤2：[ [0,1,2,3,4,5,6] ]

有没有简单的方法可以实现这一点？使用归并排序可以理论上实现O（nlog K）吗？

- ordinary

---

每个 N 个元素都必须放入输出中，因此你无法比 O(N) 更快地完成这个操作... - Oliver Charlesworth

哇，你是怎么想在O(log K)的时间复杂度下完成这个任务的？至少要"读取"每个项目一次才行啊！你真的知道对数是什么意思吗？ - Ivan Kuckir

@HotLicks：这会给你O(M.K^2)（其中M是每个列表中的元素数）。我认为通过维护某种下一个元素的最小堆，您可以获得O(M.K.log(K))。 - Oliver Charlesworth

@ordinary：我在谈论合并。但是你需要一些机制来确定下一个要附加到输出数组的元素。我认为使用大小为K的最小堆比使用排序后的大小为K的数组更好。 - Oliver Charlesworth

你问题中展示的步骤就是答案：你合并每一对数组，然后重复这个过程，最终得到O(n logk)的总运行时间。你还需要知道什么？ - interjay

Answer 1

正如其他人所说，使用最小堆来保存下一个元素是最优的方法。它被称为N路归并，其复杂度为O(n log k)。

你可以使用2路归并算法对k个数组进行排序。可能最简单的方法是修改标准的归并排序，使其使用非常量大小的分区。例如，假设你有4个长度分别为10、8、12和33的数组。每个数组都是已排序的。如果将这些数组连接成一个数组，你将得到以下分区（数字是数组中的索引，而不是值）：

[0-9][10-17][18-29][30-62]

你的归并排序第一次将从索引0和10处开始。你会像标准归并排序一样将它们合并到一个新数组中。下一次合并将从第二个数组的位置18和30处开始。完成第二次排序后，输出数组包含：

[0-17][18-62]

现在你的分区从0和18开始。将这两个分区合并成一个数组，你就完成了。

唯一真正的区别是，你不是从分区大小为2开始倍增，而是有非固定分区大小。当你进行每次排序时，新的分区大小是前一次使用的两个分区大小之和。这实际上只是标准归并排序的轻微修改。

排序需要log(k)次操作，并且每次都要检查所有n个元素。该算法的时间复杂度为O(n log k)，但比N路归并的常数要高得多。

对于实现，构建一个包含每个子数组起始索引的整数数组。因此，在上面的示例中，你将拥有：

int[] partitions = [0, 10, 18, 30];
int numPartitions = 4;

现在你执行标准的归并排序。但是你从partitions数组中选择你的分区。因此，你的合并将从以下内容开始：

merge (inputArray, outputArray, part1Index, part2Index, outputStart)
{
    part1Start = partitions[part1Index];
    part2Start = partitions[part2Index];

    part1Length = part2Start - part1Start;
    part2Length = partitions[part2Index-1] - part2Start;

    // now merge part1 and part2 into the output array,
    // starting at outputStart
}

而你的主循环应该类似于：

while (numPartitions > 1)
{
    for (int p = 0; p < numPartitions; p += 2)
    {
        outputStart = partitions[p];
        merge(inputArray, outputArray, p, p+1, outputStart);
        // update partitions table
        partitions[p/2] = partitions[p] + partitions[p+1];
    }
    numPartitions /= 2;
}

那就是基本思路。当数字是奇数时，您需要做一些工作来处理悬空分区，但通常情况下都是这样做的。

您还可以通过维护一个数组的数组，并将每两个数组合并为一个新数组，将其添加到输出数组的数组中来完成。反复操作。

- Jim Mischel

---

谢谢！一个合法的答案。如何使用非标准分区大小实现归并排序？我的做法是递归地进行后序遍历，它会到达树的底部，然后合并2个、翻倍等等。我无法想出一种方法来修改这个版本以适应非标准分区大小。 - ordinary

你不觉得使用你提出的方式（使用最小堆）处理大小为n的k个数组的时间复杂度将会是O(nk logk)而不是O(n logk)吗？ - Hengameh

我听说合并k个已排序数组的最佳方法是使用Min Heap，其时间复杂度为O（nk logk）。因此，如果您的解决方案合并了k个已排序的数组，并且具有O（n logk）的时间复杂度，则您的解决方案将是最优的。 - Hengameh

@Hengameh：不，我的解决方案不会对单独的数组进行排序，只会合并。据我所知，这个合并算法和使用最小堆的算法都是O(nlogk)的时间复杂度。我不知道你从哪里得到了O(nklogk)的值。 - Jim Mischel

@Hengameh：使用最小堆合并k个已排序数组的时间复杂度为O(n log k)，而不是O(nk log k)。请参考http://en.wikipedia.org/wiki/Merge_algorithm或任何标准算法参考资料。 - Jim Mischel

Answer 2

请注意，当我们说复杂度为O(n log k)时，我们假设n表示k个数组中所有元素的总数，即最终合并数组中的元素数量。

例如，如果您想要合并包含n个元素的k个数组，则最终数组中的元素总数将是nk。因此，复杂度将为O(nk log k)。

- Lirrik

Answer 3

我用Python实现了它。主要思路类似于归并排序。在lists中有k个数组。在函数mainMerageK中，只需将列表（k）分成左侧（k/2）和右侧（k/2）。因此，划分的总计数为log(k)。关于函数merge，很容易知道运行时间为O(n)。最后，我们得到O(nlog k)。 顺便说一下，它也可以在最小堆中实现，这里有一个链接：使用优先队列合并K个已排序列表。

def mainMergeK(*lists):
    # implemented by k-way partition
    k = len(lists)
    if k > 1:
        mid = int(k / 2)
        B = mainMergeK(*lists[0: mid])
        C = mainMergeK(*lists[mid:])
        A = merge(B, C)
        print B, ' + ', C, ' = ', A
        return A
    return lists[0]

def merge(B, C):
    A = []
    p = len(B)
    q = len(C)
    i = 0
    j = 0
    while i < p and j < q:
        if B[i] <= C[j]:
            A.append(B[i])
            i += 1
        else:
            A.append(C[j])
            j += 1
    if i == p:
        for c in C[j:]:
            A.append(c)
    else:
        for b in B[i:]:
            A.append(b)
    return A

if __name__ == '__main__':
    x = mainMergeK([1, 3, 5], [2, 4, 6], [7, 8, 10], [9])
    print x

输出结果如下：

[1, 3, 5]  +  [2, 4, 6]  =  [1, 2, 3, 4, 5, 6]
[7, 8, 10]  +  [9]  =  [7, 8, 9, 10]
[1, 2, 3, 4, 5, 6]  +  [7, 8, 9, 10]  =  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

- yinchuandong

Answer 4

合并数组有不同的方法。为了在N*Log(K)的时间内完成这个任务，你可以使用一个叫做Heap的结构（它是实现优先队列的好结构）。我假设你已经有了它，如果没有，那么选择任何可用的实现：http://en.wikipedia.org/wiki/Heap_(data_structure) 然后你可以这样做：

1.  We have A[1..K] array of arrays to sort, Head[1..K] - current pointer for every array and Count[1..K] - number of items for every array.
2.  We have Heap of pairs (Value: int; NumberOfArray: int) - empty at start.
3.  We put to the heap first item of every array - initialization phase.
4.  Then we organize cycle:
5.  Get pair (Value, NumberOfArray) from the heap. 
6.  Value is next value to output.
7.  NumberOfArray – is number of array where we need to take next item (if any) and place to the heap.
8.  If heap is not empty, then repeat from step 5

因此，对于每个项目，我们只使用最多K个项目构建的堆。这意味着我们将具有您所要求的N * Log(K)复杂度。

- Andrei Galatyn

Answer 5

只需像两路合并一样做，但是要使用K个项目。将导致O(NK)。如果您想要O(NlogK)，则需要在下面的算法中使用一个最小堆来跟踪K个指针（以源数组作为元数据）：

保持一个包含K个元素的数组-即显示每个数组中位置的K个指针。 标记所有K个元素都有效。

循环： 比较有效的K个指针中的值。如果该值是最小值，则选择最小的索引指针并将其递增到数组中的下一个值。如果递增值已经超过其数组，则将其标记为无效。 将最小值添加到结果中。 重复直到所有K个元素无效为止。

例如：

Positions        Arrays
p1:0  Array 1:  0  5  10  
p2:3  Array 2:  3  6   9
p3:2  Array 3:  2  4  6

输出 (0, 3, 2) 的最小值为 => 0。因此输出为 {0}

      Array
p1:5    0  5  10
p2:3    3  6   9
p3:2    2  4  6

输出（5、3、2的最小值）=> 2。所以{0,2}

       Array
p1:5    0  5  10
p2:3    3  6  9
p3:4    2  4  6

输出（5、3、4的最小值）=> 3。因此为{0,2,3}，以此类推，直到达到输出为{0,2,3,4,5,6}的状态。

   Array
p1:5    0  5  10
p2:9    3  6  9
p3:6    2  4  6

输出（5、9、6的最小值）=>6。所以当您将p3标记为“无效”时，您已经用完了数组，因此{0,2,3,4,5,6}+{6}。（或者如果您正在使用最小堆，则只需删除最小项，获取其源数组元数据：在本例中为数组3，查看它是否完成，因此您不会向最小堆添加任何新内容）

- arviman