algorithm - 如何使用 MERGE SORT 对 K 个排序数组进行排序

Question

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

我的问题是如何使用合并排序的合并功能来做到这一点。

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

我只是不知道该怎么做!

说我有

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

第 1 步:[ [3,4,5,6], [0,1,2] ]

第二步:[ [0,1,2,3,4,5,6] ]

有没有简单的方法来做到这一点？ O(nlog K) 在理论上可以通过归并排序实现吗？

Answer 1

正如其他人所说，使用最小堆来保存下一个项目是最佳方式。这称为 N 路合并。其复杂度为 O(n log k)。

您可以使用双向合并算法对 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;
}

这是基本的想法。当数字为奇数时，您将不得不做一些工作来处理悬空分区，但通常情况就是这样。

您也可以通过维护数组数组，将每两个数组合并为一个新数组，将其添加到数组的输出数组来实现。起泡沫，冲洗，重复。