我有一组项目和一个定义部分排序的比较器函数 - 给定两个项目,它返回“=”、“<”、“>”或“未定义排序”(例如“<>”) )。我想生成一个尊重此部分排序的项目排序列表。
如果我寻找进行拓扑排序的算法,它们通常会从有向无环图开始。但我没有 DAG,而且我看不到一种无需进行大量(也许是 N*N?)比较即可构建 DAG 的简单方法。我想要的是某种类似快速排序的算法,它通过比较和交换列表中的选定项目来工作。有这样的算法吗?我假设大多数经典排序算法都会因为不确定性而失败。
我想过尝试使用经典排序算法并将“<>”视为“=”,但它不起作用,因为我可能会出现 A < B, A <> C, B <> C 的情况,所以我不能将 C 视为等于 A 和 B。
有什么想法或指示吗?
最佳答案
您不需要显式创建图来使用拓扑排序算法。
设S
为要排序的元素集合,其中有partial order在S
中。令 used
为字典,将 S
中的每个元素映射到 bool 值(默认为 false
),该值将为 true
当我们访问带有此元素的“节点”时。令 stack
为来自 S
的元素堆栈(默认为空)。
定义一个方法dfs(x)
(x
是S
的一个元素),它执行以下操作:
将
used[x]
设置为true
对于
S
中的每个元素y
:如果
used[y]
为false
并且x
小于或等于y
(*):- 调用
dfs(y)
- 调用
将
x
添加到堆栈
然后:
对于
S
中的每个元素x
:如果
used[x]
为false
:- 调用
dfs(x)
- 调用
在此循环之后,stack
中的元素将被排序(从stack
中弹出的第一个项目是最小的一个( not necessarily minimum ),最后一个项目是最大的一个(不一定是最大值))。
该算法显然运行时间为 O(n^2),因为它仍然是拓扑排序,只是没有显式创建图。
(*):与拓扑排序一样,仅处理从 x
到 y
的边,而不处理从 y
到边的情况到 x
或根本没有边,该算法仅处理“小于或等于”关系。
关于algorithm - 基于比较器(而不是图)的拓扑排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59965812/