Compared with algorithms such as bubble sorting, selection sorting, etc., the specific algorithm principles and implementation of quick sorting are difficult. To better understand quick sorting, we still describe the algorithmic principles of quick sorting in detail in the form of examples. In the previous sorting algorithm, we will use the height sorting problem of 5 athletes as an example to explain it. In order to better reflect the characteristics of fast sorting, we will add 3 more athletes here. The 8 athletes and their height information in the example are as follows (F, G, H are new athletes): A(181), B(169), C(187), D(172), E(163), F(191), G(189), H(182)
In the previous sorting algorithm, these sortings were all done by the coach. Now that the number of athletes has increased, the coach also wants to take the opportunity to take a break, so the coach called two assistants and asked the two assistants to sort the heights of the 8 athletes from left to right and low to high in a quick sorting way.
According to the algorithm principle of the quick sorting method, the two assistants stand on both sides of the athlete's arrangement, as shown in the figure below:
First, assistant 1 selects an athlete from the arrangement (usually selects the first athlete on the left or the middle athlete), and here selects athlete A (181). Since the sorting is from left to right and from low to high, Assistant 1 requires an athlete who is smaller in height than A(181) (the selected A(181) is used as the benchmark for comparison. All comparisons in this round are compared with the initially selected athlete A(181)):
Let’s continue to refer to the detailed diagram of the first round of quick sorting.
When the two assistants meet during the sorting and search process, the comparison of the current round is stopped and the initially selected athlete A (181) is placed in the empty space where the two assistants meet:
In Quick Sort, this round of sorting ends when two assistants meet. At this time, we found that using the position A (181) where the two athletes met as the division point, the ones on the left are athletes who are smaller than A (181), and the ones on the right are athletes who are larger than A (181). At this time, we will separate the two sorts on the left and right side of A(181). If we continue to sort the arrangements on both sides using the sorting methods of the two assistants above, then after multiple arrangements, we will finally get the sorting results we need.
The above is the entire sorting implementation process of quick sorting. Quick sorting is to use the above sorting rules to divide an arrangement into two arrangements, and the two arrangements into four arrangements until there is no arrangement to be divided, and finally we get the sorting result we need.
Now, we still program Java code to sort the heights of the above 8 athletes using quick sort:
/** * Quick sorting of the elements in the specified array from start to end* * @param array The specified array* @param start The resulting point of the array inquiry that needs to be quickly sorted* @param end The end of the array index that needs to be quickly sorted*/public static final void quickSort(int[] array, int start, int end) { // i is equivalent to the position of assistant 1, j is equivalent to the position of assistant 2 int i = start, j = end; int pivot = array[i]; // Take the first element as the reference element int emptyIndex = i; // The position index of the empty space is indicated, and the default is the position of the reference element being retrieved// If there are more than 1 elements to sort, enter quick sort (as long as i and j are different, it means that at least 2 array elements need to be sorted) while (i < j) { // Assistant 2 starts looking for elements smaller than the reference element from right to left (i < j && pivot <= array[j]) j--; if (i < j) { // If Assistant 2 finds the corresponding element before encountering Assistant 1, it gives the element to the "vacancies" of Assistant 1, j becomes an empty space array[emptyIndex] = array[emptyIndex = j]; } // Assistant 1 starts looking for elements larger than the reference element from left to right (i < j && array[i] <= pivot) i++; if (i < j) { // If assistant 1 finds the corresponding element before encountering assistant 2, it will give the element to the "vacancies" of assistant 2, and i becomes a vacant array[emptyIndex] = array[emptyIndex = i]; } } // After assistant 1 and assistant 2 encounter, the loop will stop and the initial reference value is taken to the last vacant array[emptyIndex] = pivot; // ===== This round of quick sorting is completed===== // If there are more than 2 elements on the left side of the split point i, the recursive call continues to quickly sort it if (i - start > 1) { quickSort(array, 0, i - 1); } // If there are more than 2 elements on the right side of the split point j, the recursive call continues to quickly sort it if (end - j > 1) { quickSort(array, j + 1, end); }}//Main method public static void main(String[] args) { // =====Sort from low to high using quick sort method to represent the heights of 8 athletes ===== // A(181), B(169), C(187), D(172), E(163), F(191), G(189), H(182) int[] heights = { 181, 169, 187, 172, 163, 191, 189, 182 }; // Call the quick sort method quickSort(heights, 0, heights.length - 1); // Output sorted result for (int height : heights) { System.out.println(height); }}The above Java code run results are output as follows:
163169172181182187189191
Note: Due to local thinking differences, there may be multiple variations in the above quick sorted code implementation. However, no matter what variants are, the core idea of quick sorting will not change.
Another implementation: one-way scanning
There is another one-way scan version for quick sorting array slicing. The specific step is to select the last element in the array as the slicing element, and set two pointers. The pointer i points to a position in front of the first element in the array, and j points to the first element in the array. j scans from front to right and right. When encountering a slicing element less than or equal to, add i to one, and then exchange the elements pointed to by i and j. Finally, exchange the elements at position i+1 and the slicing elements to complete the array division. The code implementation is as follows:
int partition(int[] a, int lo, int hi) { int i = lo - 1, j = lo; int v = a[hi]; while (j < hi) { if (a[j] <= v) { swap(a, ++i, j); } j++; } swap(a, i + 1, hi); return i + 1;}