具有自定義比較器的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）

回答

相關問題