欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Collections.sort 的排序问题

程序员文章站 2022-04-16 23:33:44
...

 

今天运行了一段时间的代码突然爆出异常。信息如下:

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)过程,直到所有数据处理完毕。

 

 

相关标签: Collection sort