Java Arrays.sort和Collections.sort排序实现原理解析
1、使用
排序
2、原理
事实上Collections.sort方法底层就是调用的array.sort方法，而且不论是Collections.sort或者是Arrays.sort方法，
跟踪下源代码吧，首先我们写个demo
publicstaticvoidmain(String[]args){
Liststrings=Arrays.asList("6","1","3","1","2");
Collections.sort(strings);//sort方法在这里
for(Stringstring:strings){
System.out.println(string);
}
}
简单得不能再简单的方法了，让我们一步步跟踪
OK，往下面看，发现collections.sort方法调用的list.sort
然后跟踪一下，list里面有个sort方法，但是list是一个接口，肯定是调用子类里面的实现，这里我们demo使用的是一个Arrays.asList方法，所以事实上我们的子类就是arraylist了。OK，看arraylist里面sort实现，选择第一个，为什么不选择第二个呢？（可以看二楼评论，解答得很正确，简单说就是用Arrays.sort创建的ArrayList对象）
OK，发现里面调用的Arrays.sort(a,c);a是list,c是一个比较器，我们来看一下这个方法
我们没有写比较器，所以用的第二项，LegacyMergeSort.userRequested这个bool值是什么呢？
跟踪这个值，我们发现有这样的一段定义：
>Oldmergesortimplementationcanbeselected(for
>compatibilitywithbrokencomparators)usingasystemproperty.
>Cannotbeastaticbooleanintheenclosingclassdueto
>circulardependencies.Toberemovedinafuturerelease.反正是一种老的归并排序，不用管了现在默认是关的
OK，我们走的是sort(a)这个方法，接着进入这个
staticvoidsort(Object[]a,intlo,inthi,Object[]work,intworkBase,intworkLen){
asserta!=null&&lo>=0&&lo<=hi&&hi<=a.length;
intnRemaining=hi-lo;
if(nRemaining<2)
return;//array的大小为0或者1就不用排了
//当数组大小小于MIN_MERGE(32)的时候，就用一个"mini-TimSort"的方法排序，jdk1.7新加
if(nRemaining
回到5，我们可以看到当我们写了比较器的时候就调用了TimSort.sort方法，源码如下
staticvoidsort(T[]a,intlo,inthi,Comparatorc,
T[]work,intworkBase,intworkLen){
assertc!=null&&a!=null&&lo>=0&&lo<=hi&&hi<=a.length;
intnRemaining=hi-lo;
if(nRemaining<2)
return;//Arraysofsize0and1arealwayssorted
//Ifarrayissmall,doa"mini-TimSort"withnomerges
if(nRemainingts=newTimSort<>(a,c,work,workBase,workLen);
intminRun=minRunLength(nRemaining);
do{
//Identifynextrun
intrunLen=countRunAndMakeAscending(a,lo,hi,c);
//Ifrunisshort,extendtomin(minRun,nRemaining)
if(runLen
和上面的sort方法是一样的，其实也就是TimSort的源代码
3、总结
不论是Collections.sort方法或者是Arrays.sort方法，底层实现都是TimSort实现的，这是jdk1.7新增的，以前是归并排序。TimSort算法就是找到已经排好序数据的子序列，然后对剩余部分排序，然后合并起来
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。