2

我有多个有序列表。不幸的是，项目的顺序不是简单的字母或数字比较，否则这是微不足道的。所以我所拥有的是：

List #1        List #2       List #3
groundhog      groundhog     easter
mothersday     mayday        mothersday
midsummer      laborday      halloween
christmas

并且从这里我可以收集到比土拨鼠<母亲节，但土拨鼠和复活节的关系是未知的。我保证从列表到列表的项目顺序是自洽的。（即无论它出现在哪个列表中，复活节总是在万圣节之前）

但我需要的是一个新的有序列表，它只代表其他列表中的每个项目一次，它保留了上面所有已知的关系：

groundhog
easter
mayday
mothersday
midsummer
laborday
halloween
christmas

但是，以下列表也是完全有效的：

easter
groundhog
mothersday
mayday
midsummer
laborday
halloween
christmas

我正在寻找一种相当快速的通用算法，我可以用这种算法对 N 个列表进行排序。（工作 C# 代码当然是一个加分项，但不是必需的。）

我有可行的解决方案，但它的 O(N^2) 和一只狗甚至拥有适度的数据集。

4

3 回答 3

5

您可能想看看拓扑排序。我认为它非常适用于您的情况。

于 2008-11-11T21:52:50.070 回答
1

我同意@bdumitriu，你想要拓扑排序。

这种类型的排序假定您的数据项之间存在偏序，这意味着对于某些项对，您可以比较它们以查看哪个在另一个之前。在这种情况下，就像您说的那样，有多种方法可以创建一个保留所有约束的项目列表。

拓扑排序通常通过首先创建项目的有向无环图来工作，其中每个项目成为一个顶点，从节点 X 到节点 Y 的有向边意味着项目 X 在输入列表中位于项目 Y 之前。（因此，您将遍历您的输入排序列表集，每次遇到新项目时，都会为其创建一个顶点，并且对于每个排序列表中的每一对连续项目，您都会从第一项到第二项。请​​注意，您不需要创建从一个项目到每个输入列表中所有先前项目的有向边；例如，在您的输入列表 1 中，您将创建边groundhog-> mothersday，mothersday-> midsummer, 和midsummer-> christmas.)

拓扑排序将花费时间 O(V+E)，其中 V 是您要排序的项目总数（顶点数），E 是输入列表中前导关系的总数（边数） .

——菲尔

于 2008-11-17T22:28:46.697 回答
0

我将使用 Array.Sort 方法和一个比较方法，该方法需要比较两个字符串，然后检查它们是否存在于任何列表中；任何同时包含它们的列表，找到它们的相对位置，并基于此返回；如果没有列表同时包含它们，则返回相等。

MSN 文档指出他们的排序算法使用快速排序；平均 nlog(n) 顺序，最坏的情况是 n^2 的顺序。

这样，您就可以利用他们对排序算法的实现；您所要做的就是实现比较代码。

于 2008-11-11T22:56:36.120 回答