具有自定义比较器的Collections.sort（）是否对每对（a，b）进行比较（a，b）和比较（b，a）

将Collections.sort（）与自定义比较器一起使用时，具有自定义比较器的Collections.sort（）是否对每对（a，b）进行比较（a，b）和比较（b，a）

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

Google上搜寻有关此错误后，我看到若干问题的解释是说，如果comapare（A，b）给我-1和比较（b，A）也给了我-1，那么我会看到这个错误。

我不明白为什么比较会发生两次？

来源

2016-03-29 user3344591

只需修复您的比较器。找出排序例程所做的“比较”调用的确切顺序不会对你有所帮助;只要输出结果是排序的，排序就可以随意进行任何比较，而不同的Java版本和实现可以完成不同的事情。 – user2357112

我知道我的比较器有问题。我只是试图了解比较是否每次都发生一次以上 – user3344591

对于每一对都不会发生;那就是O（n^2）比较，Collections.sort是O（n log n）。 –

JavaDoc of Comparable's compareTo()

实现程序必须确保的sgn（则x.compareTo（Y））== -sgn（y.compareTo（X））对于所有的x和y。（这意味着，如果y.compareTo（x）抛出异常，则x.compareTo（y）必须抛出异常。）

实现者还必须确保该关系是可传递的：（x.compareTo（y）> 0 y.compareTo（z）> 0）意味着x.compareTo（z）> 0。

最后，对于所有z，实现者必须确保x.compareTo（y）== 0意味着sgn（x.compareTo（z））== sgn（y.compareTo（z））。

简单地说，它意味着：

如果x.compareTo(y)抛出一个异常，y.compareTo(x)也应该抛出异常。
如果x > y，并y > z，然后x > z
如果x.compareTo(y) == 0，然后x.compareTo(z)和y.compareTo(z)应该具有相同的符号。

总之：如果a == b，然后b == a。如果没有，你违反了合同。

来源

2016-03-29 17:56:59 Jaims

从Java 1.8开始，Collections.sort(..)将工作交给List#sort()，该工作将工作交给Arrays.sort(..)，该工作将作业交给TimSort。 Here's a link to the API and code used for that algorithm.

这是相当混乱和复杂（出于很好的理由 - 优化排序算法很重要），但足以说它永远不能保证（甚至暗示）每一对元素只被比较一次。它最多可以保证O（n * logn）的比较，但不是它们将是唯一的比较。

来源

2016-03-29 18:37:00 Mshnik

具有自定义比较器的Collections.sort（）是否对每对（a，b）进行比较（a，b）和比较（b，a）

回答

相关问题