让面试官满意的排序算法（图文解析）

这种排序算法能够让面试官面露微笑

这种排序算法集各排序算法之大成

这种排序算法逻辑性十足

这种排序算法能够展示自己对Java底层的了解

这种排序算法出自Vladimir Yaroslavskiy、Jon Bentley和Josh Bloch三位大牛之手，它就是JDK的排序算法——java.util.DualPivotQuicksort（双支点快排）

想看以往学习内容的朋友
可以看我的GitHub:https://github.com/Meng997998/AndroidJX

觉得文章枯燥的朋友，可以看视频学习,免费领取vx【xx13414521】
DualPivotQuicksort

先看一副逻辑图（如有错误请大牛在评论区指正）

插排指的是改进版插排——哨兵插排

快排指的是改进版快排——双支点快排

DualPivotQuickSort没有Object数组排序的逻辑，此逻辑在Arrays中，好像是归并+Tim排序

图像应该很清楚：对于不同的数据类型，Java有不同的排序策略：

byte、short、char他们的取值范围有限，使用计数排序占用的空间也不过256/65536个单位，只要排序的数量不是特别少（有一个计数排序阈值，低于这个阈值的话就没有不要用空间换时间了），都应使用计数排序

int、long、float、double他们的取值范围非常的大，不适合使用计数排序

float和double他们又有特殊情况：

NAN（not a number），NAN不等于任何数字，甚至不等于自己+0.0，-0.0，float和double无法精确表示十进制小数，我们所看到的十进制小数其实都是取得近似值，因而会有+0.0（接近0的正浮点数）和-0.0（接近0的负浮点数)，在排序流程中统一按0来处理，因而最后要调整一下-0.0和+0.0的位置关系

Object

计数排序

计数排序是以空间换时间的排序算法，它时间复杂度O(n)，空间复杂度O(m)（m为排序数值可能取值的数量），只有在范围较小的时候才应该考虑计数排序

（源码以short为例）

int[]count=newint[NUM_SHORT_VALUES];//1<<16=65536，即short的可取值数量//计数，left和right为数组要排序的范围的左界和右界//注意，直接把for(inti=left-1;++i<=right;count[a[i]-Short.MIN_VALUE]++);//排序for(inti=NUM_SHORT_VALUES,k=right+1;k>left;){while(count[--i]==0);shortvalue=(short)(i+Short.MIN_VALUE);ints=count[i];do{a[--k]=value;}while(--s>0);}哨兵插排

当数组元素较少时，时间O(n2)和O(logn)其实相差无几，而插排的空间占用率要少于快排和归并排序，因而当数组元素较少时（<插排阈值），优先使用插排

哨兵插排是对插排的优化，原插排每次取一个值进行遍历插入，而哨兵插排则取两个，较大的一个（小端在前的排序）作为哨兵，当哨兵遍历到自己的位置时，另一个值可以直接从哨兵当前位置开始遍历，而不用再重头遍历

只画了静态图，如果有好的绘制Gif的工具请在评论区告诉我哦

我们来看一下源码：

if(leftmost){//传统插排（无哨兵Sentinel）//遍历//循环向左比较（<左侧元素——换位）-直到大于左侧元素for(inti=left,j=i;i<right;j=++i){intai=a[i+1];while(ai<a[j]){a[j+1]=a[j];if(j--==left){break;}}a[j+1]=ai;}//哨兵插排}else{//如果一开始就是排好序的——直接返回do{if(left>=right){return;}}while(a[++left]>=a[left-1]);//以两个为单位遍历，大的元素充当哨兵，以减少小的元素循环向左比较的范围for(intk=left;++left<=right;k=++left){inta1=a[k],a2=a[left];if(a1<a2){a2=a1;a1=a[left];}while(a1<a[--k]){a[k+2]=a[k];}a[++k+1]=a1;while(a2<a[--k]){a[k+1]=a[k];}a[k+1]=a2;}//确保最后一个元素被排序intlast=a[right];while(last<a[--right]){a[right+1]=a[right];}a[right+1]=last;}return;双支点快排

重头戏：双支点快排！

快排虽然稳定性不如归并排序，但是它不用复制来复制去，省去了一段数组的空间，在数组元素较少的情况下稳定性影响也会下降（>插排阈值 ，<快排阈值），优先使用快排

双支点快排在原有的快排基础上，多加一个支点，左右共进，效率提升

看图：

第一步，取支点

注意：如果5个节点有相等的任两个节点，说明数据不够均匀，那就要使用单节点快排

快排

源码（int为例，这么长估计也没人看）

//Inexpensiveapproximationoflength/7//快排阈值是286其7分之一小于等于1/8+1/64+1intseventh=(length>>3)+(length>>6)+1;//获取分成7份的五个中间点inte3=(left+right)>>>1;//Themidpointinte2=e3-seventh;inte1=e2-seventh;inte4=e3+seventh;inte5=e4+seventh;//保证中间点的元素从小到大排序if(a[e2]<a[e1]){intt=a[e2];a[e2]=a[e1];a[e1]=t;}if(a[e3]<a[e2]){intt=a[e3];a[e3]=a[e2];a[e2]=t;if(t<a[e1]){a[e2]=a[e1];a[e1]=t;}}if(a[e4]<a[e3]){intt=a[e4];a[e4]=a[e3];a[e3]=t;if(t<a[e2]){a[e3]=a[e2];a[e2]=t;if(t<a[e1]){a[e2]=a[e1];a[e1]=t;}}}if(a[e5]<a[e4]){intt=a[e5];a[e5]=a[e4];a[e4]=t;if(t<a[e3]){a[e4]=a[e3];a[e3]=t;if(t<a[e2]){a[e3]=a[e2];a[e2]=t;if(t<a[e1]){a[e2]=a[e1];a[e1]=t;}}}}//Pointersintless=left;//Theindexofthefirstelementofcenterpartintgreat=right;//Theindexbeforethefirstelementofrightpart//点彼此不相等——分三段快排，否则分两段if(a[e1]!=a[e2]&&a[e2]!=a[e3]&&a[e3]!=a[e4]&&a[e4]!=a[e5]){/**Usethesecondandfourthofthefivesortedelementsaspivots.*Thesevaluesareinexpensiveapproximationsofthefirstand*secondtercilesofthearray.Notethatpivot1<=pivot2.*/intpivot1=a[e2];intpivot2=a[e4];/**Thefirstandthelastelementstobesortedaremovedtothe*locationsformerlyoccupiedbythepivots.Whenpartitioning*iscomplete,thepivotsareswappedbackintotheirfinal*positions,andexcludedfromsubsequentsorting.*/a[e2]=a[left];a[e4]=a[right];while(a[++less]<pivot1);while(a[--great]>pivot2);/**Partitioning:**leftpartcenterpartrightpart*+--------------------------------------------------------------+*|<pivot1|pivot1<=&&<=pivot2|?|>pivot2|*+--------------------------------------------------------------+*^^^*|||*lesskgreat*/outer:for(intk=less-1;++k<=great;){intak=a[k];if(ak<pivot1){//Movea[k]toleftparta[k]=a[less];/**Hereandbelowweuse"a[i]=b;i++;"instead*of"a[i++]=b;"duetoperformanceissue.*/a[less]=ak;++less;}elseif(ak>pivot2){//Movea[k]torightpartwhile(a[great]>pivot2){if(great--==k){breakouter;}}if(a[great]<pivot1){//a[great]<=pivot2a[k]=a[less];a[less]=a[great];++less;}else{//pivot1<=a[great]<=pivot2a[k]=a[great];}/**Hereandbelowweuse"a[i]=b;i--;"instead*of"a[i--]=b;"duetoperformanceissue.*/a[great]=ak;--great;}}//Swappivotsintotheirfinalpositionsa[left]=a[less-1];a[less-1]=pivot1;a[right]=a[great+1];a[great+1]=pivot2;//Sortleftandrightpartsrecursively,excludingknownpivotssort(a,left,less-2,leftmost);sort(a,great+2,right,false);/**Ifcenterpartistoolarge(comprises>4/7ofthearray),*swapinternalpivotvaluestoends.*/if(less<e1&&e5<great){/**Skipelements,whichareequaltopivotvalues.*/while(a[less]==pivot1){++less;}while(a[great]==pivot2){--great;}/**Partitioning:**leftpartcenterpartrightpart*+----------------------------------------------------------+*|==pivot1|pivot1<&&<pivot2|?|==pivot2|*+----------------------------------------------------------+*^^^*|||*lesskgreat**Invariants:**allin(*,less)==pivot1*pivot1<allin[less,k)<pivot2*allin(great,*)==pivot2**Pointerkisthefirstindexof?-part.*/outer:for(intk=less-1;++k<=great;){intak=a[k];if(ak==pivot1){//Movea[k]toleftparta[k]=a[less];a[less]=ak;++less;}elseif(ak==pivot2){//Movea[k]torightpartwhile(a[great]==pivot2){if(great--==k){breakouter;}}if(a[great]==pivot1){//a[great]<pivot2a[k]=a[less];/**Eventhougha[great]equalstopivot1,the*assignmenta[less]=pivot1maybeincorrect,*ifa[great]andpivot1arefloating-pointzeros*ofdifferentsigns.Thereforeinfloatand*doublesortingmethodswehavetousemore*accurateassignmenta[less]=a[great].*/a[less]=pivot1;++less;}else{//pivot1<a[great]<pivot2a[k]=a[great];}a[great]=ak;--great;}}}//Sortcenterpartrecursivelysort(a,less,great,false);}else{//Partitioningwithonepivot/**Usethethirdofthefivesortedelementsaspivot.*Thisvalueisinexpensiveapproximationofthemedian.*/intpivot=a[e3];/**Partitioningdegeneratestothetraditional3-way*(or"DutchNationalFlag")schema:**leftpartcenterpartrightpart*+-------------------------------------------------+*|<pivot|==pivot|?|>pivot|*+-------------------------------------------------+*^^^*|||*lesskgreat**Invariants:**allin(left,less)<pivot*allin[less,k)==pivot*allin(great,right)>pivot**Pointerkisthefirstindexof?-part.*/for(intk=less;k<=great;++k){if(a[k]==pivot){continue;}intak=a[k];if(ak<pivot){//Movea[k]toleftparta[k]=a[less];a[less]=ak;++less;}else{//a[k]>pivot-Movea[k]torightpartwhile(a[great]>pivot){--great;}if(a[great]<pivot){//a[great]<=pivota[k]=a[less];a[less]=a[great];++less;}else{//a[great]==pivot/**Eventhougha[great]equalstopivot,the*assignmenta[k]=pivotmaybeincorrect,*ifa[great]andpivotarefloating-point*zerosofdifferentsigns.Thereforeinfloat*anddoublesortingmethodswehavetouse*moreaccurateassignmenta[k]=a[great].*/a[k]=pivot;}a[great]=ak;--great;}}/**Sortleftandrightpartsrecursively.*Allelementsfromcenterpartareequal*and,therefore,alreadysorted.*/sort(a,left,less-1,leftmost);sort(a,great+1,right,false);}归并排序

你不会以为元素多（>快排阈值）就一定要用归并了吧？

错！元素多时确实对算法的稳定性有要求，可是如果这些元素能够稳定快排呢？

开发JDK的大牛显然考虑了这一点：他们在归并排序之前对元素进行了是否能稳定快排的判断：

如果数组本身几乎已经排好了（可以看出几段有序数组的拼接），那还排什么，理一理返回就行了如果出现连续33个相等元素——使用快排（实话说，我没弄明白为什么，有无大牛给我指点迷津？）

//判断结构是否适合归并排序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{//连续MAX_RUN_LENGTH（33）个相等元素，使用快排for(intm=MAX_RUN_LENGTH;++k<=right&&a[k-1]==a[k];){if(--m==0){sort(a,left,right,true);return;}}}//count达到MAX_RUN_LENGTH，使用快排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;}

归并排序源码

byteodd=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;}最后第一次看文章的朋友可以关注我Android进阶之路不定期发布大厂面试题、Android架构技术知识点及解析等内容，还有学习PDF+源码笔记+面试文档+进阶视频分享

点击就看学习小彩蛋
点个赞，收藏起来认真学习哦