关于Arrays.sort()

先给不熟悉的兄弟们科普一下

jdk 提供的排序工具类主要有两个：

  java .util.Arrays
java.util.Collections

大家可能更常用

Collections.sort() + 重写compare方法

的方式来基于某个属性排序

不过翻看Collections.sort()源码你会发现，

最终也是调用Arrays.sort()方法进行排序：

 default  void  sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
     ListIterator <E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

所以Arrays.sort()才是排序的最终处理入口，了解一下还是很有必要的！

常用的排序算法

我们简单罗列一下目前常用的排序算法英文说明，以便后面阅读源码做参考：

冒泡排序 Bubble Sort
插入排序 Insertion Sort
归并排序 Merge Sort
快排 Quick sort

源码浅析

纵览Arrays.sort()所有的重载方法

我们可以从” 被排序对象的数据类型 “角度来分别推敲具体使用的排序算法

基本数据类型

拿int类型举例

(其它基本数据类型逻辑相同)

01 -> Arrays.sort()

方法里只有一行代码，看英文我们对照刚才罗列的算法不难猜到，

这大致是一个快排算法，我们点进去看一下：

 public  static  void sort(int[] a) {
    //快排  Quick sort
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

02 -> DualFivotQuicksort. sort ()

该方法存在两个分支，且由数组的长度决定走向

根据两处注释来看

我们对照刚才罗列的算法可以暂时得出一个结论：

数组长度大于286，使用归并排序

小于286则使用快排

 static void sort(int[] a, int left, int right,
                 int[] work, int workBase, int workLen) {
    // Use Quicksort on small arrays
    if (right - left < QUICKSORT_THRESHOLD) {
        sort(a, left, right, true);
        return;
    }
    ...
    // Merging
    ...
}
//QUICKSORT_THRESHOLD
 private  static final int QUICKSORT_THRESHOLD = 286;

但事实真的如此吗？

我们进入快排的sort方法

03 -> sort(a, left, right, true)

该方法里又存在着两个分支

 private static void sort(int[] a, int left, int right,  boolean  leftmost) {
    int length = right - left + 1;
    // Use insertion sort on tiny arrays
    if (length < INSERTION_SORT_THRESHOLD) {
        ...
    }
    ...
}
//INSERTION_SORT_THRESHOLD
private static final int INSERTION_SORT_THRESHOLD = 47;

根据注释说明，再对照我们上面罗列的算法英文说明

我们修正一下刚才的结论：

当数组长度小于47，使用插入排序

大于47且小于286才真正使用快排

所以其实快排方法并不只是快排

结论总结

对于基本数据类型排序

具体排序算法取决于元素个数

< 47 插入排序

> 47 且 < 286 快排

> 286 归并排序

泛型

这种应该就是我们常用的，

也就是通过Collections.sort()调用

让我们逐步分析一下：

01 -> Collections.sort()

 两个重载方法：//入参List<T> list

public static <T extends Comparable<? super T>> void sort(List<T> list) {

    list.sort(null);

}




/**

 * 入参

 * List<T> list

 * 带 比较器  Comparator<? super T> c

 */

public static <T> void sort(List<T> list, Comparator<? super T> c) {

    list.sort(c);

}

02 -> List.sort()

先将对象转为数组

然后第三行，调用Arrays.sort()

 default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

03 -> Arrays.sort(a, (Comparator) c)

针对泛型的排序方法有两个大分支，分别对应Collections.sort()的两个重载方法：

 public static <T> void sort(T[] a, Comparator<? super T> c) {
    //调用默认Collections.sort(List<T> list)方法走if分支
    if (c == null) {
        sort(a);
    } 
    //调用带选择器Collections.sort(List<T> list,Comparator<? super T> c)方法走else分支
    else {
        //LegacyMergeSort.userRequested默认为false
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            //默认走这里
             TimSort .sort(a, 0, a.length, c, null, 0, 0);
    }
}

通过我在注释里的说明，

我们同样可以暂时得出一个结论：

当我们调用带选择器的Collections.sort()方法，

可能会执行两种算法归并排序、TimSort，

但由于LegacyMergeSort.userRequested

默认为false，

所以最终会执行TimSort排序算法。

福利 ” 上菜 ”

不知不觉又到了经典”上菜”环节

兄弟们准备好了嘛！

今日菜系：

800道大厂面试题

1000道基础面试题

公众号”浩说编程”发送数字 “7”

找面试题再也不用东拼西凑爽到飞起！

关于这个TimSort，我简单看了一下源码,

知道兄弟们可能不想看大篇幅的代码，所以我这里只列出关键部分：

 static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,

                     T[] work, int workBase, int workLen) {

    .....

    // If array is small, do a "mini-TimSort" with no merges

     if  (nRemaining < MIN_MERGE) {

        int initRunLen = countRunAndMakeAscending(a, lo, hi, c);

        binarySort(a, lo, hi, lo + initRunLen, c);

        return;

    }

    .....

    // Merge all remaining runs to complete sort

    assert lo == hi;

    ts.mergeForceCollapse();

    assert ts.stackSize == 1;

}

依然有两个分支，通过注释可以大体看出：
1、对于小量级数组，将执行叫做”mini-TimSort”的算法，我进入这个binarySort()方法发现其实是插入排序。
2、否则就是归并排序
所以兄弟们可以这样理解：

TimSort是基于归并排序 + 插入排序的优化算法！

以上是基于else分支得出的结论，接下来我们继续探讨if分支的逻辑：

c == null -> sort(a)

 这里逻辑也很清晰，两种情况：
true: 归并排序
false(默认)：ComparableTimSortpublic static void sort(Object[] a) {

    if (LegacyMergeSort.userRequested)

        legacyMergeSort(a);

    else

        //默认走这里

        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);

}

这里的ComparableTimSort 和 Timsort

唯一的区别就是前者不需要自定义比较器。

泛型排序的分支比较多，我们再重新梳理一下逻辑：

01.Collections.sort(List<T> list)

legacyMergeSort 归并排序

TimSort （默认）

02.带比较器Collections.sort(List<T> list,Comparator<? super T> c)

legacyMergeSort 归并排序

ComparableTimSort（默认）

兄弟们发现没有

归并排序这个分支似乎没什么用

默认都是在使用TimSort。

而事实也确实如此，在legacyMergeSort方法里已经有注释，翻译一下大概就是”可能将在之后的版本移除”，所以这个TimSort 应该是优于归并排序的更优解！

关于Arrays.sort()应用的排序算法大家已经有了大致的了解

我再给兄弟们做一个整体总结，记得 点赞分享 ！

Arrays.sort()根据被排序数据的数据类型分为两种排序逻辑：

01 | 基本数据类型

具体排序算法取决于元素个数

< 47 插入排序

> 47 且·< 286 快排

> 286 归并排序

02 | 泛型

01.Collections.sort(List<T> list)

legacyMergeSort 归并排序

TimSort （默认）：归并 + 插入

02.带比较器 Collections.sort(List<T> list,Comparator<? super T> c)

legacyMergeSort 归并排序

ComparableTimSort（默认）：归并 + 插入

智云一二三科技

浅析：java的"排序"函数使用了哪些"算法"

关于Arrays.sort()

常用的排序算法

源码浅析

结论总结

福利 ” 上菜 ”

关于作者: 智云科技

关于Arrays.sort()

常用的排序算法

源码浅析

结论总结

福利 ” 上菜 ”

给这篇文章的作者打赏

关于作者: 智云科技

相关文章

Map和List的几种遍历方式

全网大佬都在用的Java+Python这两套视频学习教程，学习很重要

JavaWeb快速进阶全套教程(程序员必备2020版)：视频+笔记+源码

热门文章

1分享新浪图床上传接口源码

2PHP简单实现路由Route功能

3Tideways、xhprof 和 xhgui 打造 PHP 非侵入式监控平台

4centos系统如何查看是否安装了mysql

5curl 工具简述