浅浅梳理一下双轴快排（DualPivotQuickSort）

本文主要是介绍浅浅梳理一下双轴快排（DualPivotQuickSort），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原理：

双轴嘛，也就是取两个基准pivot1，pivot2，更高效的分拣原数组中的元素。

取两基准分别标记数组两端，然后拿一个变量k对基准之间的元素进行扫描。通过一定的交换使当前区域分为X < pivot1，pivo1 <= X <= pivot2，pivot2 < X 三部分。

i k ...... j

X < pivot1 i pivo1 <= X <= pivot2 k ...... j X>pivot2

之后再将三区域分别递归即可

由于k向后扫描，设置函数成立条件（k < j）比较好。这样的话应该优先处理区域前半部分的数据

演示：

用数组[2, 1, 3, 4, 7, 0, 5, 9, 6, 8]为例过一遍：

初始状态，基准分别为2， 8

第①次，1属于第1区间，同时也呆在第1区间，不管它~ i，k继续前进
[2, 1, 3, 4, 7, 0, 5, 9, 6, 8]

i k j
第②次：3 > 2，i 停下等待k找到一个乱跑的第1区间成员把3这个第2区间成员换掉，k独自前进

[2, 1, 3, 4, 7, 0, 5, 9, 6, 8]

i k j

第③次：k独自前进中...

[2, 1, 3, 4, 7, 0, 5, 9, 6, 8]

i k j

第④次：k独自前进中.>_<.

[2, 1, 3, 4, 7, 0, 5, 9, 6, 8]

i k j

第⑤次：k遇到了0，0 < 2，i先向前一步标记到k离开的地方...而后与k将标记的数交换，k继续前进

[2, 1, 0, 4, 7, 3, 5, 9, 6, 8]

i k j

第⑥次：k独自前进...

[2, 1, 0, 4, 7, 3, 5, 9, 6, 8]

i k j

第⑦次：k遇到了9！9 > 8。k告诉j赶紧找到一个不该在第3区间呆着的数，j急忙搭上while，回头便遇到了老6...j便把6踢给了k，和9换了位置。k得到6后判断了一下，这不是第1区间的元素，便让i继续原地待命

[2, 1, 0, 4, 7, 3, 5, 6, 9, 8]

i k j

第⑧次：k继续前进，k，j相遇了，它们之间没有未扫描过的元素了。分区结束。i和j此时站的位置是3区间的两个交界处，也即两基准要放的位置。于是将左基准与i位置的数交换，右基准与j位置的数交换，第一次对数据的分拣便完成了

[0, 1, 2, 4, 7, 3, 5, 6, 8, 9]

i kj

第一次分拣完后：

[0, 1, 2, 4, 7, 3, 5, 6, 8, 9]（红色是基准）

输出如下：

代码：

Main类：
package SeachAndFindTest;
import java.util.*;
/*Main类
*/
public class Main {private static final Scanner sc = new Scanner(System.in);private static void timeCost(long begin, long end){System.out.println("\n用时： " + (end - begin) + "ms\n");}private static int[] makeRandomArr(int size, int left, int right){int[] arr = new int[size];for(int i = 0; i < size; i++){arr[i] = (int)(Math.random()*(right - left + 1) + left);}return arr;}private static int[] getRandomArr(int[] arr, int size){return Arrays.copyOf(arr, size);}private static void printArr(int[] arr){System.out.println(Arrays.toString(arr));}public static void main(String[] args) {System.out.print("""请输入期望的数组长度，数据范围。例：期望数组长度为10，数据范围[0,10]，则输入：10 0 10请输入：\s""");int size = sc.nextInt(), left = sc.nextInt(), right = sc.nextInt();if(size <= 0 || left < 0 || left > right){System.out.println("不是有效数据！");return;}double flag = (double)(right - left + 1) / size;if(flag < 0.33){System.out.println("\n您当前测试的数据将有高重复度的特征，相关算法耗时会有不同\n");}else{System.out.println("\n您当前测试的数据将有低重复度的特征，相关算法耗时会有不同\n");}int[] basicArr = makeRandomArr(size, left, right);int[] arr = getRandomArr(basicArr, size);System.out.println("当前数组长度：" + arr.length + "; 数据范围：[" + left + "," + right + "];");boolean t = false;if(size <= 10000){t = true;System.out.println("数组： ");printArr(arr);}else{System.out.println("当前数组长度大于10000，是否展示？请输入 是/否：");String rubbish = sc.next();String ans = sc.nextLine();if(Objects.equals(ans, "是")){t = true;System.out.println("数组： ");printArr(arr);}}long begin = System.currentTimeMillis();AllKindQuickSort.DualPivotQuickSort.sort(arr);long end = System.currentTimeMillis();if(t){System.out.println("有序数组：");printArr(arr);}timeCost(begin, end);sc.close();}
}
DualPivotQuickSort类部分：
//双轴快排
public static class DualPivotQuickSort{public static void sort(int[] arr) {dualPivotQuickSort(arr, 0, arr.length - 1);}private static void dualPivotQuickSort(int[] arr, int left, int right) {if (left < right) {if (arr[left] > arr[right]) {//升序排序，先调整两基准顺序swap(arr, left, right);}int pivot1 = arr[left], pivot2 = arr[right];int i = left, j = right, k = left + 1;level_one: while (k < j) {//先判断k标记的数是否属于第一区间，如果是的话，i向前//一位到达第二区间首，然后i，k标记的数进行交换，扩展//第一区间同时第二区间后移，其他区间关系类似if (arr[k] < pivot1) {swap(arr, ++i, k++);}//下面再尝试用k，j寻找两个不在正确区间的数else if (arr[k] <= pivot2) {//在第二区间找一个//由于要不断搬运第一区间的数(第一个if)，这里不//能用while，必须一步一步找k++;}else {//在第三区间找一个while (arr[--j] > pivot2) {//如果找完了都符合，那么这次分区结束，退出循环if (j <= k) {break level_one;}}//找到两个不合法的值后，交换他们swap(arr, j, k);//再判断需不需要继续向前调整if (arr[k] < pivot1) {swap(arr, ++i, k);}//k后移，等待继续比较k++;}}//分区完成后，将两基准值放到正确位置swap(arr, left, i);swap(arr, right, j);//再分别对三个区间递归处理dualPivotQuickSort(arr, left, i - 1);dualPivotQuickSort(arr, i + 1, j - 1);dualPivotQuickSort(arr, j + 1, right);}}
}
输出：