language-agnostic - 对有序链表集进行排序

Question

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

有 256 个链表。

• 每个列表都包含相同类型的对象，其中包含用于定义排序顺序的整数。
• 所有列表中的所有数字都是唯一的
• 每个单独的列表都按这些数字升序排序

你将如何从 256 个原始链表中的所有对象创建一个升序列表？我不想强行使用它，并有其他一些想法，但这似乎是有标准的最佳解决方案的问题之一。

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())

Answer 2

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

编辑：Konrad 使用优先级队列（堆）是一种更加优雅和可扩展的解决方案，但也许 256 个输入列表太少了，简单的比较可能会更快。

Answer 3

只需将每个列表与其上方的列表 128 合并即可。（产生 128 个列表）
然后将每个列表与其上方的 64 个列表合并。（产生 64 个列表）
然后将每个列表与其上方的 32 个列表合并。（产生 32 个列表）
然后将每个列表与上面的列表 16 合并。（产生 16 个列表）
然后将每个列表与上面的列表 8 合并。（产生 8 个列表）
然后将每个列表与上面的列表 4 合并。（产生 4 个列表）
然后将每个列表与上面的列表 2 合并。（产生 2 个列表）
然后将每个列表与其上方的列表 1 合并。（导致 1 个列表）
（您可能会为上述内容使用循环）。

Answer 4

您没有说这些列表有多长，但我假设它们都同时适合 RAM。我会尝试的第一件事是将它们全部附加在一起，并调用我的环境的内置排序例程，我会看看这是否能提供可接受的性能。它很容易实现并且不需要很长时间来测试。如果这不能提供可接受的性能，我会选择 Konrad Rudolph 给出的优先级队列合并。