Collections.sort()和Arrays.sort()排序算法选择

Collections.sort()和Arrays.sort()排序算法选择参考:http://blog.sina.com.cn/wangran97java中Arrays.sort使用了两种排序方法,快速排序和优化的合并排序。快速排序主要是对哪些基本类型数据(int,short,long等)排序,而合并排序用于对对象类型进行排序。使用不同类型的排序算法主要是由于快速排序是不稳定的,而合并排序是稳定的。这里的稳定是指比较相等的数据在排序之后仍然按照排序之前的前后顺…

大家好,欢迎来到IT知识分享网。Collections.sort()和Arrays.sort()排序算法选择"

参考:http://blog.sina.com.cn/wangran97

  • java中Arrays.sort使用了两种排序方法,快速排序和优化的合并排序。快速排序主要是对哪些基本类型数据(int,short,long等)排序, 而合并排序用于对对象类型进行排序。使用不同类型的排序算法主要是由于快速排序是不稳定的,而合并排序是稳定的。这里的稳定是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列。对于基本数据类型,稳定性没有意义,而对于对象类型,稳定性是比较重要的,因为对象相等的判断可能只是判断关键属性,最好保持相等对象的非关键属性的顺序与排序前一直;另外一个原因是由于合并排序相对而言比较次数比快速排序少,移动(对象引用的移动)次数比快速排序多,而对于对象来说,比较一般比移动耗时。补充一点合并排序的时间复杂度是n*logn, 快速排序的平均时间复杂度也是n*logn,但是合并排序的需要额外的n个引用的空间
    //Arrays.sort():
        基本数据类型:
             public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }
        对象类型
            public static void sort(Object[] a) {
                if (LegacyMergeSort.userRequested)
                    legacyMergeSort(a);
                else
                    ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
            }

        //Collections.sort():
             Arrays.sort(a, (Comparator) c);

             public static <T> void sort(T[] a, Comparator<? super T> c) {
                 if (c == null) {
                     sort(a);
                 } else {
                     if (LegacyMergeSort.userRequested)
                         legacyMergeSort(a, c);
                     else
                         TimSort.sort(a, 0, a.length, c, null, 0, 0);
                 }
             }

DualPivotQuicksort:双轴快速排序
参考:https://blog.csdn.net/timheath/article/details/68930482
LegacyMergeSort:传统归并排序

ComparableTimSort:归并排序做了大量优化的版本
具体参考:https://blog.csdn.net/bruce_6/article/details/38299199

Arrays类的其他方法

public class Test{
public static void main(String[] args) {
    int[] arr={1,5,8,6,3,4};
    Arrays.sort(arr);
    Test.printArray(arr);
    //注:使用二分查找时,先排序
    int index=Arrays.binarySearch(arr, 8);
    System.out.println("排序后的位置:"+index);
    //copyOfRange:不破坏原数组的部分拷贝
    //fill:用一个元素替换数组的所有值
    //toString:将数组转换为字符串
}
public static void printArray(int[] array){
    System.out.print("[");
    for(int i=0;i<array.length;i++){
        if(i!=array.length-1){
            System.out.print(array[i]+",");
        }else{
            System.out.println(array[i]+"]");
        }
    }
}

}

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/21049.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信