浅析：java的"排序"函数使用了哪些"算法"
我是浩说
前几天在做数据排序的时候
手滑点进了Arrays.sort()方法的源码里
本着"既来之，则安之"的心态
索性哥们儿就看了一番
没想到有了新收获
原来
Arrays.sort()方法会根据不同的情况使用不同的"排序算法"
接下来就给兄弟们详细汇报一下具体情况
关于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()所有的重载方法
我们可以从"被排序对象的数据类型"角度来分别推敲具体使用的排序算法
1
基本数据类型
拿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(默认)：ComparableTimSort
public 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()根据被排序数据的数据类型分为两种排序逻辑：
基本数据类型
具体排序算法取决于元素个数
< 47 插入排序
> 47 且·< 286 快排
> 286 归并排序
01.Collections.sort(List<T> list)legacyMergeSort 归并排序TimSort （默认）：归并 + 插入02.带比较器 Collections.sort(List<T> list,Comparator<? super T> c)legacyMergeSort 归并排序ComparableTimSort（默认） ：归并 + 插入
腾讯云开发者
