Text Description:

1. Choose a pivot point (Pivot) for each round of sorting

(1) Let the elements smaller than the reference point enter one partition, and the elements larger than the reference point enter another partition

(2) When the partition is completed, the position of the reference point element is its final position

2. Repeat the above process in subpartitions until the number of subpartitions is less than or equal to 1. This is divide-and-conquer

Implementation method:

1, unilateral cycle fast row

(1) Select the rightmost element as the reference point element

(2) The j pointer is responsible for finding elements smaller than the reference point, and once found, it will exchange with I

(3) The I pointer maintains the boundary of the element less than the reference point, which is the target index of each exchange

(4) The final datum is exchanged with I, and I is the partition position

2, bilateral circulation fast row

(1) Select the leftmost element as the reference point element

(2) The J pointer is responsible for looking for elements smaller than the reference point from right to left, and the I pointer is responsible for looking for elements larger than the reference point from left to right. Once the two are found, they will be exchanged until I and J intersect

(3) The final datum is exchanged with I (when I is equal to J), and I is the partition position

code

Unilateral circulation

public class QuickSortDemo {

    public static void main(String[] args) {
        int[] array = {5.9.7.4.1.3.2.8};

        quickSort(array);
        System.out.println(Arrays.toString(array));
    }

    /** * quick row loop * take the rightmost element as the base value * I is responsible for maintaining the partition boundary, j is responsible for finding the greater than the base value from left to right * and swap with I, finally I is the base value to go to the location * and continue to partition the steps * end condition: The element in the partition <= 1 */
    public static void quickSort(int[] array, int l, int h) {
        if (l >= h) {
            return ;
        }
        // Take the rightmost element of the partition as the reference point
        int pv = array[h];
        // I maintains partition boundaries. The left side of I is smaller than the base value and the right side is larger than the base value
        int i = l;

        for (int j = l; j < h; j++) {
            if (array[j] < pv) {
                if (i != j) {
                    swap(array, i, j);
                }
                i++;
            }
        }
        // The position of I is where the reference point goes
        if(i ! = h) { swap(array, i, h); }// perform recursion
        quickSort(array, l, i - 1);
        quickSort(array, i + 1, h);
    }

    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    /** * Swaps two elements of the array */
    public static void swap(int[] array, int i, int j) {
        inttemp = array[i]; array[i] = array[j]; array[j] = temp; }}Copy the code

Bilateral circulation

/** * quick row double-sided loop ** take the leftmost element as the base value * I from left to right find * j from left to right find * I from left to right find * j from left to right find * I from left to right find * j from left to right find * I from left to right find * J from left to right find * I from left to right less than the base value, j swap * finally I or j is the base value to go */
public static void quickSort(int[] array, int l, int h) {
    if (l >= h) {
        return ;
    }
    // Base on the leftmost element
    int pv = array[l];
    int i = l;
    int j = h;

    while (i < j) {
        // First j then I
        while (i < j && array[j] > pv) {
            j--;
        }

        // array[I] <= pv
        while (i < j && array[i] <= pv) {
            i++;
        }

        swap(array, i, j);
    }
    // Swap elements
    swap(array, i, l);

    quickSort1(array, l, i - 1);
    quickSort1(array, i + 1, h);
}
Copy the code