最近有粉丝叫我帮他做一下一道最简单的排序基础题。。。。
额。。。。。。这同学应该好好听课啦 哈哈
int[]a={25,24,12,76,101,96,28};Arrays.sort(a);//排序System.out.println("排序后数组如下");for(inti=0;i<a.length;i++){System.out.print(a[i]+",");}既然写到这里了就看下底层实现吧
断点跟踪调用的是DualPivotQuicksort.java类的java双基准快速排序方法sort实现
跟踪进去就是具体排序方法的实现、其中具体方法：参数 int[] a是需被排序的int数组, left和right是该数组中需要被排序的部分的左右界限. 而后面的work, workBase和workLen三个参数其实并不会参与双基准快速排序, 而是当系统认为本数组更适合使用归并排序(merge sort)的时候, 供归并排序使用。具体代码算法源码如下。
staticvoidsort(int[]a,intleft,intright,int[]work,intworkBase,intworkLen){//UseQuicksortonsmallarraysif(right-left<QUICKSORT_THRESHOLD){sort(a,left,right,true);return;}/**Indexrun[i]isthestartofi-thrun*(ascendingordescendingsequence).*/int[]run=newint[MAX_RUN_COUNT+1];intcount=0;run[0]=left;//Checkifthearrayisnearlysortedfor(intk=left;k<right;run[count]=k){if(a[k]<a[k+1]){//ascendingwhile(++k<=right&&a[k-1]<=a[k]);}elseif(a[k]>a[k+1]){//descendingwhile(++k<=right&&a[k-1]>=a[k]);for(intlo=run[count]-1,hi=k;++lo<--hi;){intt=a[lo];a[lo]=a[hi];a[hi]=t;}}else{//equalfor(intm=MAX_RUN_LENGTH;++k<=right&&a[k-1]==a[k];){if(--m==0){sort(a,left,right,true);return;}}}/**Thearrayisnothighlystructured,*useQuicksortinsteadofmergesort.*/if(++count==MAX_RUN_COUNT){sort(a,left,right,true);return;}}//Checkspecialcases//Implementationnote:variable"right"isincreasedby1.if(run[count]==right++){//Thelastruncontainsoneelementrun[++count]=right;}elseif(count==1){//Thearrayisalreadysortedreturn;}//Determinealternationbaseformergebyteodd=0;for(intn=1;(n<<=1)<count;odd^=1);//Useorcreatetemporaryarraybformergingint[]b;//temparray;alternateswithaintao,bo;//arrayoffsetsfrom'left'intblen=right-left;//spaceneededforbif(work==null||workLen<blen||workBase+blen>work.length){work=newint[blen];workBase=0;}if(odd==0){System.arraycopy(a,left,work,workBase,blen);b=a;bo=0;a=work;ao=workBase-left;}else{b=work;ao=0;bo=workBase-left;}//Mergingfor(intlast;count>1;count=last){for(intk=(last=0)+2;k<=count;k+=2){inthi=run[k],mi=run[k-1];for(inti=run[k-2],p=i,q=mi;i<hi;++i){if(q>=hi||p<mi&&a[p+ao]<=a[q+ao]){b[i+bo]=a[p+++ao];}else{b[i+bo]=a[q+++ao];}}run[++last]=hi;}if((count&1)!=0){for(inti=right,lo=run[count-1];--i>=lo;b[i+bo]=a[i+ao]);run[++last]=right;}int[]t=a;a=b;b=t;into=ao;ao=bo;bo=o;}}虽然看似简单的一行代码其实底层的实现也是很复杂的、对算法感兴趣的同学可以仔细看看底层实现。