「排序算法」图解双轴快排 (2)

而如果arr[k]>pivot2.(区间自行安排即可)有点区别的就是right可能连续的大于arr[k],比如9 3 3 9 7如果我们需要跳过7前面9到3才能正常交换，这和快排的交换思想一致，当然再具体的实现上就是right--到一个合适比arr[k]小的位置。然后swap(arr,k,right)切记此时k不能自加。因为带交换的那个有可能比pivot1还小要和left交换。

如果是介于两者之间，k++即可

收尾工作

在执行完这一趟即k=right之后，即开始需要将pivot1和pivot2的数值进行交换

swap(arr, start, left); swap(arr, end, right);

然后三个区间根据编号递归执行排序函数即可。

双轴快排代码

在这里，分享下个人实现双轴快排的代码：

import java.util.Arrays; public class 双轴快排 { public static void main(String[] args) { int a[]= {7,3,5,4,8,5,6,55,4,333,44,7,885,23,6,44}; dualPivotQuickSort(a,0,a.length-1); System.out.println(Arrays.toString(a)); } private static void dualPivotQuickSort(int[] arr, int start, int end) { if(start>end)return;//参数不对直接返回 if(arr[start]>arr[end]) swap(arr, start, end); int pivot1=arr[start],pivot2=arr[end];//储存最左侧和最右侧的值 //(start，left]:左侧小于等于pivot1 [right,end)大于pivot2 int left=start,right=end,k=left+1; while (k<right) { //和左侧交换 if(arr[k]<=pivot1) { //需要交换 swap(arr, ++left, k++); } else if (arr[k]<=pivot2) {//在中间的情况 k++; } else { while (arr[right]>=pivot2) {//如果全部小于直接跳出外层循环 if(right--==k) break ; } if(k>=right)break ; swap(arr, k, right); } } swap(arr, start, left); swap(arr, end, right); dualPivotQuickSort(arr, start, left-1); dualPivotQuickSort(arr, left+1, right-1); dualPivotQuickSort(arr, right+1, end); } static void swap(int arr[],int i,int j) { int team=arr[i]; arr[i]=arr[j]; arr[j]=team; } }

执行结果为：

好啦，到这里双轴快排就实现完成啦。至于算法分析，希望在评论区和你们讨论哦！