虽然有许多排序算法可供选择，但其中大多数仅适用于全序集，因为它们假定任意两个元素是可比较的。 然而，在部分排序集合中是否存在任何好的算法可用于排序，其中一些元素是不可比较的呢？也就是说，给定一个从部分排序集合S中提取出来的元素集合，输出排序x1，x2，...，xn的最佳方法是什么，使得如果 xi ≤ xj，那么i ≤ j？
排序偏序集？
12
- templatetypedef
2
2这不就是拓扑排序吗？ - Josh Lee
2@jleedev- 只有在您事先知道S中每对元素相互比较的方式时，才能使用拓扑排序来完成它；否则，您将不得不花费O（|S|^2）的时间进行所有比较。 - templatetypedef
3个回答
8
这里有一篇名为“Posets中的排序和选择”的论文可在arxiv.org上获取，讨论了O((w^2)nlog(n/w))级别的排序方法，其中w是poset的“宽度”。我没有阅读这篇论文，但看起来它涵盖了您正在寻找的内容。
- Blaise Pascal
1
谢谢提供链接！这看起来非常有前途！ - templatetypedef
2
拓扑排序适用于部分有序集合的排序。大多数算法是O(n^2)。以下是维基百科上的算法：
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
这里有一个有用的视频示例。大多数类Unix系统都有tsort命令。您可以按照以下方式使用tsort解决视频中的布朗尼问题：
$ cat brownies.txt
preheat bake
water mix
dry_ingredients mix
grease pour
mix pour
pour bake
$ tsort brownies.txt
grease
dry_ingredients
water
preheat
mix
pour
bake
- mndrix
0
我会从选择交换排序开始。这是O(n^2)的，我认为你不可能做得比这更好。
- Zeki
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接