language-agnostic - 排序一个poset？

Question

有大量的排序算法，但它们中的大多数只适用于完全有序的集合，因为它们假设任何两个元素都是可比的。但是，有没有什么好的算法可以对偏序集进行排序，其中某些元素是无法比较的？也就是说，给定从偏序集抽取的一组 S 元素，输出排序 x1, x2, ..., xn 使得如果 xi ≤ xj, i ≤ j 的最佳方法是什么？

Answer 1

有一篇论文题为 Sorting and Selection in Posets arxiv.org 上讨论了 O((w^2)nlog(n/w)) 顺序的排序方法，其中 w 是偏序集的“宽度”。我没有读过这篇论文，但它似乎涵盖了你正在寻找的内容。