Overview
Quick sorting is a sorting algorithm developed by Tony Hall. In the average situation, the order of n items requires Ο(nlogn) comparison. In fact, quick sorting is usually significantly faster than other Ο(nlogn) algorithms, because its inner loop can be implemented efficiently on most architectures, and in most real-world data, it can determine the choice of design and reduce the possibility of quadratic terms that require time.
Quick sorting, divide the records to be sorted into two independent parts through one order, where the keywords of some records are smaller than the keywords of the other part, and then the two records are continued to be sorted separately to achieve the purpose of ordering the entire sequence.
Image illustration:
step
When selecting a benchmark element, the first element or the last element is usually selected to divide the records to be sorted into two independent parts through a one-sortment, where the element values of some records are smaller than the benchmark element values. The elements recorded in the other part are larger than the reference value. At this time, the reference elements are in the correct position after they are sorted, and then the two parts of the records are continued to be sorted in the same way until the entire sequence is ordered.
Example
Raw data:
3 5 2 6 2
Select 3 as the benchmark
The first round
From right to left to find something smaller than 3, 2 matches, and adjust 2 and 3 2 5 2 6 3 once, and the direction of the search is reversed, from left to right to find something larger than 3, 5 matches, and adjust 2 3 2 6 5 Then from right to left to find something smaller than 3, 2 matches, and adjust 2 2 3 6 5 One round ends
Round 2
The same method as above is performed for [2 2], and 2 2 3 6 5
The third round
The same method as above is performed for [6 5], and 2 2 3 5 6
Final result
2 2 3 5 6
Code Implementation (Java)
package com.coder4j.main.arithmetic.sorting;public class Quick { private static int mark = 0; /** * Auxiliary exchange method* * @param array * @param a * @param b */ private static void swap(int[] array, int a, int b) { if (a != b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; // Find the matching, switch System.out.println("Shift" + array[a] + "and" + array[b] + ",get"); for (int i : array) { System.out.print(i + " "); } System.out.println(); } } /** * New round of separation* * @param array * @param low * @param high * @return */ private static int partition(int array[], int low, int high) { int base = array[low]; mark++; System.out.println("Throwth in progress" + mark + "wheel separation, area: " + low + "-" + high); while (low < high) { while (low < high && array[high] >= base) { high--; System.out.println("From right to left to find the ratio" + base + "small, pointer change: " + low + "-" + high); } swap(array, low, high); while (low < high && array[low] <= base) { low++; System.out.println("From left to right to find the ratio" + base + "large, pointer change: " + low + "-" + high); } swap(array, low, high); } return low; } /** * Quick sorting of the array, call recursively * * @param array * @param low * @param height * @return */ private static int[] quickSort(int[] array, int low, int height) { if (low < height) { int division = partition(array, low, height); quickSort(array, low, division - 1); quickSort(array, division + 1, height); } return array; } /** * Quick sort* * @param array * @return */ public static int[] sort(int[] array) { return quickSort(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = { 3, 5, 2, 6, 2 }; int[] sorted = sort(array); System.out.println("final result"); for (int i : sorted) { System.out.print(i + " "); } }}Test output results:
Select all and put it in the notes. The first round of separation is being performed. Area: 0-4. The second round of adjustments are 2 and 3. The second round of separation is 2 5 2 6 3. The second round of separation is 3 and 5. The second round of separation is 2 3 2 6 5. The second round of separation is 3 and 5. The second round of separation is 2 and 3. The second round of separation is 2 and 3. The second round of separation is 2 and 3. The second round of separation is 2 and 3. The second round of separation is 2 and 3. The second round of separation is 2 and 3. The second round of separation is 2 and 3. The second round of separation is 2 and 3. The second round of separation is 2 and 2 are 3. 6. The third round of separation is 2 are 2 and 3 are 6. The second round of separation is 2 are 2 and 3 are 6. The last round of separation is 2 are 2 and 3 are 6. The last round of separation is 2 are 2 and 3 are 5. The last round of separation is 2 are 2 and 3 are 5. The last round of separation is 2 are 2 and 3 are 5. The last result is 2 are 2 and 3 are 5. 6. The last result is 2 2 3 5. 6.
After testing, it is consistent with the results in the example.