Detail the method of using generics to implement quick sort algorithm in Java
- 2020-05-09 18:41:28
- OfStack
Quicksort algorithm concept
Quicksort 1 is generally based on a recursive implementation. The idea goes like this:
1. Select an appropriate value (ideally best, but implementation 1 USES the first value of the array), called "pivot" (pivot).
2. Based on this value, divide the array into two parts, with the smaller part on the left and the larger part on the right.
3. It is certain that the pivot position 1 is fixed at the final position when the rotation is down.
4. Repeat the procedure for the two subarrays until each has only one element.
5. Sorting is complete.
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); // Recursively sort the left subarray
qsort(arr, pivot+1, high); // Recursively sort the right subarray
}
}
private static int partition(int[] arr, int low, int high){
int pivot = arr[low]; // Pivot records
while (low<high){
while (low<high && arr[high]>=pivot) --high;
arr[low]=arr[high]; // Swap notes smaller than the pivot to the left end
while (low<high && arr[low]<=pivot) ++low;
arr[high] = arr[low]; // Swap records smaller than the pivot to the right
}
// Scan complete, pivot in place
arr[low] = pivot;
// It returns the position of the pivot
return low;
}
Using generics to implement the quicksort algorithm
Let's design an QuickSort class that contains the static function sort(), which sorts an array of any type. If it is an array of object types, the object type must implement the Comparable interface so that it can be compared using the compareTo function.
The most basic quicksort algorithm is used without optimization.
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 quicksort function prototype above to sort any array of object types. This function is for internal use and the external sorting function interface is sort() . sort The function requires that the object be implemented Comparable Interface that provides compile-time type detection, see below.
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++) {
// The object type array must be implemented Comparable Interface so you can use it compareTo Function 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;
}
// With generics, sort any array of object types that must be implemented Comparable interface
public static <T extends Comparable<? super T>> void sort(T[] input){
quickSort(input,0,input.length);
}
// To add to List Object to sort the function of the reference Java In the Java.util.Collections Of the class sort() function
public static <T extends Comparable<? super T>> void sort(List<T> list){
Object[] t = list.toArray();// Converts a list to an array
quickSort(t,0,t.length); // Sort the array
// After sorting the array, write it back into the list
ListIterator<T> i = list.listIterator();
for (int j=0; j<t.length; j++) {
i.next();
i.set((T)t[j]);
}
}
// Due to the Java In the original data type ( int , double , byte Generics cannot be used, so you can only use the function overloading mechanism to implement an array of these primitive types ( int[] , double[] , byte[] Sort, etc. It's for sharing 1 Sort functions, using the primitive type (AutoBoxing . UnBoxing) The mechanism encapsulates it as a corresponding object type, forms a new array of objects, sorts them and unseals them, which requires extra conversion steps and extra space to save the encapsulated array. On the other 1 The way to do this is to copy the sort code into the various overloaded functions, officially API In the Java.util.Arrays In this class sort() This is the way the function works Arrays Class source code see.
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);// The sorting
for(int i = 0; i < input.length; i++){
input[i] = t[i];// decapsulation
}
}
//double[] Array overload function
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];
}
}
//byte[] Array overload function
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++){
input[i] = t[i];
}
}
//short[] Array 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];
}
}
//char[] Array 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];
}
}
//float[] Array overload function
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 test of the main function
public static void main(String[] args) {
// production 1 It's made up of random Numbers int[] Array for testing
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 1 An array of strings for testing
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 1 A list of strings for testing
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 it can be seen from the output that the QuickSort class works normally:
int[] before sorting: 65 48 92 26 3 8 59 21 16 45
int[] after sorting: 3 8 16 21 26 45 48 59 65 92
String[] before sorting: b a e d f c
String[] after sorting: a b c d e f
LinkedList<String> before sorting: b a e d f c
LinkedList<String> after sorting: a b c d e f