`

Collections.sort 的排序问题

    博客分类:
  • JDK
阅读更多

 

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

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

 

 

0
0
分享到:
评论

相关推荐

    java List 排序 Collections.sort

    当我们需要对List中的元素进行排序时,`Collections.sort()`方法就派上了用场。这个方法能够根据元素的自然顺序或者自定义的比较器进行排序。本文将深入探讨`Collections.sort()`的使用、原理以及如何自定义排序规则...

    java中Collections.sort排序详解

    Java中Collections.sort排序详解 Java中的Collections.sort排序是Java.util.Collections类中的一个静态方法,用于对列表进行排序。下面将详细介绍Collections.sort排序的使用和实现机制。 Collections.sort()方法...

    Java Arrays.sort和Collections.sort排序实现原理解析

    Java中的`Arrays.sort()`和`Collections.sort()`是两个常用的排序函数,它们分别用于对数组和集合进行排序。这两个函数在内部实现上有所不同,但都基于高效的排序算法。 首先,`Collections.sort()`方法在处理列表...

    java中Collections.sort排序函数用法详解

    在Java编程语言中,`Collections.sort()` 是一个非常重要的函数,它用于对集合中的元素进行排序。这个函数是 `java.util.Collections` 类的一个静态方法,适用于列表(List)类型的集合。`Collections.sort()` 可以...

    Java Collections.sort()实现List排序的默认方法和自定义方法

    Java Collections.sort()实现List排序的默认方法和自定义方法 Java Collections.sort()是Java语言中用于对List进行排序的方法,通过使用这个方法可以对List进行默认排序,也可以根据需要实现自定义的排序规则。 ...

    详解Java中Collections.sort排序

    在Java编程语言中,`Collections.sort()`方法是一个非常重要的工具,它用于对集合中的元素进行排序。这个方法主要应用于`List`接口的实现类,如`ArrayList`和`LinkedList`等。`Collections.sort()`有两种主要的排序...

    JAVA对list集合进行排序Collections.sort()

    在Java编程语言中,`Collections.sort()` 方法是一个非常重要的工具,用于对List接口实现的集合进行排序。这个方法使得开发者能够方便地按照指定的顺序排列集合中的元素。本篇文章将详细探讨如何使用 `Collections....

    Java Collections.sort()排序代码案例

    Java Collections.sort() 排序代码案例是 Java Collections 框架中一个非常重要的排序算法,通过本文,我们将深入探讨 Java Collections.sort() 排序代码案例的实现细节,并对其进行详细的解释。 Java Collections...

    详解java Collections.sort的两种用法

    Java Collections.sort 是 Java 集合框架中的一种静态方法,用于对 List 类型进行排序。该方法有两种参数形式,分别是对基本类型和自定义类的排序。在本文中,我们将通过示例代码来详细介绍这两种用法。 基本类型的...

    用Java集合中的Collections.sort方法如何对list排序(两种方法)

    在Java编程中,集合框架是处理数据的重要工具,而Collections.sort方法则是对列表(List)进行排序的关键函数。本文将深入探讨两种使用Collections.sort方法对List排序的方法。 首先,第一种方法是让List中的对象实现...

    listview按序排列显示

    在这个场景下,我们使用`Collections.sort()`函数对一个包含Map对象的List进行排序,然后将排序后的数据适配到ListView中。以下是关于这个主题的详细解释。 **一、Map与List的关系** 在Java中,Map是一种键值对的...

    JAVA中Collections工具类sort()排序方法

    通过了解和掌握`Collections.sort()`方法的两种形式,开发者可以更灵活地处理集合排序问题,提升代码的可读性和可维护性。在编写Java程序时,充分利用这些工具类的方法,可以提高开发效率并保证代码质量。

    金陵科技学院软件院大二上Java高级1215Collections.docx

    在示例中,`Collections.sort(list)`按照默认的自然顺序对元素进行排序,使得`list`变为"123", "123", "aaa", "abc", "xyz"。 3. **`Collections.shuffle(List&lt;T&gt; list, Random rnd)`**:这个方法将列表中的元素...

    Collections

    * `Collections.sort(List&lt;T&gt; list)`: 对列表进行自然排序。 * `Collections.sort(List&lt;T&gt; list, Comparator&lt;? super T&gt; c)`: 对列表进行自定义排序。 线程安全操作 Collections 中的线程安全操作方法包括同步和不...

    java 使用Collections类对List的排序操作

    1. **自然排序**:如果 `List` 中的元素是实现了 `Comparable` 接口的对象,那么可以使用 `Collections.sort()` 方法进行自然排序。`Comparable` 接口定义了一个 `compareTo()` 方法,该方法用于比较对象之间的大小...

    Java Collections.pdf

    例如,Collections.sort()方法可以对List进行排序,而Collections.synchronizedXXX()方法则可以帮助我们创建线程安全的集合。 在实际开发中,选择合适的集合类型和方法至关重要。例如,当我们需要保持元素插入顺序...

    java sort排序算法实例完整代码

    - **`Collections.sort()`**: 用于对实现了`List`接口的集合进行排序。同样支持自定义比较逻辑,通过提供`Comparator`。 ### 2. TimSort算法 Java的`sort`方法采用了一种称为TimSort的稳定排序算法,由Tim Peters在...

    Collections集合工具类排序.docx

    首先,`sort(List&lt;T&gt; list)`方法是Collections工具类中最常用的排序方法之一,它根据列表中元素的自然排序(natural ordering)来对列表进行排序。自然排序是指列表中的元素必须实现Comparable接口,该接口定义了一...

    java 字符串排序

    字符串数组 排序

    arrayList排序

    首先,ArrayList本身并不提供直接的排序功能,但我们可以借助Java提供的`Collections.sort()`方法来实现排序。`Collections.sort()`是一个通用的方法,可以对List接口的实现类进行排序。在使用这个方法前,确保...

Global site tag (gtag.js) - Google Analytics