Record the differences and improvements of one-way quick sort, two-way quick sort and three-way quick sort

Basic idea: divide the records to be arranged into two independent parts through one-time sorting. If the keywords of one part of the records are smaller than those of the other part and larger than those of the other part, the records of the two parts can be sorted separately to achieve the order of the whole sequence.

All the way quick sorting steps

1. Pick an element from the sequence and set it to V

2. Reorder the sequence. All elements smaller than V are placed in front of V, and all elements larger than V are placed behind V (the same number to the right). After this partition exits, V is in the middle of the sequence.

3. Recursively sort the subsequence less than V and the subsequence greater than v.

Disadvantages: meeting a large number of the same elements will greatly waste time and complexity, which does not meet expectations

code implementation

public class QuickSort01 extends Sort{
    public QuickSort01(int[] arr) {
        super(arr);
    }
    @Override
    public void sort() {
        quickSort(0,arr.length - 1);
    }

    private void quickSort(int L, int R) {
        if (L >= R) {
            return;
        }
        //First divide the array and return the midpoint after division
        int p = partition(L ,R);
        quickSort(L, p - 1);//After the division, arrange it again
        quickSort(p + 1, R);
    }

    private int partition(int L, int R) {
        //Optimize the random number and change the following number with the first number
        //Try to avoid extreme situations with a random corner mark
        //L = 5 R = 10   [0,5] + 5 = [5,10]
        swap(L, (int) (Math.random() * (R - L + 1) + L));
        int v = arr[L];//Let the first continue in recursion

        //arr[l+1 ~ j] < v < arr[j+1 ~ i)
        int j = L;
        for (int i = L + 1; i <= R; i++) {
            if (arr[i] < v) {
                swap(j + 1, i);
                j++;
            }
        }
        swap(L, j);//transposition
        return j;
    }
}

Two way quick sort

step

1. Pick an element from the sequence and set it to V

2. Reorder the sequence. There is a cursor on the left and right. When the left cursor i is greater than the current V, the right cursor j is traversed from the back. If it is smaller than V, it is exchanged with the current left cursor i. This is repeated until the two cursors meet. (in the code operation, the left i stops when it is not less than V, and the right j stops when it is not greater than V, and then exchange the two values and repeat)

3. Recursively and repeatedly sort the subsequence less than V and the subsequence greater than v.

The ultimate goal is to divide the equal elements roughly into two sides to reduce the number of subsequent recursion and avoid extreme cases.

code implementation

//Two way quick sort
public class QuickSort02 extends Sort {//Implement abstract classes
    public QuickSort02(int[] arr) {//Reference parent class construction copy
        super(arr);
    }

    @Override
    public void sort() {
        quickSort(0, arr.length - 1);
    }

    private void quickSort(int L, int R) {
        if (L >= R) {//judge
            return;
        }
        //Divide the array and return the midpoint after division
        int p = partition(L, R);
        quickSort(L, p - 1);
        quickSort(p + 1, R);
    }

    private int partition(int L, int R) {
        //Optimize the random number and change the following number with the first number
        //Try to avoid extreme cases (ascending cases)
        swap(L, (int) (Math.random() * (R - L + 1) + L));
        int v = arr[L];
        int i = L + 1;
        int j = R;
        while (true) {
            while (i <= R && arr[i] < v) {//Judge that the corner mark of i does not cross the boundary and go to a stop not less than V
                i++;
            }
            while (j >= L + 1 && arr[j] > v) {//Go to a stop not greater than V
                j--;
            }
            if (i > j) {//Judge not to cross the line
                break;
            }
            swap(i, j);
            i++;
            j--;
        }
        swap(L, j);//Change V to the middle
        return j;
    }
}

Three way quick sort

The biggest difference between the first two ways is to open up a separate middle area to store the same elements, and then traverse and exchange from both ends.

It's like making one-way fast platoon for the left area and the middle area, merging the left area with the middle area and making two-way fast platoon with the right area.

The code is as follows

//Three way quick sort
public class QuickSort03 extends Sort {
    public QuickSort03(int[] arr) {
        super(arr);
    }

    @Override
    public void sort() {
        quickSort(0, arr.length - 1);
    }

    private void quickSort(int L, int R) {
        if (L >= R) {
            return;
        }//Random elements
        swap(L, (int) (Math.random() * (R - L + 1) + L));
        int v = arr[L];
        int lt = L;
        int gt = R + 1;
        int i = L + 1;
        while (i < gt) {
            if (arr[i] < v) {//Left expansion
                swap(i, lt + 1);
                lt++;
                i++;
            } else if (arr[i] > v) {//Right expansion
                swap(i,gt - 1);
                gt--;
            } else {//Intermediate zone
                i++;
            }
        }
        //Division area
        swap(L,lt);
        quickSort(L,lt - 1);
        quickSort(gt, R);
    }
}