java - 排序松散可比数据的算法？

Question

假设我有一个包含四个对象的未排序列表:[B, C, A, D] .

所有四个对象都是同一类型，并且:

  (A > B),
  (C > D),
  (A != C or D)
  (B != C or D)
  (C != A or B)
  (D != A or B).

通过 !=我的意思是它们既不小于、等于或大于其他对象。

我需要对列表进行“排序”，使得 A总是会在 B 之前出现, 和 C总是会在 D 之前出现.除了这两个要求之外，我对列表的排序没有任何要求；因此，给定前面描述的列表，排序函数应该返回 [A, B, C, D]或 [C, D, A, B] .

至于这个问题的原因，我正在尝试对 java.lang.Class 的数组进行排序对象基于它们之间的关系。例如，如果 A是 B 的父类(super class)/超接口(interface), 然后 A小于 B .如果A扩展/实现 B , 然后是 A大于B .如果A是B , 那么显然 A等于 B .否则，A完全无法与相比B.

Answer 1

构建图表。对于满足 x > y 的每两个元素 x 和 y，添加从 x 到 的有向边>y。在您的示例中，您将拥有 A -> B 和 C -> D。然后运行 ​​topological sort在这张图上。返回的拓扑排序将是一个可能的解决方案。