文档章节

java中Arrays.sort()实现原理

liujiest
 liujiest
发布于 2016/05/07 17:30
字数 955
阅读 863
收藏 2

先在网上找到一些说法:

        java中Arrays.sort使用了两种排序方法,快速排序和优化的合并排序。

        快速排序主要是对哪些基本类型数据(int,short,long等)排序, 而合并排序用于对对象类型进行排序。
        使用不同类型的排序算法主要是由于快速排序是不稳定的,而合并排序是稳定的。这里的稳定是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列。对于基本数据类型,稳定性没有意义,而对于对象类型,稳定性是比较重要的,因为对象相等的判断可能只是判断关键属性,最好保持相等对象的非关键属性的顺序与排序前一直;另外一个原因是由于合并排序相对而言比较次数比快速排序少,移动(对象引用的移动)次数比快速排序多,而对于对象来说,比较一般比移动耗时。

        补充一点合并排序的时间复杂度是n*logn, 快速排序的平均时间复杂度也是n*logn,但是合并排序的需要额外的n个引用的空间 ......


自定义比较接口:

sort(T[] a, Comparator<? super T> c)

class Dog{  
    int size;  
    int weight;  
   
    public Dog(int s, int w){  
        size = s;  
        weight = w;   
    }  
}  
   
class DogSizeComparator implements Comparator<Dog>{  
   
    @Override  
    public int compare(Dog o1, Dog o2) {  
        return o1.size - o2.size;  
    }  
}  
   
class DogWeightComparator implements Comparator<Dog>{  
   
    @Override  
    public int compare(Dog o1, Dog o2) {  
        return o1.weight - o2.weight;  
    }  
}  
   
public class ArraySort {  
   
    public static void main(String[] args) {  
        Dog d1 = new Dog(2, 50);  
        Dog d2 = new Dog(1, 30);  
        Dog d3 = new Dog(3, 40);  
   
        Dog[] dogArray = {d1, d2, d3};  
        printDogs(dogArray);  
   
        Arrays.sort(dogArray, new DogSizeComparator());   
        printDogs(dogArray);  
   
        Arrays.sort(dogArray, new DogWeightComparator());     
        printDogs(dogArray);  
    }  
   
    public static void printDogs(Dog[] dogs){  
        for(Dog d: dogs)  
            System.out.print("size="+d.size + " weight=" + d.weight + " ");  
   
        System.out.println();  
    }  
}

为何使用"super"
        如果使用 "Comparator < T > c" 那是很简单易懂的,但是sort的第2个参数里面的 < ? super T > 意味着比较器所接受的类型可以是T或者它的超类. 为什么是超类呢? A:这允许使用同一个比较器对不同的子类对象进行比较。

基本类型源码:

/**
     * Sorts the specified array into ascending numerical order.
     *
     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
     * offers O(n log(n)) performance on many data sets that cause other
     * quicksorts to degrade to quadratic performance, and is typically
     * faster than traditional (one-pivot) Quicksort implementations.
     *
     * @param a the array to be sorted
     */
    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);
    }

ComparableTimSort.sort:

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
        assert a != null && lo >= 0 && lo <= hi && hi <= a.length;

        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a "mini-TimSort" with no merges
        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi);
            binarySort(a, lo, hi, lo + initRunLen);
            return;
        }

        /**
         * March over the array once, left to right, finding natural runs,
         * extending short natural runs to minRun elements, and merging runs
         * to maintain stack invariant.
         */
        ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
        int minRun = minRunLength(nRemaining);
        do {
            // Identify next run
            int runLen = countRunAndMakeAscending(a, lo, hi);

            // If run is short, extend to min(minRun, nRemaining)
            if (runLen < minRun) {
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen);
                runLen = force;
            }

            // Push run onto pending-run stack, and maybe merge
            ts.pushRun(lo, runLen);
            ts.mergeCollapse();

            // Advance to find next run
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);

        // Merge all remaining runs to complete sort
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 1;
    }

这里发现如果元素少于MIN_MERGE=32采用binarySort(二分排序);后面还有些判断bulabula,最后采用mergeForceCollapse(归并排序)。

真实情况还要看JDK版本,这里我用的是JDK8

4. 小结
与Arrays.sort()相关的信息总结如下:

  1. 通用: super 类

  2. 策略设计模式(strategy pattern);

  3. 归并排序(merge sort): 时间复杂度 n*log(n);

  4. Java.util.Collections#sort(List < T > list, Comparator < ? super T > c)与Arrays.sort 使用类似的思想.


© 著作权归作者所有

共有 人打赏支持
liujiest
粉丝 7
博文 66
码字总数 28338
作品 0
杭州
程序员
455. Assign Cookies - LeetCode

Question 455. Assign Cookies Solution 题目大意:数组g的大小表示有几个小孩,每个元素表示小孩的食量,数组s的大小表示有多少个饼干,每个元素的大小表示每个饼干的大小,把饼干分给小孩,每个小...

yysue
07/05
0
0
Comparator与Comparable的应用

当需要排序的集合或数组不是单纯的数字型时,通常可以使用Comparator或Comparable,以简单的方式实现对象排序或自定义排序。 阅读过程中有任何问题,请联系egg: 邮箱:xtfggef@gmail.com 微...

mrliuze
2015/08/04
0
0
Java高级程序员面试大纲——错过了金三,你还要错过银四吗

跳槽时时刻刻都在发生,但是我建议大家跳槽之前,先想清楚为什么要跳槽。切不可跟风,看到同事一个个都走了,自己也盲目的开始面试起来(期间也没有准备充分),到底是因为技术原因(影响自己...

Java高级架构
04/27
0
0
java8之lambda表达式(函数式接口)

在Java中有许多已有的接口都需要封装代码块,例如:Runnable或者Comparator。lambda表达式与这些接口是向后兼容的。对于只包含一个抽象方法的接口,你可以通过lambda表达式来创建该接口的对象...

柳哥
2015/05/21
0
0
Java程序员面试大纲—错过了金三银四,你还要错过2018吗?

跳槽时时刻刻都在发生,但是我建议大家跳槽之前,先想清楚为什么要跳槽。切不可跟风,看到同事一个个都走了,自己也盲目的开始面试起来(期间也没有准备充分),到底是因为技术原因(影响自己...

java高级架构牛人
04/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mac OS X下Maven的安装与配置

Mac OS X 安装Maven: 下载 Maven, 并解压到某个目录。例如/Users/robbie/apache-maven-3.3.3 打开Terminal,输入以下命令,设置Maven classpath $ vi ~/.bash_profile 添加下列两行代码,之后...

TonyStarkSir
今天
3
0
关于编程,你的练习是不是有效的?

最近由于工作及Solution项目的影响,我在重新学习DDD和领域建模的一些知识。然后,我突然就想到了这个问题,以及我是怎么做的? 对于我来说,提升技能的项目会有四种: 纯兴趣驱动的项目。即...

问题终结者
今天
4
0
打开eclipse出现an error has occurred see the log file

解决方法: 1,打开eclipse安装目录下的eclipse.ini文件; 2,打开的文本文件最后添加一行 --add-modules=ALL-SYSTEM 3,保存重新打开Eclipse。...

任梁荣
昨天
4
0
搞定Northwind示例数据库,无论哪个版本的SQLServer都受用

Northwind数据库 从这里可以找到突破口: http://social.msdn.microsoft.com/Forums/zh-CN/Vsexpressvb/thread/8490a1c6-9018-40c9-aafb-df9f79d29cde 下面是MSDN: http://msdn2.microsoft......

QQZZFT
昨天
1
0
mysql主从同步,安装配置操作

准备 两台mysql服务,我这里准备了如下: 主库:192.168.176.128 从库:192.168.176.131 如何在Linux上安装mysql服务,请看https://blog.csdn.net/qq_18860653/article/details/80250499 操作...

小致dad
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部