使用有限数据对非数字对象进行排序

Question

说我有时可以比较的非数字对象，但有时没有用于比较的数据。

例如：

• A大于B更大，但不与之比较的C.
• B比C更大。

这清楚地创建了一个排序列表A，B,C。

但是，让我们添加大于C的D。由于没有比较D与A或B的数据，因此最终排名并不明确。

我在寻找的是一种用“尽力而为”的方式来排列这些类型的数据点，知道数据有限，最终的排序列表只会被部分排序。

此外，我打算代表这不是一维数组。也许是某种树？

另一个想法是将数据点与大量数据组合在一起，因为它们可以很容易地排序。然后使用组间比较来对组进行排名。问题在于有时一个数据点可以与多个组进行比较。

Answer 1

如果我正确记得大学，这通常是用图算法完成的。对边缘从较大元素变为较小元素的所有项目制作有向图，并跟踪节点有多少入局边。从图形中删除没有传入边的节点 - 减少删除的节点指向的所有节点的传入边数 - 清洗，重复。有关详细信息和算法提示，请致电topological sorting。

如果在任何时候你最终得到一个非空图，其中所有节点都有一个入边，那么你的排序就有一个循环，因此不是一个排序。