Briefly sort out the dualpivotquicksort

principle ：

Biaxial , That is, take two benchmarks pivot1,pivot2, More efficient sorting of elements in the original array .

Take two benchmarks to mark both ends of the array , Then take a variable k Scan elements between benchmarks . Through certain exchange, the current area is divided into X < pivot1,pivo1 <= X <= pivot2,pivot2 < X In the third part of .

i

k

......

j

X < pivot1

i

pivo1 <= X <= pivot2

k

......

j

X>pivot2

Then recurse the three regions respectively

because k Scan back , Set the conditions for the function （k < j） better . In this case, priority should be given to the data in the first half of the region

demonstration ：

Using arrays [2, 1, 3, 4, 7, 0, 5, 9, 6, 8] As an example ：

The initial state , The benchmarks are 2, 8

The first ① Time ,1 Belong to the first 1 Section , At the same time, stay in the first 1 Section , Whatever it is ~ i,k To move forward
[2, 1, 3, 4, 7, 0, 5, 9, 6, 8]

  i   k                              j
The first ② Time ：3 > 2,i Stop and wait k Find a running number 1 Interval members put 3 This article 2 Replace the interval members ,k Go alone

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

      i  k                           j

The first ③ Time ：k Moving forward alone ...

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

      i      k                       j

The first ④ Time ：k Moving forward alone .>_<.

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

      i          k                   j

The first ⑤ Time ：k Yes 0,0 < 2,i First step forward and mark to k The place to leave ... Then with k Swap marked numbers ,k To move forward

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

         i               k           j

The first ⑥ Time ：k Go alone ...

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

         i               k           j

The first ⑦ Time ：k Yes 9！9 > 8.k tell j Hurry to find one who shouldn't be in the first 3 Number of interval stays ,j Catch up in a hurry while, Looking back, I met old 6...j Then put 6 Kicked to k, and 9 Changed position .k obtain 6 Then I judged , This is not the first 1 The elements of the interval , Let i Continue to stand by

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

          i                  k   j 

The first ⑧ Time ：k To move forward ,k,j Met , There are no unscanned elements between them . The partition ends .i and j At this time, the position of the station is 3 The two junctions of the section , That is, where the two benchmarks should be placed . So the left datum is compared with i The number exchange of positions , Right datum and j The number exchange of positions , The first sorting of data is completed

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

          i                      kj 

After the first sorting ：

[0, 1, 2, 4, 7, 3, 5, 6, 8, 9]（ Red is the benchmark ）

Output is as follows ：

Code ：

Main class ：

package SeachAndFindTest;
import java.util.*;
/*
    Main class 
*/
public class Main {
    private static final Scanner sc = new Scanner(System.in);
    private static void timeCost(long begin, long end){
        System.out.println("\n when ： " + (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("""
                 Please enter the expected array length , Data range .
                 example ： The expected array length is 10, Data range [0,10], Then input. ：10 0 10
                 Please enter ：\s""");
        int size = sc.nextInt(), left = sc.nextInt(), right = sc.nextInt();
        if(size <= 0 || left < 0 || left > right){
            System.out.println(" Not valid data ！");
            return;
        }
        double flag = (double)(right - left + 1) / size;
        if(flag < 0.33){
            System.out.println("\n The data you are currently testing will have the characteristics of high repeatability , The time consumption of relevant algorithms will be different \n");
        }else{
            System.out.println("\n The data you are currently testing will have the characteristics of low repeatability , The time consumption of relevant algorithms will be different \n");
        }
        int[] basicArr = makeRandomArr(size, left, right);
        int[] arr = getRandomArr(basicArr, size);
        System.out.println(" Current array length ：" + arr.length + ";  Data range ：[" + left + "," + right + "];");
        boolean t = false;
        if(size <= 10000){
            t = true;
            System.out.println(" Array ： ");
            printArr(arr);
        }else{
            System.out.println(" The current array length is greater than 10000, Whether to show ？ Please enter   yes / no ：");
            String rubbish = sc.next();
            String ans = sc.nextLine();
            if(Objects.equals(ans, " yes ")){
                t = true;
                System.out.println(" Array ： ");
                printArr(arr);
            }
        }
        long begin = System.currentTimeMillis();
        AllKindQuickSort.DualPivotQuickSort.sort(arr);
        long end = System.currentTimeMillis();
        if(t){
            System.out.println(" Ordered array ：");
            printArr(arr);
        }
        timeCost(begin, end);
        sc.close();
    }
}

DualPivotQuickSort Class section ：

// Double quick row 
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]) {// Ascending sort , First adjust the order of the two benchmarks 
                swap(arr, left, right);
            }
            int pivot1 = arr[left], pivot2 = arr[right];
            int i = left, j = right, k = left + 1;
            level_one: while (k < j) {
                // First judge k Whether the marked number belongs to the first interval , If so ,i forward 
                // One reaches the first of the second interval , then i,k Exchange the marked number , Expand 
                // The first interval moves back at the same time as the second interval , Other interval relationships are similar 
                if (arr[k] < pivot1) {
                    swap(arr, ++i, k++);
                }
                // Now try again k,j Look for two numbers that are not in the correct range 
                else if (arr[k] <= pivot2) {// Find one in the second interval 
                    // Because the number of the first interval has to be moved constantly ( first if), Here no 
                    // It works while, We must find it step by step 
                    k++;
                }
                else {
                    // Find one in the third interval 
                    while (arr[--j] > pivot2) {
                        // If you find it, it matches , So this partition is over , Exit loop 
                        if (j <= k) {
                            break level_one;
                        }
                    }
                    // After finding two illegal values , Exchange them 
                    swap(arr, j, k);
                    // Then judge whether it is necessary to continue to adjust forward 
                    if (arr[k] < pivot1) {
                        swap(arr, ++i, k);
                    }
                    //k Move backward , Wait to continue the comparison 
                    k++;
                }
            }
            // After the partition is completed , Put the two reference values in the correct position 
            swap(arr, left, i);
            swap(arr, right, j);
            // Then recursively handle the three intervals respectively 
            dualPivotQuickSort(arr, left, i - 1);
            dualPivotQuickSort(arr, i + 1, j - 1);
            dualPivotQuickSort(arr, j + 1, right);
        }
    }
}

Output ：