Quick sorting of top ten sorting

Exchange method

The steps of exchange quick sorting

1、 Find a dividing point , Let the value on the left of the dividing point be less than the dividing point , The value on the right is greater than or equal to the dividing point .

2、 Do this on the left .

3、 Right, do it on the right .

Core code

    #  Incomplete code 
    private static int partition2(int[] arr, int left, int right) {
        int i = left, j = right;
        int pivot = arr[left];
        while (i < j) {
             while (i < j && arr[j] >= pivot) {
                j--;
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                swap(arr, i, j);
            }
        }
        swap(arr, left, i);
        return i;
    }

Q&A

Why go forward from the back , Can you change the position ？

1、 Because our chosen pacesetter is on the left , So we're going to traverse from the right

Then why? Because the pacesetter we choose is on the left , Just start on the right ?

Further analysis , We finally need to set a model i==j The value of the stopped position is exchanged , So where to stop , It must be smaller than the pacesetter , Otherwise, I will not be satisfied , The value on the left of the pacesetter is less than the premise of the pacesetter . Suppose we start on the left , Then there will be people who finally stop at a place larger than the pacesetter , It leads to the violation of the principles mentioned above when the exchange finally takes place . And from the right, we can guarantee that we must encounter Value smaller than the pacesetter or return to the pacesetter's position Just stop .

2、 If you want to start on the left , Then the pacesetter can choose the rightmost .