听起来你需要使用自适应排序算法。

“如果排序算法利用其输入中的现有顺序，则它属于自适应排序系列。它受益于输入序列中的预分类性 - 或者对于无序度量的各种定义，无序量有限 - 并且排序更快。自适应排序通常通过修改现有的排序算法来执行。

示例包括插入排序和 Timsort;有关详细信息，请参阅上面的文章。请注意，在 Java 8 中，库方法使用修改后的 Timsort。Arrays.sort(Object[])

我不知道有任何已发布的算法可以处理您示例的特定要求，但这里有一个想法：

1. 对两个输入列表 L1 和 L2 执行经典合并：

   • 当您合并一对对象并且它更改了确定顺序的键时，请将合并的对象放入临时列表 A 中。
   • 否则，请将对象放入临时列表 B ...这将保持有序。

2. 对临时列表 A 进行排序。

3. 合并列表 A 和 B。

假设：

• 原始列表L1和L2的长度分别为M和N，以及
• 键已更改的合并对象数为 R（小于 max（M， N）），

那么整体复杂度是O（M + N + RlogR）。如果R相对于M + N很小，那么这应该是一个改进。

在您的示例中，输入列表中的元素之间存在匹配项的每个情况都可能按顺序移动元素。如果它移动元素，它将按顺序移动到稍后（并且永远不会更早）。因此，另一个想法是在原始的2列表和优先级队列之间进行三向合并。获得匹配项后，将合并计数并将结果添加到优先级队列中。

复杂性与上一个类似，但您可以避免额外的传递来合并列表。并且还成为其中A是优先级队列的平均大小。RlogRRlogA

请记住，我对R大约等于max（M，N）以及M == N的情况特别感兴趣。

（您在问题中没有说明！而且，事实上，将R>min（M，N）没有任何意义！

在这种情况下，也许只需将优先级队列用作增量排序器。将所有合并的记录和所有无法合并的记录扔到队列中，如果它们的键/分数小于两个列表的当前标题，则提取我们的记录。假设 M 和 N 是列表长度，A 是平均优先级队列大小，则复杂度为 max（M，N） * log A）。这是否是对简单重新排序的改进将取决于平均值A是否显着（以大O术语）小于max（M，N）。这将取决于输入...和合并函数。

数字 （N） 各不相同，但 256 到 1，000 是典型的。也许多达10，000。

对于这种典型大小的列表，您处于复杂性分析无济于事的水平。但是，您也处于优化变得毫无意义的水平......除非您多次进行手术，或者在紧张的“时间预算”下进行操作。

这都是非常近似的，我的数学充其量是“粗略的”。

适当的调查将需要数百个小时来研究，编码，测试，基准测试，分析各种替代方案......我们可能仍然会得到答案，这取决于输入数据集的大小和分布。

看起来你想要一个O（n）合并，就像他们使用合并排序一样。我想我可能有一些坏消息要告诉你。我将（希望）证明，对于广义问题，你不能比O（nlog（n））做得更好：（因此，你应该只使用其他人提出的任何最优O（nlog（n））解决方案）。首先，我将从直觉开始，解释为什么会这样，然后我会写一个非正式的证明。

直觉

这个想法是将列表排序的问题变成你的问题，并表明如果你能比O（nlog（n）更快地解决你的问题，那么我可以比O（nlog（n））更快地对任何列表进行排序，我们知道这是错误的。我们将只使用整数来保持简单。

假设您有一些奇怪的序列要排序：.我现在将构建两个列表 Dec 和 Inc。我从（即）开始。然后，如果是增加，我从12月的值中减去1，并在Inc中计算必要的值，以求和为。如果是一个减少，那么我在 Inc 中的值加上 1，并在 Dec 中计算必要的值，以求和为 。我们将此算法应用于下表中的序列：X = 1, 3, 2, -10, 5, 4, 7, 251 = 1 + 0x_1 = x_1 + 0x_{i-1} -> x_ix_ix_{i-1} -> x_ix_i

idx   x     Dec    Inc      
----------------------
 1 |  1  =  1   +  0
 2 |  3  =  0   +  3
 3 |  2  =  -2  +  4
 4 | -10 =  -15 +  5
 5 |  5  =  -16 +  21
 6 |  4  =  -18 +  22
 7 |  7  =  -19 +  23
 8 |  25 =  -20 +  45

请注意，我可以在O（n）中从排序转换为您的问题 - 注意：在O（n）时间内反向Inc以获得两个递减序列。然后，我们可以输入您的问题

A = {(1, 1), (2, 0), (3, -2), (4, -15), (5, -16), (6, -18), (7, -19), (8, -20)}
B = {(8, 45), (7, 23), (6, 22), (5, 21), (4, 5), (3, 4), (2, 3), (1, 0)}

现在，如果您可以将A和B按其值的总和（有序对中的第二个元素）组合成排序顺序，并得到类似的东西

C = {(8, 25), (7, 7), (5, 5), (6, 4), (2, 3), (3, 2), (1, 1), (4, -10)

那么你基本上已经完成了初始序列的argsort（按索引排序）。因此，如果你比O（nlog（n）更快地解决你的问题，那么我可以通过首先解决你的问题，然后将解决方案转换为我的列表排序问题来比O（nlog（n））更快地排序。特别是，我将使用复杂性O（n）+ O（复杂性）进行排序以解决您的问题）x_i

有待证明的声明

让您的两个键值列表成为

A = [(ka_i, va_i) | i = 1..n]
B = [(kb_i, vb_i) | i = 1..m] 

按值的降序排序。找不到组合列表

C = [(ka_i, va_i + va_j) | ka_i = kb_j]

比 O（nlog（n）） 时间快。

校样大纲

这个证明所做的唯一假设是，你不能比O（nlog（n））时间更快地对列表进行排序，并且这个证明将通过提供在O（n）时间内运行的减少来继续，从对任何任意列表进行排序到你的问题。

从本质上讲，我们将证明，如果我们比O（nlog（n）更快地解决您的问题，那么我们也可以比O（nlog（n））更快地对任何任意列表进行排序。我们已经知道不可能比nlog（n）更快地对列表进行排序，因此您所需的解决方案也一定是不可能的。

证明详情

为简单起见，我们将对整数列表进行排序。设为任何整数序列。我们现在将构建两个列表，Dec 和 Inc。S = x_1, x_2, ..., x_n

我们有三个约束：

1. 公司正在严格增加
2. 12月严格减少
3. 在算法的迭代 i 上，Inc[j] + Dec[j] = x_j for all j = 1..i-1

顾名思义，Dec将严格减少，Inc将严格增加。我们将保持不变性x_i = Dec[i] + Inc[i] for i = 1..n

以下是减少：

# (Assume 1-indexed lists)
1. Initialize Inc = [x_1] and Dec = [0]
2. For i = 2..n:
    a. if x[i] > x[i-1] then
          Dec.append(Dec[i-1] - 1)
          Inc.append(x_i - Dec[i])
       else   # We must have x[i] <= x[i-1]
          Inc.append(Inc[i-1] + 1)
          Dec.append(x_i - Inc[i])

3. Create list A and B:
    A = [(i, Dec[i]) | i = 1..n]
    B = [(i, Inc[i]) | i = 1..n]
4. B = reverse(B) # Reverse B because B was in increasing order and we
                  # need both lists to be in decreasing order
5. A and B are inputs to your algorithm.
  If your algorithm can combine A and B into sorted order,
  then we have also sorted S (via argsort on the keys).

您可能还渴望得到一个证据，证明我选择将Inc增加1或将12月减少1的临时方法有效。好吧，这是一个非正式的“证明”（你可以通过使用归纳法将其形式化）：

Case x_{i} > x_{i-1}

回想一下，在本例中，我们选择将 Dec 递减 1。我们得到了这一点，我们知道.我们也可以说.x_{i} > x_{i-1}Dec_{i-1} + Inc_{i-1} = x_{i-1}(Dec_{i-1} - 1) + (Inc_{i+1} + 1) = x_{i-1}

既然 ，我们必须有 .因此。因此，如果我们只将 Dec 递减 1，我们将被迫向 Inc 添加至少 1，因此 Inc 仍然严格增加。x_{i} > x_{i-1}x_{i} >= x_{i-1} + 1x_{i} >= (Dec_{i-1} - 1) + (Inc_{i+1} + 1)

Case x_{i} ≤ x_{i-1}

回想一下，在本例中，我们选择将 Inc 递增 1。我们得到了这一点，我们知道.我们也可以说，既然，那一定是这样的。因此，如果我们向 Inc 添加 1，我们确信必须从 12 月中减去至少 1。x_{i} <= x_{i-1}Dec_{i-1} + Inc_{i-1} = x_{i-1}(Dec_{i-1} - 1) + (Inc_{i+1} + 1) = x_{i-1}x_{i} <= x_{i-1}(Dec_{i-1} - 1) + (Inc_{i+1} + 1) <= x_{i}

结论

您的问题无法比O（nlog（n）更快地完成。您最好只是组合成一个HashMap，然后在O（nlog（n））中对其元素进行排序，因为不可能找到更快的解决方案。

但是，如果您发现减少的问题或有疑问，请随时发表评论。我很确定这是正确的。当然，如果我错误地认为排序速度不比O（nlog（n）快），那么整个证明就崩溃了，但是最后我检查了一下，有人已经证明了O（nlog（n））是排序的最快复杂性。如果您更喜欢正式的减少，请发表评论。对我来说，现在已经很晚了，我跳过了一些“形式化”，但是当我有机会时，我可以编辑它们。

如果您编写用于创建约简的算法，则可以更好地理解。

另外：如果你想解释排序的O（nlog（n））绑定排序，请参阅这篇文章 排序算法的“Ω（n log n）障碍”的规则是什么？