algorithm - 知道对顺序的一组元素的排序算法

Question

这是一个我正在寻找算法解决方案的问题。假设我们有一组 n 个元素，A1, A2, ..., An并且我们有一组规则，如 A1 > A2、A1 < A3 等。规则足以手动编写排序列表。有没有已知的排序方法？我不想像循环一样进行冒泡排序，我正在寻找标准解决方案。有任何想法吗？一个名字对我来说就足够了!

提前致谢。

Answer 1

基于比较的排序算法只有在您有 total ordering 时才有效，也就是说，如果对于每对 x, y与 x != y ，我们知道是否x < y或 y < x .你拥有的是 partial ordering在你的元素集上，你正在寻找的是 toplogical ordering根据该部分顺序的元素。

要找到它，请将您的输入解释为有边的图 (a, b)其中 a < b是输入对。然后做一个DFS在该图上:

dfs(x):
  if x is visited: return
  for every rule x < y or y > x:
    dfs(y)
  add x to front of output

output = []
for every element x:
  dfs(x)

运行时间是O(n + m)其中 n是元素(节点)的数量，m是规则(边)的数量。