排序不完整如何排序？

Question

我有一个要排序的元素列表和一个比较函数

cmp(x,y)

，它决定

x

是否应该出现在

y

之前或之后

y

。问题是有些元素没有定义的顺序。

cmp

函数返回“don't care”。

示例：输入：

[A,B,C,D]

、

C > D

、

B > D

。输出：许多正确答案，例如

[D,C,B,A]

或

[A,D,B,C]

。我所需要的只是所有可能输出中的一个输出..

我无法使用Python的

sort

来实现这一点，我的解决方案是老式的冒泡排序从一个空列表开始，然后一次插入一个元素到正确的位置以保持列表全部排序时间。

是否可以使用内置的

sort

/

sorted

函数来实现此目的？关键是什么？

Answer 1

无法为此使用内置排序。相反，您需要实现拓扑排序。

Answer 2

内置排序方法要求

cmp

强制执行 总排序。如果比较不一致，则不起作用。如果参数颠倒，则返回 A < B one time it must always return that, and it must return that B > A。

如果您引入任意的决胜局，您就可以使您的

cmp

实现发挥作用。如果两个元素没有定义的顺序，请补上一个。例如，您可以返回

cmp(id(a), id(b))

——通过对象的任意 ID 号来比较对象。

Answer 3

Python有一些带有部分排序的内置类型，我们可以从中得到启发。其中一种类型是

float

，因为它包含 NaN（非数字）值，这些值与所有内容（包括它们自身）进行无序比较。根据 IEEE 754-2008，

可能存在四种互斥关系：小于、等于、大于和无序。当至少一个操作数为 NaN 时，就会出现最后一种情况。每个 NaN 都应无序地与所有内容（包括其自身）进行比较。

回到 Python，我们可以检查涉及

float

的比较如何表现：

>>> float("NaN") < 5
False
>>> 5 < float("NaN")
False
>>> float("NaN") == float("NaN")
False

因此 Python 通过一致返回

False

来处理无序值的比较。