多个列表的排序组合

难道你不能用修改吗? merge sort ,因为你已经有三个排序列表了?(所谓“modified”,我指的是利用您知道每个输入列表都已经排序这一事实的一些东西。)

假设您不能直接使用合并排序,因为您不想在内存中计算整个新合并的排序列表,那么您可以这样做:在计算第一组合并项并显示这些项的位置使用修改后的合并排序,维护合并排序中使用的指针。你只需坚持你在每个列表中的位置,一个指向每个列表中当前位置的指针,然后选择你为每个块留下的位置。

好吧,我可能会被这个答案激怒。但由于您只需要算法,最好的解决方案是同时使用最佳元素(在本例中是较低的元素,或者是您喜欢的元素)创建结果列表。 使用此方法,您有4个位置,每个要进行平移的列表对应一个位置,最后一个点可以指向需要插入的结果列表中的位置(或插入的最后一个位置)。有了这个,你只需要一个列表。

我发现在这种情况下合并排序有问题。您显示的数据可能不是确切的数据(因为您需要对下一部分进行排序,并且可以与当前部分合并)。

好的,首先举一个二维的例子:

    1  2  3

1   2  3  4
5   6  7  8
7   8  9 10

显然,您从左上角开始,并将该值放入结果列表中。接下来,您必须将所有可到达的候选项(通过递增一个索引)添加到某种排序集合(这里是值为3和6的单元格)中。然后从该集合中取出最低的成员,将其值放入结果列表,将集合中尚未包含的所有可从该集合访问的候选项添加到结果列表中,依此类推。

你需要:

• 包含一个候选对象的数据结构,包含所有索引和结果值(我将其表示为“ ((i1 i2) value) “”。
• 按值排序的候选集合的数据结构。一堆似乎是最理想的。

当您将所有候选项放入集合时,必须确保它们的索引是唯一的。这些值不一定是唯一的,但堆应该按它们排序。由于给定的一组索引总是产生相同的值,因此只有在插入堆时遇到该值时,才必须检查索引的唯一性。这可能是一种优化,使堆的节点不是单个候选节点,而是具有相同值的候选节点列表。

在上面的例子中这样做:首先,结果列表是(2)。候选人是((12)3)和((21)6)。取出值最低的候选项,将值放入结果列表->(2 3),找到所有新候选项的坐标->(2 2)和(13),计算它们的值->((2)7)和((1 3)4),将它们放入候选项堆(此处为序列化表示)->((1 3)4)(2 1)(2)7)、起泡、冲洗、重复。

表格形式:

result-list          candidates
(2)                  ((1 2) 3) ((2 1) 6)
(2 3)                ((1 3) 4) ((2 1) 6) ((2 2) 7)
(2 3 4)              ((2 1) 6) ((2 2) 7) ((2 3) 8)
(2 3 4 6)            ((2 2) 7) ((3 1) 8) ((2 3) 8)
(2 3 4 6 7)          ((3 1) 8) ((2 3) 8) ((3 2) 9)
(2 3 4 6 7 8)        ((2 3) 8) ((3 2) 9)
(2 3 4 6 7 8 8)      ((3 2) 9) ((3 3) 10)
(2 3 4 6 7 8 8 9)    ((3 3) 10)
(2 3 4 6 7 8 8 9 10)

我现在没有更好的办法了。堆似乎需要数量级为n1、n2和n3的节点。