基于比较器（而不是图形）的拓扑排序
Topological sort based on a comparator (rather than a graph)
我有一组项目和一个定义偏序的比较器函数——给定两个项目，它 returns“=”、“<”、“>”或 "no defined ordering" （说“<>”）。我想生成一个符合此部分排序的项目排序列表。
如果我寻找进行拓扑排序的算法，它们通常从有向无环图开始。但是我没有 DAG，而且我看不到一种不进行大量（可能是 N*N？）比较就可以构建 DAG 的简单方法。我想要的是某种类似 QuickSort 的算法，它通过比较和交换列表中的选定项目来工作。有这样的算法吗？我假设大多数经典排序算法都会因为不确定性而失败。
我想尝试使用经典排序算法并将“<>”视为“=”，但它不起作用，因为我可能遇到这种情况 A < B, A <> C, B <> C，所以我不能将 C 视为等于 A 和 B。
有什么想法或建议吗？
您无需显式创建图即可使用拓扑排序算法。
设S为要排序的元素集合，S中有一个partial order。设 used 是将每个元素从 S 映射到布尔值（默认情况下为 false ）的字典，当我们访问 'node' 时，该值将是 true这个元素。设 stack 为 S 中的元素堆栈（默认为空）。
定义一个方法 dfs(x)（x 是 S 的一个元素），它执行以下操作：
将used[x]设置为true
对于S中的每个元素y：
如果used[y]是false且x小于或等于y(*):
- 致电
dfs(y)
将x添加到stack
然后：
对于S中的每个元素x：
如果used[x]是false:
- 致电
dfs(x)
此循环后，stack中的元素将被排序（从stack中弹出的第一项是最小项（not necessarily minimum），最后一项是最大项（不一定最大值)).
这个算法显然在 O(n^2) 中运行，因为它仍然是一种拓扑排序，只是没有显式创建图。
(*)：像拓扑排序一样，只处理从 x 到 y 的边，不处理边从 y 到 x 的情况，或者根本没有边，这个算法只处理 'less than or equal to' 个关系。
我有一组项目和一个定义偏序的比较器函数——给定两个项目，它 returns“=”、“<”、“>”或 "no defined ordering" （说“<>”）。我想生成一个符合此部分排序的项目排序列表。
如果我寻找进行拓扑排序的算法，它们通常从有向无环图开始。但是我没有 DAG，而且我看不到一种不进行大量（可能是 N*N？）比较就可以构建 DAG 的简单方法。我想要的是某种类似 QuickSort 的算法，它通过比较和交换列表中的选定项目来工作。有这样的算法吗？我假设大多数经典排序算法都会因为不确定性而失败。
我想尝试使用经典排序算法并将“<>”视为“=”，但它不起作用，因为我可能遇到这种情况 A < B, A <> C, B <> C，所以我不能将 C 视为等于 A 和 B。
有什么想法或建议吗？
您无需显式创建图即可使用拓扑排序算法。
设S为要排序的元素集合，S中有一个partial order。设 used 是将每个元素从 S 映射到布尔值（默认情况下为 false ）的字典，当我们访问 'node' 时，该值将是 true这个元素。设 stack 为 S 中的元素堆栈（默认为空）。
定义一个方法 dfs(x)（x 是 S 的一个元素），它执行以下操作：
将
used[x]设置为true对于
S中的每个元素y：如果
used[y]是false且x小于或等于y(*):- 致电
dfs(y)
- 致电
将
x添加到stack
然后：
对于
S中的每个元素x：如果
used[x]是false:- 致电
dfs(x)
- 致电
此循环后，stack中的元素将被排序（从stack中弹出的第一项是最小项（not necessarily minimum），最后一项是最大项（不一定最大值)).
这个算法显然在 O(n^2) 中运行，因为它仍然是一种拓扑排序，只是没有显式创建图。
(*)：像拓扑排序一样，只处理从 x 到 y 的边，不处理边从 y 到 x 的情况，或者根本没有边，这个算法只处理 'less than or equal to' 个关系。