有序链表集合的排序

Question

我正在寻找一个优雅、高性能的解决方案来解决以下问题。

有256个链表。

每个链表包含相同类型的对象，其中包含一个整数，用于定义排序顺序。

所有列表中的数字都是唯一的。

每个单独的列表按这些数字按升序排序。

如何从256个原始链接列表中创建一个单一的升序排序列表？我不想采用蛮力方法，并且有一些其他想法，但这似乎是那种有标准、最佳解决方案的问题。

- Nerdfest

Answer 1

您可以使用一个优先队列来保存256个链接列表中的“顶部”项目。这个“顶部”项目是计划插入到结果列表中的项目。这样，您只需从优先队列中取出最小的元素，将其插入到结果队列中，并将其下一个元素插入到优先队列中即可：

# Preprocessing:
result = list.new()
queue = priority_queue.new()

foreach (list in lists):
    queue.push(list.first())

# Main loop:
while (not queue.empty()):
    node = queue.pop()
    result.insert(node)
    if (node.next() != null):
        queue.push(node.next())

- Konrad Rudolph

Answer 2

如果单个列表已经排序，则可以直接应用合并算法。简而言之：比较所有头部并选择最小的，将其从其列表中取出并推入输出列表中。重复此过程，直到所有源列表为空。

编辑：Konrad使用优先队列(a 堆)是一种更优雅和可扩展的解决方案，但也许256个输入列表如此少，以至于简单比较可能更快。

- Javier

---

+1，但如果它只在一个列表上运行，合并的速度会更快。 - Mike F

Answer 3

只需将每个列表与其上面的128个列表合并。(结果为128个列表)
然后将每个列表与其上面的64个列表合并。(结果为64个列表)
然后将每个列表与其上面的32个列表合并。(结果为32个列表)
接着将每个列表与其上面的16个列表合并。(结果为16个列表)
然后将每个列表与其上面的8个列表合并。(结果为8个列表)
然后将每个列表与其上面的4个列表合并。(结果为4个列表)
然后将每个列表与其上面的2个列表合并。(结果为2个列表)
最后将每个列表与其上面的1个列表合并。(结果为1个列表)
(您可以使用循环来完成上述操作)。

- paperhorse

Answer 4

您没有说明这些列表的长度，但我假设它们都可以同时放入RAM中。我首先尝试的是将它们全部附加在一起，调用我的环境中内置的排序程序，然后查看是否具有可接受的性能。这很容易实现，也不需要花费太长时间来测试。如果那样并不能提供可接受的性能，我会选择 Konrad Rudolph 给出的优先级队列合并方案。

- Glomek