正如其他人所说，使用最小堆来保存下一个项目是最佳方式。它被称为 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;
}
这是基本的想法。当数字为奇数时，您必须做一些工作来处理悬空分区，但一般来说就是这样做的。
您还可以通过维护一个数组数组并将每两个数组合并为一个新数组，将其添加到数组的输出数组中来实现。起泡，冲洗，重复。
您应该注意，当我们说复杂度为 O(n log k) 时，我们假设 n 表示所有 k 个数组中的元素总数，即最终合并数组中的元素数。
例如，如果要合并 k 个数组，每个数组包含 n 个元素，则最终数组中的元素总数将为 nk。所以复杂度将是 O(nk log k)。
有不同的方法来合并数组。要在 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) 复杂度。
我在python中实现了它。主要思想类似于归并排序。列表中有 k 个数组。在函数 mainMerageK 中，只需将列表 (k) 分为左 (k/2) 和右 (k/2)。因此，分区的总数为 log(k)。关于函数合并，很容易知道运行时间是 O(n)。最后得到 O(n log k) 顺便说一下，也可以在 min heap 中实现，有一个链接：Merging K-Sorted Lists using Priority Queue
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]
就像一个 2-way 合并一样，除了 K 项。将导致 O(NK)。如果你想要 O(N logK)，你需要使用最小堆来跟踪下面算法中的 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。所以 {0,2,3,4,5,6}+{6} 当您将 p3 标记为“无效”时，因为您已经用尽了数组。（或者，如果您使用的是最小堆，您只需删除最小项，获取它的源数组元数据：在这种情况下，数组 3，请注意它已完成，因此您不会向最小堆添加任何新内容）