Quick sorting algorithm concept
Quick sorting is generally based on recursive implementation. The idea is as follows:
1. Select an appropriate value (the ideal value is the best, but the first value in the array is generally used in the implementation), which is called "pivot".
2. Based on this value, divide the array into two parts, the smaller part on the left and the larger part on the right.
3. It is certain that after such a round, the position of this pivot must be at the final position.
4. Repeat the above process for the two subarrays until there is only one element per array.
5. Sorting is completed.
Basic implementation method:
public static void quickSort(int[] arr){ qsort(arr, 0, arr.length-1);}private static void qsort(int[] arr, int low, int high){ if (low < high){ int pivot=partition(arr, low, high); //Divide the array into two parts qsort(arr, low, pivot-1); //Sort the left subarray qsort(arr, pivot+1, high); //Sort the right subarray recursively}}private static int partition(int[] arr, int low, int high){ int pivot = arr[low]; //Pivot record while (low<high){ while (low<high && arr[high]>=pivot) --high; arr[low]=arr[high]; //Swap records smaller than the pivot to the left while (low<high && arr[low]<=pivot) ++low; arr[high] = arr[low]; //Swap records smaller than the pivot to the right end} //Scan completes, the pivot is in place arr[low] = pivot; //Return the position of the pivot return low;}Use generics to implement fast-order algorithm
Below is a QuickSort class, which contains the static function sort(), which can sort arrays of any type. If it is an array of object types, the object type must implement the Comparable interface so that the comparisonTo function can be used for comparison.
The most basic fast-row sorting algorithm was used and no optimization processing was performed.
The source code is as follows:
import java.util.LinkedList;import java.util.List;import java.util.ListIterator;import java.util.Random; public class QuickSort { @SuppressWarnings("unchecked") //Modify the above quick-row function prototype so that it can sort arrays of any object type. This function is used internally, and the external sorting function interface is sort(). The sort function requires that the object must implement the Comparable interface, which can provide compile-time type detection, see the following article. private static void quickSort(Object[] in,int begin, int end) { if( begin == end || begin == (end-1) ) return; Object p = in[begin]; int a = begin +1; int b = a; for( ; b < end; b++) { //This object type array must implement the Comparable interface so that you can use the compareTo function for comparison if( ((Comparable<Object>) in[b]).compareTo(p) < 0) { if(a == b){a++; continue;} Object temp = in[a]; in[a] = in[b]; in[b] = temp; a++; } } in[begin] = in[a-1]; in[a-1] = p; if( a-1 > begin){ quickSort(in,begin, a); } if( end-1 > a ) { quickSort(in,a, end); } return; } //Use generics to sort any object array, the object type array must implement the Comparable interface public static <T extends Comparable<? super T>> void sort(T[] input){ quickSort(input,0,input.length); } //Add the function of sorting List objects, refer to the sort() function of the Java.util.Collections class in Java public static <T extends Comparable<? super T>> void sort(List<T> list){ Object[] t = list.toArray();//Convert the list to an array quickSort(t,0,t.length); //Sort the array//After the array sorting is completed, write back to the list ListIterator<T> i = list.listIterator(); for (int j=0; j<t.length; j++) { i.next(); i.set((T)t[j]); } } //Because generics cannot be used in Java, primitive data types (int, double, byte, etc.), you can only use the function overloading mechanism to sort these primitive arrays (int[], double[], byte[], etc.). In order to share the same sorting function here, the original type (AutoBoxing, UnBoxing) mechanism is used to encapsulate it into the corresponding object type, form a new object array, sort it and then deencapsulate it. The disadvantage of this is that it requires additional conversion steps and additional space to save the encapsulated array. Another way is to copy the sort code into each overloaded function. The sort() function in the Java.util.Arrays class in the official API uses this method, which can be seen from the source code of the Arrays class. public static void sort(int[] input){ Integer[] t = new Integer[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i];//Encapsulation} quickSort(t,0,t.length);//Sorting for(int i = 0; i < input.length; i++){ input[i] = t[i];//Uncapsulation} } //Overload function of double[] array public static void sort(double[] input){ Double[] t = new Double[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quickSort(t,0,t.length); for(int i = 0; i < input.length; i++){ input[i] = t[i]; } } //Overload function of byte[] array public static void sort(byte[] input){ Byte[] t = new Byte[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quickSort(t,0,t.length); for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quickSort(t,0,t.length); for(int i = 0; i < input.length); input.length; i++){ input[i] = t[i]; } } //Short[] overload function public static void sort(short[] input){ Short[] t = new Short[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quickSort(t,0,t.length); for(int i = 0; i < input.length; i++){ input[i] = t[i]; } } //Short[] overload function public static void sort(char[] input){ Character[] t = new Character[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quickSort(t,0,t.length); for(int i = 0; i < input.length; i++){ input[i] = t[i]; } } //Overload function of float[] array public static void sort(float[] input){ Float[] t = new Float[input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i]; } quickSort(t,0,t.length); for(int i = 0; i < input.length; i++){ input[i] = t[i]; } } //The main function for testing public static void main(String[] args) { //Produce an int[] array composed of random numbers to test int LEN = 10; int[] input = new int[LEN]; Random r = new Random(); System.out.print("int[] before sorting: "); for(int i = 0; i < input.length; i++) { input[i] = r.nextInt(10*LEN); System.out.print(input[i] + " "); } System.out.println(); System.out.print("int[] after sorting: "); sort(input); for(int i : input) { System.out.print(i + " "); } System.out.println(); // Generate an array of strings to test String[] s = new String[]{"b","a","e","d","f","c"}; System.out.print("String[] before sorting: "); for(int i = 0; i < s.length; i++) { System.out.print(s[i] + " "); } System.out.println(); System.out.print("String[] after sorting: "); sort(s); for(int i = 0; i < s.length; i++) { System.out.print(s[i] + " "); } System.out.println(); // Generate a list of strings to test List<String> l = new LinkedList<String>(); s = new String[]{"b","a","e","d","f","c"}; System.out.print("LinkedList<String> before sorting: "); for (int j=0; j<s.length; j++) { l.add(s[j]); System.out.print(s[j] + " "); } System.out.println(); sort(l); System.out.print("LinkedList<String> after sorting: "); for (String ts : l) { System.out.print(ts + " "); } System.out.println(); }}Run the main function test, and from the output, you can see that the QuickSort class is working normally:
int[] before sorting: 65 48 92 26 3 8 59 21 16 45int[] after sorting: 3 8 16 21 26 45 48 59 65 92String[] before sorting: baedfc String[] after sorting: abcdef LinkedList<String> before sorting: baedfc LinkedList<String> after sorting: abcdef