Java QuickSort principle and implementation code

QuickSort is a commonly used, more efficient sorting algorithm, and is often mentioned during the interview process. Let’s explain its principles in detail and give a Java version implementation.

Quick sorting idea:

Two independent parts are divided by sorting the data element set Rn in one trip. One part of the keyword is smaller than the other part. Then sort the keywords of the two parts one by one until there is only one independent element, and the entire element collection is in order.

The process of quick sorting - the method of digging holes and filling numbers (this is a very vivid name), for an element set R[ low ... high ], first take a number (usually R[low]) as a reference, and R[low] rearranges all elements as the benchmark.

All those smaller than R[low] are placed in the front, all those larger than R[low] are placed in the back, and then R[low] is used as the boundary, and R[low ... high] is divided into two subsets and then divided . Until low >= high .

For example: The process of performing a quick sorting of R={37, 40, 38, 42, 461, 5, 7, 9, 12} is as follows (Note: The following table of elements described below starts from 0):

Start selecting the base base = 37, the table below is low = 0, high = 8, starting from high=8, if R[8] < base, write the content in the high position into R[low], and then high The position is empty, low = low +1;

Start probing from low, since low=1, R[low] > base, write R[low] to R[high], high = high -1;

Low < high is detected, so the first quick sorting still needs to continue:

At this time low=1, high=7, because R[high] < base, R[high] is written into R[low], low = low + 1;

Start detection from low, low = 2, R[low] >base, so R[low] is written to R[high], high=high-1;

Continue to detect low is less than high

At this time low=2, high=6, similarly, R[high] < base, write R[high] to R[low], low=low+1;

Continue to detect from low, low = 3 , high=6 , R[low] > base , write R[low] to R[high], high = high-1;

Continue to detect that the low is less than high

At this time low=3, high=5, similarly, R[high] < base, write R[high] into R[low], low = low +1;

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

At this time, low == high == 4 is detected; this position is the location where the base is located, and base is written to this position.

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

(Note: In the above form, you can see that there are some duplicate data in the sorting (no duplicate data in the original data). This is because the data at that location is not cleared. We look at the data of the memory block at a specific time. It is still it until the next time the data is written to the location - the data at this location is meaningless dirty data, called "pit")

Quick sort Java implementation:

The code copy is as follows:

private static boolean isEmpty(int[] n) {

return n == null || n.length == 0;

}

// //////////////////////////////////////////////// ///

/**

* Quick sorting algorithm idea - method of digging holes and filling:

*

* @param n Array to be sorted

*/

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 = partition(n, l, h);

quickSort(n, l, pivot - 1);

quickSort(n, pivot + 1, h);

}

}

private static int partition(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 a function like this in the code:

The code copy is as follows:

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

This function can be implemented to sort data elements in the element set between specific l and h positions.

That’s all for quick sorting.