本篇内容介绍了“Java中怎么使用DualPivotQuicksort排序”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

这里描述 leftmost = true 的情况，也就是会从数组的开始一直排序到数组的结尾。

数组类型：int[]、long[]、short[]、char[]、float[]、double[]，还有比较特殊的 byte[]

适合长度短的数组排序，对于byte[] 长度小于等于30 和 其它数组长度小于47 的情况，会使用这种排序

代码以 int[] a 为例：

//第一次循环i=j=0，之后每次循环j=i.//j=++i相当于在每次循环的最后执行{i++;j=i;}//j=i++相当于在每次循环的最后执行{j=i;i++;}for(inti=0,j=i;i<(length-1);j=++i){intai=a[i+1];//每次循环的目的是将下一个数排到它应该在的位置，这里ai就是下一个数while(ai<a[j]){//while循环的目的是确定j的值和把所有比ai大的项向后移一位来腾出ai的位置a[j+1]=a[j];//把比ai大的项向后移一位if(j--==left){//j--确定j的值，也就是确定ai的位置，j可能等于-1break;}}a[j+1]=ai;//j+1就是ai的位置}2. 计数排序（counting sort）

只针对byte[] 长度大于30的情况，因为byte的范围是[-128, 127]，只有256个数，所以循环会利用这点

int[]count=newint[256];//第一次循环：计数for(inti=(0-1);++i<=(length-1);count[a[i]-(-128)]++);//第二次循环：给<byte[]a>赋值//循环结束条件以k为标准，k<=0就会停止;//因为i和k没有固定关系，所以没有增量表达式，但在方法体中利用--i和--k进行增量。for(inti=256,k=length;k>0;){while(count[--i]==0);//如果计数个数为0，什么也不做，--ibytevalue=(byte)(i+(-128));ints=count[i];do{a[--k]=value;}while(--s>0);}3. 快速排序（Quicksort）

适合长度短的数组排序，插入排序也是快速排序的一种。
对于byte[] 长度大于30的情况会使用 计数排序，不是这种排序。
而对于其它数组长度大于等于47并且小于286 的情况，会使用这种排序。

//7等分一段的长度近似值intseventh=(length>>3)+(length>>6)+1;//一个数组分为7段，则有五个切割点，如下为五个切割点的下标inte3=(left+right)>>>1;//Themidpointinte2=e3-seventh;inte1=e2-seventh;inte4=e3+seventh;inte5=e4+seventh;3.2 对五个切割点进行插入排序

//Sorttheseelementsusinginsertionsortif(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;}}}}3.3 创建两个变量作为下标记录值

//中心部分第一个元素的索引intless=left;//右部分第一个元素前的索引intgreat=right;3.4 五个切割点的值都不相同的情况

这种情况会将排序分三块，变量 pivot1 和 pivot2 作为三块区域值的区分：
第一块区域所有的值都 < pivot1
第二块区域所有的值都 >= pivot1 并且 <= pivot2
第三块区域所有的值都 > pivot2

//取两个值作为分区值intpivot1=a[e2];intpivot2=a[e4];//要排序的第一个和最后一个元素被移动到以前由枢轴占据的位置。//当分区完成时，轴心点被交换回它们的最终位置，并从随后的排序中排除。a[e2]=a[left];a[e4]=a[right];//less一开始等于left，great一开始等于right。//跳过小于或大于分割值的元素。while(a[++less]<pivot1);//没有判断第一个while(a[--great]>pivot2);//没有判断最后一个//循环带outer:，`breakouter;`会跳出整个循环，也就是结束整个下面的for循环。//less不参与循环，只是一开始给k赋值，less的变化始终是`++less`，用来交换数组中的值。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;}}//循环结束，交换left和(less-1)的值，也就是处理循环前`a[e2]=a[left];`导致的分区错误a[left]=a[less-1];a[less-1]=pivot1;//循环结束，交换right和(great+1)的值，也就是处理循环前`a[e4]=a[right];`导致的分区错误a[right]=a[great+1];a[great+1]=pivot2;//分为三部分后，嵌套排序第一部分和第三部分sort(a,left,less-2,leftmost);sort(a,great+2,right,false);3.4.2 第二块处理

分两种情况：
如果第二块剩余项超过数组要排序总长度的4/7，会将等于pivot1和等于pivot2的值取出来，再次缩减less和great中间的部分，然后进行排序。
否则直接排序。

if(less<e1&&e5<great){//剩余的中间部分超过4/7/**Skipelements,whichareequaltopivotvalues.*/while(a[less]==pivot1){++less;}while(a[great]==pivot2){--great;}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];a[less]=pivot1;++less;}else{//pivot1<a[great]<pivot2a[k]=a[great];}a[great]=ak;--great;}}}//Sortcenterpartrecursivelysort(a,less,great,false);3.5 五个切割点的值有相同的情况（单轴分区 Partitioning with one pivot）

这种情况也可以理解为将排序分三块，但只需要一个变量 pivot 作为三块区域值的区分：
第一块区域所有的值都 < pivot
第二块区域所有的值都 = pivot，因为这块区域的值都相等，最后就可以不用排序
第三块区域所有的值都 > pivot

//取下标在中间的值做一个临时变量，该变量是中值的廉价近似值，作为分割值intpivot=a[e3];//less一开始等于left，great一开始等于right。//方法体内部不断修改great的值，使循环执行的次数不断的缩减，一次循环great可以减少0，可以减少1，可以减少n。//less并不影响循环，只是作为临时变量进行数组中值的交换，始终小于等于k，一次循环只能加1或不加。for(intk=less;k<=great;++k){if(a[k]==pivot){//如果a[k]的值等于分割值，跳过continue;}intak=a[k];//取出a[k]值赋给临时变量akif(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;}}//分为三部分后，嵌套排序第一部分和第三部分sort(a,left,less-1,leftmost);sort(a,great+1,right,false);4. 合并排序（merge sort）

长度很长的数组排序，对于其它数组长度大于等于286 的情况，会使用这种排序。

两个关键常量，起控制作用

//合并排序中的最大运行次数staticfinalintMAX_RUN_COUNT=67;//合并排序中运行的最大长度staticfinalintMAX_RUN_LENGTH=33;

排序方法

/***长度大于等于286的int数组排序**@parama*要排序int数组*@paramleft*起始下标*@paramright*结束下标*@paramwork*null*@paramworkBase*0*@paramworkLen*0*/privatestaticvoidlargeSort(int[]a,intleft,intright,int[]work,intworkBase,intworkLen){/**Indexrun[i]isthestartofi-thrun(ascendingordescending*sequence).*/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,useQuicksortinsteadof*mergesort.*/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;}}

“Java中怎么使用DualPivotQuicksort排序”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！