Collections.sort 的排序問題

今天運作了一段時間的代碼突然爆出異常。資訊如下：

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

 at java.util.TimSort.mergeLo(TimSort.java:747)

 at java.util.TimSort.mergeAt(TimSort.java:483)

 at java.util.TimSort.mergeCollapse(TimSort.java:408)

 at java.util.TimSort.sort(TimSort.java:214)

 at java.util.TimSort.sort(TimSort.java:173)

 at java.util.Arrays.sort(Arrays.java:659)

 at java.util.Collections.sort(Collections.java:217)

 at com.world.model.daos.actban.ActBanEntrustRecordDao.buyListFromList(ActBanEntrustRecordDao.java:386)

 at com.world.model.daos.actban.ActBanEntrustRecordDao.listFromList(ActBanEntrustRecordDao.java:428)

 at com.world.entrust.handler.actban.ActBanRecordHandler.run(ActBanRecordHandler.java:64)

 at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1145)

 at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)

 at java.lang.Thread.run(Thread.java:724)

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

 at java.util.TimSort.mergeLo(TimSort.java:747)

 at java.util.TimSort.mergeAt(TimSort.java:483)

 at java.util.TimSort.mergeCollapse(TimSort.java:408)

 at java.util.TimSort.sort(TimSort.java:214)

 at java.util.TimSort.sort(TimSort.java:173)

 at java.util.Arrays.sort(Arrays.java:659)

 at java.util.Collections.sort(Collections.java:217)

 at com.world.model.daos.actban.ActBanEntrustRecordDao.buyListFromList(ActBanEntrustRecordDao.java:386)

 at com.world.model.daos.actban.ActBanEntrustRecordDao.listFromList(ActBanEntrustRecordDao.java:428)

 at com.world.entrust.handler.actban.ActBanRecordHandler.run(ActBanRecordHandler.java:64)

 at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1145)

 at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)

 at java.lang.Thread.run(Thread.java:724)

檢查代碼：

class ComparatorRecordPriceAsc implements Comparator {

   public int compare(Object arg0, Object arg1) {

    ActBanEntrustRecord record0 = (ActBanEntrustRecord) arg0;

    ActBanEntrustRecord record1 = (ActBanEntrustRecord) arg1;

    int flag = 0;

    if (record0.getPrice() > record1.getPrice()) {

     flag = 1;

    } else {

     flag = -1;

    }

    return flag;

   }

  }

在比較的時候，将漏了相等的情況，是以永遠沒有傳回0的情況了。這在jdk6的時候，沒有問題。在JDK 1.7 JDK7中的Collections.Sort方法實作中，如果兩個值是相等的，那麼compare方法需要傳回0，否則 可能 會在排序時抛錯。

是以将程式修改，将大于、小于、等于的情況都傳回值就可以了。

如：

class ComparatorRecordPriceAsc implements Comparator {

   public int compare(Object arg0, Object arg1) {

    ActBanEntrustRecord record0 = (ActBanEntrustRecord) arg0;

    ActBanEntrustRecord record1 = (ActBanEntrustRecord) arg1;

    int flag = 0;

    if (record0.getPrice() > record1.getPrice()) {

     flag = 1;

    } else if(record0.getPrice() < record1.getPrice()) {

     flag = -1;

    }

    return flag;

   }

  }

究其原因是JDK1.7 對sort的排序方法做了優化，同時也繼續相容舊模式的排序，是以有人的解決這個異常的問題是重用舊的排序方法，通過設定系統屬性

  System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

讓排序方法使用舊模式來解決異常，我覺得還是按照标準寫法，對比較的三種結果都傳回對應的值，并使用JDK1.7的TimSort排序，性能更優。

 public static <T> void sort(T[] a, Comparator<? super T> c) {

        if (LegacyMergeSort.userRequested)

            legacyMergeSort(a, c);

        else

            TimSort.sort(a, c);

    }

而TimSort排序是一種優化的歸并排序，它将歸并排序(merge sort) 與插入排序(insertion sort) 結合，并進行了一些優化。對于已經部分排序的數組，時間複雜度遠低于 O(n log(n))，最好可達 O(n)，對于随機排序的數組，時間複雜度為 O(nlog(n))，平均時間複雜度 O(nlog(n))。

它的整體思路是這樣的：

1. 周遊數組，将數組分為若幹個升序或降序的片段，（如果是降序片段，反轉降序的片段使其變為升序），每個片段稱為一個Runtask
2. 從數組中取一個RunTask，将這個RunTask壓棧。
3. 取出棧中相鄰兩個的RunTask，做歸并排序，并将結果重新壓棧。
4. 重複(2),(3)過程，直到所有資料處理完畢。