栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

集合中排序 Collections.sort方法源码分析

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

集合中排序 Collections.sort方法源码分析

集合中排序 Collections.sort方法源码分析

集合排序有Collections.sort(List list) 和 Collections.sort(List list, Comparator c)两种排序方法。

  1. Collections.sort(List list)
public static > void sort(List list) {
    list.sort(null);
}
  1. Collections.sort(List list, Comparator c)
public static  void sort(List list, Comparator c) {
    list.sort(c);
}

其实我们可以看到这两种方法都是调用的list.sort()方法,只是传参不同;第一种没有Comparator比较器,所以参数为null;第二种有Comparator以将比较器传入。

list.sort(Comparator c)方法:

这个方法是将集合转换为Object数组a,然后调用Arrays.sort(T[] a, Comparator c)。

default void sort(Comparator c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    //进行迭代遍历,将排序好的a数组设置到集合中
    ListIterator i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

Arrays.sort(T[] a, Comparator c)方法:

public static  void sort(T[] a, Comparator c) {
    //当传入的比较器为空时,执行 java自带的sort(a);
    if (c == null) {
        sort(a);
    } else {
        //userRequested用户请求使用。这里是老版本jdk1.5的,将来会被删除,可以忽略
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            //使用指定的比较器
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

提一下 **legacyMergeSort(a, c);**将在将来的版本中删除。

//将在将来的版本中删除。
private static  void legacyMergeSort(T[] a, Comparator c) {
        T[] aux = a.clone();
        if (c==null)
            mergeSort(aux, a, 0, a.length, 0);
        else
            mergeSort(aux, a, 0, a.length, 0, c);
    }

进入sort(Object[] a)方法

public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        //进入方法
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

再进入ComparableTimSort.sort方法

  private static final int MIN_MERGE = 32;

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;
    //数组长度nRemaining小于等于1,无需排序
    if (nRemaining < 2)
        return;  
	
	// If array is small, do a "mini-TimSort" with no merges
    // 数组长度小于32,使用binarySort 二分法排序
    if (nRemaining < MIN_MERGE) {
        int initRunLen = countRunAndMakeAscending(a, lo, hi);
        binarySort(a, lo, hi, lo + initRunLen);
        return;
    }

    
    ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
    //选取分块大小
    int minRun = minRunLength(nRemaining);
    //TimSort:先扫描找到已经排好的序列,然后再用刚才的mini-TimSort,然后合并
    do {
        // 确定下一次运行
        int runLen = countRunAndMakeAscending(a, lo, hi);

        // 如果运行长度短,则扩展到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;
}

上面就是没有传比较器而走默认的sort()方法的方式

当代码执行指定比较器时进入TimSort.sort方法时,其实可以发现ComparableTimSort.sort和TimSort.sort是一样的,官方说ComparableTimSort是TimSort副本。因为传入参数不同,最终执行了我们指定的比较器结果

Timsort是结合了合并排序(merge sort)和插入排序(insertion sort)而得出的排序算法,它在现实中有很好的效率。该算法找到数据中已经排好序的块-分区,每一个分区叫一个run,然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序,现在Java SE7和Android也采用Timsort算法对数组排序。

总结

1.使用Collections.sort(List list)或者Collections.sort(List list, Comparator c)方法,他们执行的都是同一个sort(Comparator c)。

2.进入sort将集合转为数组a,调用Arrays.sort方法进行排序。然后排序好的数组,复制到集合中去。

3.进入Arrays.sort(a, (Comparator) c)

  • 无比较器:

    • Arrays.sort:经过判断无比较器,执行默认的sort(a);
    • 进入sort(a):进行判断,执行ComparableTimSort.sort()方法,这个方法和TimSort.sort()是一样的,只是有传无比较器的区别,默认的就是按照小到大排序或者实现的Comparator接口重写方法排序;
  • 有比较器:

    • Arrays.sort:经过判断有比较器,执行TimSort.sort()方法,按照我们指定的排序进行排序。

新手学员,如有错误请指正

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/972321.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号