Java QuickSort principle and implementation code

QuickSort is a commonly used and efficient sorting algorithm and is often mentioned in interviews. The following is a detailed explanation of his principles, given a Java version of the implementation.

Quick sort idea:

Two separate parts of the set of data elements Rn are divided by a single sort. The keyword in one section is smaller than the keyword in the other section. Then sort the keywords of the two parts separately until there is only one independent element, and the whole set of elements is in order.

Quicksort process - the method of digging holes and filling Numbers (this is a very vivid name), for a set of elements R[low... high], first take a number (usually R[low]) as a reference, with R[low] as the benchmark to rearrange all the elements.

All the ones smaller than R[low] are put in front, and all the ones larger than R[low] are put in back, and then R[low] is divided into two subsets and and then divided. Until the low > =   High.

For example, a quick sort procedure for R={37, 40, 38, 42, 461, 5, 7, 9, 12} is as follows:
The original sequence 37 40 38 42 461 5 7 9 12 A: high - > Low, 12 40 38 42 461 5 7 9 12 A: low - > high 12 40 38 42 461 5 7 9 40 2: high - > Low, 12 9 38 42 461 5 7 9 40 2: low - > high 12 9 38 42 461 5 7 38 40 3: high - > Low, 12 9 7 42 461 5 7 38 40 3: low - > high 12 9 7 42 461 5 42 38 40 4: high - > Low, 12 9 7 5 461 5 42 38 40 4: low - > high 12 9 7 5 461 461 42 38 40 Sort the results in one pass 12 9 7 5 37 461 42 38 40

Start by selecting the benchmark base = 37, and the following table shows the initial position: low = 0, high = 8& PI; , starting from high=8, if R[8] < Base,   Write the content in the high position to R[low], leave the high position empty, low = low +1;

Start with low, because low=1, R[low] > Base, so write R[low] to R[high], high = high-1;

Low < detected; High, so the first quicksort still needs to continue:

Low =1, high=7, because R[high] < Base, so write R[high] to R[low],low = low + 1;

Start with low,low = 2, R[low] > Base, so R[low] goes to R[high], high=high-1;

Continue to detect that low is less than high

At this time, low=2, high=6, the same R[high] < Base, write R[high] to R[low], low=low+1;

Continue to probe from low,low = 3, high=6, R[low] > Base, write R[low] into R[high], high = high-1;

Continue to detect that low is less than high

At this time, low=3, high=5, the same R[high] < Base, write R[high] to R[low], low = low +1;

Continue to probe from low, low = 4, high=5, due to R[low] > Base, write R[low] into R[high], high = high-1;

Low == high == 4; The location is the location where the base is, and the base is written to that location.

Then do a quick sort on the subsequences Rs1 ={12,9,7,5} and Rs2={461,422,38,40} until there is only one element or no element in the Rsi.

(note: you can see in the above form a trip to the sorting of some repetitive data (no duplicate data) in the original data, this is because there is no clear the location of the data, we see the memory block of data at a specific time is it, until the next writing data to the location - in the location of the data is a meaningless dirty data, referred to as the "pit")

Java implementation of quicksort:

private static boolean isEmpty(int[] n) {
        return n == null || n.length == 0;
    }
    // ///////////////////////////////////////////////////
    
    public static void quickSort(int[] n) {
        if (isEmpty(n))
            return;
        quickSort(n, 0, n.length - 1);
    }
    public static void quickSort(int[] n, int l, int h) {
        if (isEmpty(n))
            return;
        if (l < h) {
            int pivot = partion(n, l, h);
            quickSort(n, l, pivot - 1);
            quickSort(n, pivot + 1, h);
        }
    }
    private static int partion(int[] n, int start, int end) {
        int tmp = n[start];
        while (start < end) {
            while (n[end] >= tmp && start < end)
                end--;
            if (start < end) {
                n[start++] = n[end];
            }
            while (n[start] < tmp && start < end)
                start++;
            if (start < end) {
                n[end--] = n[start];
            }
        }
        n[start] = tmp;
        return start;
    }

There is such a function in the code:

 public static void quickSortSwap(int[] n, int l, int h)

This function can be implemented, in the collection of elements in the specific & PI; L  To   Sort the data elements between the h positions.
That's it for quicksort.