使用非传递比较器进行排序是否“有效”？

Question

如果我向Collections.sort提供一个非传递的Comparator，会发生什么？ 会陷入无限循环吗？

我写了一个小测试并产生了输出，但我想确保这种情况始终如此。

问题在于，在某些情况下，我的比较器可能会产生循环，而在这种情况下，我只想确保它不会陷入无限循环。 我不关心实际结果。

- duduamar

---

也许可以发布一些相关的代码？ - pap

这是一个一般性问题，与特定代码无关 - 问题是如果我提供一个不具有传递性的比较器给Collections.sort，它会有什么行为？ - duduamar

使用非传递性的“比较器”行为是未定义的，因为非传递性的“比较器”没有得到正确实现。在实践中，我相当确定如果“比较器”出现问题，“Collections.sort()”也不会无限循环。但规范中没有要求这种行为。 - Joachim Sauer

Answer 1

Java文档指出，您必须确保您的比较器是可传递的。如果您提供的比较器不遵守要求，那么一切都是未知的。它可能对于某个实现有效，但在另一个实现中可能会崩溃（例如C++中的std::sort）。

简而言之，即使它对某些示例起作用，您也不应该依赖它的工作。

- Pablo

---

嗨，Pablo。很抱歉打扰你的评论，但我在这里提出了一个问题：https://stackoverflow.com/questions/45599509/why-does-stdsort-segfault-with-non-transitive-comparators您显然也遇到了我今天面临的问题，即C++ std::sort与非传递比较器崩溃。我想知道您是否知道原因？再次抱歉打扰了一个六年前的评论，但关于这个问题几乎没有什么数据。 - Mike B

Answer 2

自Java 7起，Collections.sort使用TimSort。在Java >=7中使用不可传递比较器进行排序将引发以下异常：

java.lang.IllegalArgumentException: Comparison method violates its general contract!

- Martin

Answer 3

Collections.sort()基于归并排序。

归并排序总共具有O(logn)次迭代，因为数组大小始终被划分，所以排序应该会结束，无论比较器是否是传递的，所以不会出现无限循环。

但是，无法保证结果列表的顺序。

- amit

---

这是一个好的评论，但实现可能会在没有通知的情况下发生变化... - duduamar

是的。它在Java 7中发生了变化。 - vz0

Answer 4

在这种情况下，Collections.sort的行为取决于具体实现。Java 6 SE实现使用Mergesort和Insertionsort的组合，这两个排序算法都是非可传递比较器的确定性算法。但是在Java 7中，会使用Timsort算法，而其他实现可能会使用Quicksort或其他算法，因此您无法确保它将适用于所有实现。

- x4u

Answer 5

首先，我建议您考虑比较 - 比较操作是否真正是等价关系。 如果您认为它不是，并且必须是 - 跟踪一些本地变量中的比较对象。 这个本地变量可以是比较对象或线程本地变量。 这个变量可以是被比较对象对的集合。在compare方法调用内部检查是否访问了这对对象 - 如果为真，则决定要做什么。 但要注意已访问对象的集合 - 它应该真正包含类似哈希或对象ID的东西，因为否则可能会无限制地进行。 还要考虑到将比较的对存储在本地变量中会消耗内存。

- Max