基于另一个部分列表的排序对列表进行排序的算法

Question

这个问题不同于关于根据另一个列表的顺序对列表进行排序的主题的其他问题，因为顺序列表不包含列表中使用的所有键。

假设我有一个列表 [a, b, c, d, e] 和我的订单列表 [b, d, e]。

现在我将订单列表更改为 [b, e, d]。是否有一个相对简单的算法来求助于原始列表？假设最终顺序是 [a, b, e, c, d] 还是 [a, b, c, e, d] 并不重要，并且订单列表将始终是原始列表的子集。

编辑:从我的示例中清除关于最终排序的一些问题:e 被命令在 b 和 d 之间，并且在排序列表中，e 是否与 b 或 d 相邻并不重要。但是例如，如果由于这种排序 a 移动到 b 之后 - 虽然是合法的排序 - 这是不可取的。

Answer 1

您可以按照 Dennis Callanan 的建议设置自定义比较器，然后对数组进行稳定排序，从而完成您想要的操作。快速排序不是稳定排序；它通常会更改未包含在部分排序中的元素的顺序。归并排序是一种稳定排序。

如果您在比较器中使用线性搜索，我认为该算法的运行时间为 O(n^2 log n)。要使其运行得更快，您需要做的是遍历新数组，散列数组中每个元素的位置以进行快速查找。

我可以用 Java 实现它，但我不懂 Python，抱歉。

对此的另一种观点是使用拓扑排序。在您的原始列表中，您有 a -> b -> c -> d -> e，其中箭头表示“在”b 之前。然后添加新数据 b -> e -> d。你必须打破第一个列表中导致矛盾的任何箭头，即 d -> e。然后你得到的是一堆箭头:

a -> b, b -> c, c -> d, b -> e, e -> d

如果这是一个有向无环图(即没有矛盾)，那么你可以 toposort它在 O(V + E) 时间内。由于边的数量最多为 2n，即 O(n) 时间，非常高效。

问题是决定在原始列表中断开哪些箭头(并可能用其他箭头替换)，这样就不会有任何矛盾。一般来说，这是一个名为 minimum feedback arc set 的 NP 难题但我怀疑您的问题的结构中有些东西会使其运行得更快。

最后，将(非连续的)子数组 [ ..., b, ..., d, e] 中的元素替换为新数组给出的排列怎么样？这可以在 O(n) 时间内完成。