Normal quick sort
Find a base value base, and then sort it in one trip so that the numbers on the left of the base are smaller than base, and the numbers on the right of the base are greater than or equal to base. Then divide it into two subarrays sorting. Recursive like this.
public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1);}public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {if (left >= right) return;int p = partition(arr, left, right);sort(arr, left, p - 1);sort(arr, p + 1, right);}private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {T base = arr[left];int j = left;for (int i = left + 1; i <= right; i++) {if (base.compareTo(arr[i]) > 0) {j++;swap(arr, j, i);}}swap(arr, left, j);return j;//Return the lower corner of the base value after lying sorting}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}Quick sort optimization: Randomly select base value base
When the array is almost ordered, the fast-order performance is poor (because after each order, the recursive size of the left and right subs is very different, and the larger part is likely to reach O(n^2) in the end).
Solution: The reference value is selected randomly, rather than taking the first number every time. This will not be disturbed by "almost ordered arrays". But the sorting performance of "almost out-of-order arrays" may drop slightly, at least there is more of the part that is swapped before sorting. This swapping is meaningless in out-of-order... There are many "luck" components...
public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1);}public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {if (left >= right) return;int p = partition(arr, left, right);sort(arr, left, p - 1);sort(arr, p + 1, right);}private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {//Before sorting, let the reference value be exchanged with a random number. In this way, the reference value is random. //It will not cause the recursive scale of the left and right sides to be inconsistent when the array is relatively ordered, resulting in the worst time complexity swap(arr,left,(int)(Math.random()*(right - left + 1)+left));T base = arr[left];int j = left;for (int i = left + 1; i <= right; i++) {if (base.compareTo(arr[i]) > 0) {j++;swap(arr, j, i);}}swap(arr, left, j);return j;//Return the lower corner of the reference value after a lying sort}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}Quick sorting continues to optimize: Use insert sorting in conjunction
Quick-ordering is to continuously reduce the scale of the problem to solve sub-problems and requires continuous recursion. However, recursion is small enough, and if this unstable + recursion continues to be executed, the efficiency may not be very good.
So when the problem is small and nearly orderly, the insertion sorting performs well. You can often see such comments in Arrays.sort() that comes with Java: "Use insertion sort on tiny arrays", "Insertion sort on smallest arrays"
public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1, 16);}/** * @param arr Array to be sorted* @param left Close left* @param right Close right* @param k When fast sort recurses to the scale of the subproblem <= k, insert sort optimization is used * @param <T> generic, type to be sorted can be compared*/public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {// Scale hours are sorted by insertion if (right - left <= k) {insertionSort(arr, left, right);return;}int p = partition(arr, left, right);sort(arr, left, p - 1, k);sort(arr, p + 1, right, k);}public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {T cur = arr[i];int j = i - 1;for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {arr[j + 1] = arr[j];}arr[j + 1] = cur;}}private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {//Before sorting, let the reference value exchange with a random number. In this way, the reference value is random. //It will not cause the recursive scale of the left and right sides to be inconsistent when the array is relatively order, resulting in the worst time complexity swap(arr, left, (int) (Math.random() * (right - left + 1) + left));T base = arr[left];int j = left;for (int i = left + 1; i <= right; i++) {if (base.compareTo(arr[i]) > 0) {j++;swap(arr, j, i);}}swap(arr, left, j);return j;//Return the lower corner of the base value after lying sorting}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}Quick sorting continues to optimize: Two-way fast sorting
In the initial normal quick sorting, it is said that the base value on the left side of the base is smaller than the base, while the base on the right side is greater than or equal to the base. These equal to base will gather to the right (or slightly change the size relationship will gather to the left). Anyway, it will gather aside. When many numbers are repeated in the array, it will lead to a huge difference in the size of the two subs. At this time, I want to assign the numbers equal to the base to both sides of the base, instead of getting them together.
(Note: When testing the code, it is best to look away the part of the insertion sort and look like in my code below... Otherwise, when the data volume is less than k=16, the insertion sort is performed...)
public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1, 16);}/** * @param arr Array to be sorted* @param left Close left* @param right Close right* @param k When fast sort recurses to the scale of the subproblem <= k, insert sort optimization is used * @param <T> generic, type to be sorted can be compared*/public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {// Insertionsort(arr, left, right);// return;// }if (left >= right) return;int p = partition(arr, left, right);sort(arr, left, right);sort(arr, left, p - 1, k);sort(arr, p + 1, right, k);}public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {T cur = arr[i];int j = i - 1;for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {arr[j + 1] = arr[j];}arr[j + 1] = cur;}}private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {//Before sorting, let the reference value exchange with a random number. In this way, the reference value is random. //It will not cause the recursive scales of the left and right sides to be inconsistent when the array is relatively ordered, resulting in the worst time complexity swap(arr, left, (int) (Math.random() * (right - left + 1) + left));T base = arr[left];//Basic value, throw this reference value every time, see it as the sort of [left+1......right] left closed right closed interval int i = left + 1;//For the [left+1.........right] interval mentioned in the previous line, i means [left+1......i) left closed right open interval is less than or equal to base. int j = right;//For the [left+1......right] interval mentioned in the previous two lines, j means that the values of (j......right] left open and right closed intervals are greater than or equal to base. while (true) {//Scan from left to right, scan out the first element larger than base, and then i stop there. while (i <= right && arr[i].compareTo(base) < 0) i++;//Scan from right to left, scan out the first element smaller than base, and then j stops there. while (j >= left && arr[j].compareTo(base) > 0) j--;if (i > j) {//Although it is i>j, it is actually break ending with j=i-1;}swap(arr, i++, j--);}swap(arr, left, j);return j;//Return the lower corner of the reference value after lying sorting}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}Continue to optimize the fast sorting: two fast sorting does not require swap, use exchange
When the above two paths find values greater than base and values less than base, they use the swap() method to exchange. The two-digit exchange involves the operation of the third variable temp, with more read and write operations. Next, use the direct assignment method to place the less than on the right and the greater than on the left. When i and j meet, that position is where the base should be placed. This trip is completed. Just recurse.
public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1, 16);}/** * @param arr Array to be sorted* @param left Close left* @param right Close right* @param k When fast sort recurses to the scale of the subproblem <= k, insert sort optimization is used * @param <T> generic, type to be sorted can be compared*/public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {// Insertionsort(arr, left, right);// return;// }if (left >= right) return;int p = partition(arr, left, right);sort(arr, left, right);sort(arr, left, p - 1, k);sort(arr, p + 1, right, k);}public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {T cur = arr[i];int j = i - 1;for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {arr[j + 1] = arr[j];}arr[j + 1] = cur;}}private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {//Before sorting, let the reference value exchange with a random number. In this way, the reference value is random. //It will not cause the recursive scales of the left and right sides to be inconsistent when the array is relatively ordered, resulting in the worst time complexity swap(arr, left, (int) (Math.random() * (right - left + 1) + left));T base = arr[left];//Basic value, throw this reference value every time, see it as the sort of [left+1......right] left-closed right-closed interval int i = left;//For the [left+1.........right] interval mentioned in the previous line, i means [left+1......i) left-closed right-closed interval values are less than or equal to base. int j = right;//For the [left+1......right] interval mentioned in the previous two lines, j means that the values of (j......right] left-open and right-closed intervals are greater than or equal to base. while (i < j) {//Scan from right to left, scan out the first element smaller than base, and then j stops there. while (j > i && arr[j].compareTo(base) > 0) j--;arr[i] = arr[j];//Scan from left to right, scan out the first element larger than base, and then i stops there. while (i < j && arr[i].compareTo(base) < 0) i++;arr[j] = arr[i];}arr[j] = base;return j;//Return the lower corner of the reference value after a lying sorting}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}Quick sorting continues to optimize: When a large amount of data and many repetitions are used, use three-way fast sorting
Divide the array into three paths. The first path is smaller than the base, the second path is equal to the base, and the third path is greater than the base.
Use a pointer to scan from front to back, if:
1. The number pointed to by cur is less than base, then: exchange the values of arr[cur] and arr[i], and then i++, cur++.
2. The number pointed to by cur is equal to base, then: cur++
3. The number pointed to by cur is greater than base, then: exchange the values of arr[cur] and arr[j], and then j--.
When cur>j, it means that all three paths have been completed.
public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1, 16);}/** * @param arr Array to be sorted* @param left Close left* @param right Close right* @param k When fast sort recurses to the scale of the subproblem <= k, insert sort optimization is used * @param <T> generic, type to be sorted can be compared*/public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {// Insertionsort(arr, left, right);// return;// }if (left >= right) return;int[] ret = partition(arr, left, right);sort(arr, left, ret[0], k);sort(arr, ret[1], right, k);}public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {T cur = arr[i];int j = i - 1;for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {arr[j + 1] = arr[j];}arr[j + 1] = cur;}}/** * @param arr Array to be sorted* @param left The left boundary of the array to be sorted* @param right The right boundary of the array to be sorted* @param <T> Generics* @return */private static <T extends Comparable<? super T>> int[] partition(T[] arr, int left, int right) {//Before sorting, let the reference value be exchanged with a random number. In this way, the reference value is random. //It will not cause the recursive scales on the left and right sides to be inconsistent when the array is relatively order, resulting in the worst time complexity swap(arr, left, (int) (Math.random() * (right - left + 1) + left));T base = arr[left];//Basic value, throw this reference value every time, see it as the sort of [left+1......right] left closed right closed interval // Three fast rows are divided into the following three channels (intervals) int i = left;// left indicates that [lleft...left) The numbers in the left closed right open interval are smaller than base int j = right;// left indicates that (rright...right] The numbers in the left and right closed intervals are larger than base int cur = i;// Use cur to traverse the array. [left...cur) The numbers in the left and right closed intervals are equal to basewhile (cur <= j) {if (arr[cur].compareTo(base) == 0) {cur++;} else if (arr[cur].compareTo(base) < 0) {swap(arr, cur++, i++);} else {swap(arr, cur, j--);}} return new int[]{i - 1, j + 1};//[i...j] are all equal to base, and the sub-problem only needs to solve the left and right of i and j } public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}Summarize
The above is all the detailed explanation of Java programming implementation quick sorting and optimization code. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!