先来看看List中的sort是怎么写的:

@SuppressWarnings({"unchecked","rawtypes"})defaultvoidsort(Comparator<!--?superE-->c){Object[]a=this.toArray();Arrays.sort(a,(Comparator)c);ListIterator<e>i=this.listIterator();for(Objecte:a){i.next();i.set((E)e);}}

首先,你需要传入一个比较器作为参数,这个好理解,毕竟你肯定要定一个比较标准。然后就是将list转换成一个数组,再对这个数组进行排序,排序完之后,再利用iterator重新改变list。

接着,我们再来看看Arrays.sort:

publicstatic<t>voidsort(T[]a,Comparator<!--?superT-->c){if(c==null){sort(a);}else{if(LegacyMergeSort.userRequested)legacyMergeSort(a,c);elseTimSort.sort(a,0,a.length,c,null,0,0);}}publicstaticvoidsort(Object[]a){if(LegacyMergeSort.userRequested)legacyMergeSort(a);elseComparableTimSort.sort(a,0,a.length,null,0,0);}staticfinalclassLegacyMergeSort{privatestaticfinalbooleanuserRequested=java.security.AccessController.doPrivileged(newsun.security.action.GetBooleanAction("java.util.Arrays.useLegacyMergeSort")).booleanValue();}

这样可以看出,其实排序的核心就是TimSort,LegacyMergeSort大致意思是表明如果版本很旧的话,就用这个,新版本是不会采用这种排序方式的。

我们再来看看TimSort的实现:

privatestaticfinalintMIN_MERGE=32;static<t>voidsort(T[]a,intlo,inthi,Comparator<!--?superT-->c,T[]work,intworkBase,intworkLen){assertc!=null&amp;&amp;a!=null&amp;&amp;lo&gt;=0&amp;&amp;lo&lt;=hi&amp;&amp;hi&lt;=a.length;intnRemaining=hi-lo;if(nRemaining&lt;2)return;//Arraysofsize0and1arealwayssorted//Ifarrayissmall,doa"mini-TimSort"withnomergesif(nRemaining&lt;MIN_MERGE){//获得最长的递增序列intinitRunLen=countRunAndMakeAscending(a,lo,hi,c);binarySort(a,lo,hi,lo+initRunLen,c);return;}/***Marchoverthearrayonce,lefttoright,findingnaturalruns,*extendingshortnaturalrunstominRunelements,andmergingruns*tomaintainstackinvariant.*/TimSort<t>ts=newTimSort&lt;&gt;(a,c,work,workBase,workLen);intminRun=minRunLength(nRemaining);do{//IdentifynextrunintrunLen=countRunAndMakeAscending(a,lo,hi,c);//Ifrunisshort,extendtomin(minRun,nRemaining)if(runLen&lt;minRun){intforce=nRemaining&lt;=minRun?nRemaining:minRun;binarySort(a,lo,lo+force,lo+runLen,c);runLen=force;}//Pushrunontopending-runstack,andmaybemergets.pushRun(lo,runLen);ts.mergeCollapse();//Advancetofindnextrunlo+=runLen;nRemaining-=runLen;}while(nRemaining!=0);//Mergeallremainingrunstocompletesortassertlo==hi;ts.mergeForceCollapse();assertts.stackSize==1;}

如果小于2个,代表不再不需要排序;如果小于32个,则采用优化的二分排序。怎么优化的呢?首先获得最长的递增序列:

privatestatic<t>intcountRunAndMakeAscending(T[]a,intlo,inthi,Comparator<!--?superT-->c){assertlo&lt;hi;intrunHi=lo+1;if(runHi==hi)return1;//Findendofrun,andreverserangeifdescendingif(c.compare(a[runHi++],a[lo])&lt;0){//Descending//一开始是递减序列,就找出最长递减序列的最后一个下标while(runHi&lt;hi&amp;&amp;c.compare(a[runHi],a[runHi-1])&lt;0)runHi++;//逆转前面的递减序列reverseRange(a,lo,runHi);}else{//Ascendingwhile(runHi&lt;hi&amp;&amp;c.compare(a[runHi],a[runHi-1])&gt;=0)runHi++;}returnrunHi-lo;}

接着进行二分排序:

privatestatic<t>voidbinarySort(T[]a,intlo,inthi,intstart,Comparator<!--?superT-->c){assertlo&lt;=start&amp;&amp;start&lt;=hi;if(start==lo)start++;for(;start&lt;hi;start++){Tpivot=a[start];//Setleft(andright)totheindexwherea[start](pivot)belongsintleft=lo;intright=start;assertleft&lt;=right;/**Invariants:*pivot&gt;=allin[lo,left).*pivot&lt;allin[right,start).*///start位置是递增序列后的第一个数的位置//从前面的递增序列中找出start位置的数应该处于的位置while(left&lt;right){//&gt;&gt;&gt;无符号右移intmid=(left+right)&gt;&gt;&gt;1;if(c.compare(pivot,a[mid])&lt;0)right=mid;elseleft=mid+1;}assertleft==right;/**Theinvariantsstillhold:pivot&gt;=allin[lo,left)and*pivot&lt;allin[left,start),sopivotbelongsatleft.Note*thatifthereareelementsequaltopivot,leftpointstothe*firstslotafterthem--that'swhythissortisstable.*Slideelementsovertomakeroomforpivot.*/intn=start-left;//Thenumberofelementstomove//Switchisjustanoptimizationforarraycopyindefaultcase//比pivot大的数往后移动一位switch(n){case2:a[left+2]=a[left+1];case1:a[left+1]=a[left];break;default:System.arraycopy(a,left,a,left+1,n);}a[left]=pivot;}}

好了,待排序数量小于32个的讲完了,现在来说说大于等于32个情况。首先,获得一个叫minRun的东西,这是个啥含义呢:

intminRun=minRunLength(nRemaining);privatestaticintminRunLength(intn){assertn>=0;intr=0;//Becomes1ifany1bitsareshiftedoffwhile(n>=MIN_MERGE){//这里我没搞懂的是为什么不直接将(n&1)赋值给r,而要做一次逻辑或。r|=(n&1);n>>=1;}returnn+r;}

各种位运算符,MIN_MERGE默认为32,如果n小于此值,那么返回n本身。否则会将n不断地右移,直到小于MIN_MERGE,同时记录一个r值,r代表最后一次移位n时,n最低位是0还是1。 其实看注释比较容易理解:

Returnstheminimumacceptablerunlengthforanarrayofthespecifiedlength.NaturalrunsshorterthanthiswillbeextendedwithbinarySort.Roughlyspeaking,thecomputationis:Ifn<MIN_MERGE,returnn(it'stoosmalltobotherwithfancystuff).Elseifnisanexactpowerof2,returnMIN_MERGE/2.Elsereturnanintk,MIN_MERGE/2<=k<=MIN_MERGE,suchthatn/kiscloseto,butstrictlylessthan,anexactpowerof2.Fortherationale,seelistsort.txt.

返回结果其实就是用于接下来的合并排序中。

接下来就是一个while循环

do{//Identifynextrun//获得一个最长递增序列intrunLen=countRunAndMakeAscending(a,lo,hi,c);//Ifrunisshort,extendtomin(minRun,nRemaining)//如果最长递增序列if(runLen<minRun){intforce=nRemaining<=minRun?nRemaining:minRun;binarySort(a,lo,lo+force,lo+runLen,c);runLen=force;}//Pushrunontopending-runstack,andmaybemerge//lo——runLen为将要被归并的范围ts.pushRun(lo,runLen);//归并ts.mergeCollapse();//Advancetofindnextrunlo+=runLen;nRemaining-=runLen;}while(nRemaining!=0);

这样,假设你的每次归并排序的两个序列为r1和r2,r1肯定是有序的,r2也已经被排成递增序列了,因此这样的归并排序就比较特殊了。

为什么要用归并排序呢,因为归并排序的时间复杂度永远为O(nlogn),空间复杂度为O(n),以空间换取时间。

感谢各位的阅读,以上就是“Java List中的sort方法怎么用”的内容了,经过本文的学习后,相信大家对Java List中的sort方法怎么用这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是本站,小编将为大家推送更多相关知识点的文章,欢迎关注!