对已排序的链接列表进行排序

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

如果个人名单已经排序，那么它是一个直接应用merge algorithm。简而言之：比较所有头部并挑选最小的头部，将其从列表中取出并推入输出列表。重复，直到所有源列表都为空。编辑：Konrad使用优先级队列（heap）是一种更加优雅和可扩展的解决方案，但是256个输入列表可能很少，以至于简单的比较可能会更快。

Answer 3

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

Answer 4

你不会说这些列表有多长，但我认为它们都可以同时装入RAM中。我会尝试的第一件事就是将它们全部附加在一起，然后调用我的环境的内置排序例程，然后我会看看它是否能够提供可接受的性能。这很容易实现，不需要很长时间来测试。如果这没有给出可接受的表现，我会选择康拉德鲁道夫给出的优先队列合并。