Detailed explanation of how to use generics to implement quick sorting algorithm in Java

Quick sort algorithm concept
Quick sort is generally based on recursive implementation. The idea is as follows:
1. Select a suitable value (ideally the median value is the best, but in implementation the first value of the array is generally used), which is called the "pivot".
2. Based on this value, divide the array into two parts, with the smaller one on the left and the larger one on the right.
3. It is certain that after this round, the position of this pivot must be at the final position.
4. Repeat the above process for the two sub-arrays until each array has only one element.
5. Sorting 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);    //将数组分为两部分
    qsort(arr, low, pivot-1);          //递归排序左子数组
    qsort(arr, pivot+1, high);         //递归排序右子数组
  }
}
private static int partition(int[] arr, int low, int high){
  int pivot = arr[low];   //枢轴记录
  while (low<high){
    while (low<high && arr[high]>=pivot) --high;
    arr[low]=arr[high];       //交换比枢轴小的记录到左端
    while (low<high && arr[low]<=pivot) ++low;
    arr[high] = arr[low];      //交换比枢轴小的记录到右端
  }
  //扫描完成，枢轴到位
  arr[low] = pivot;
  //返回的是枢轴的位置
  return low;
}

Use generics to implement the quick sort algorithm

The following design a QuickSort class, including The static function sort() can sort arrays of any type. If it is an array of object type, the object type must implement the Comparable interface so that the compareTo function can be used for comparison.

The most basic quick sort 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")
  //对上述快排函数原型修改，使其可以对任意对象类型数组进行排序。这个函数为内部使用，外部排序函数接口为sort()，sort函数要求对象必须实现Comparable接口，可以提供编译时类型检测，见后文。
  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++) {
      //该对象类型数组必须实现Comparable接口，这样才能使用compareTo函数进行比较
      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;
  }
    
  //使用泛型，对任意对象数组排序，该对象类型数组必须实现Comparable接口
  public static <T extends Comparable<? super T>> void sort(T[] input){
    quickSort(input,0,input.length);
  }
    
  //添加对List对象进行排序的功能，参考了Java中的Java.util.Collections类的sort()函数
  public static <T extends Comparable<? super T>> void sort(List<T> list){
    Object[] t = list.toArray();//将列表转换为数组
    quickSort(t,0,t.length); //对数组进行排序
    //数组排序完成后再写回到列表中
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<t.length; j++) {
      i.next();
      i.set((T)t[j]);
    }
  }
    
  //由于Java中原始数据类型（int、double、byte等）无法使用泛型，所以只能使用函数重载机制实现对这些原始类型数组（int[]、double[]、byte[]等）的排序。这里为了共用同一个排序函数，利用原始类型的(AutoBoxing，UnBoxing)机制将其封装为对应对象类型，组成新的对象数组，排序后再解封装，这样的缺点是需要额外的转换步骤、额外的空间保存封装后的数组。另一种方式是将排序代码复制到各个重载函数中，官方API中的Java.util.Arrays这个类中的sort()函数就是使用这种方法，可以从Arrays类的源代码看出。
  public static void sort(int[] input){
    Integer[] t = new Integer[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];//解封装
    }
  }
  //double[]数组的重载函数
  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[]数组的重载函数
  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[]数组的重载函数
  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[]数组的重载函数
  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[]数组的重载函数
  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];
    }
  }
    
  //测试用的main函数
   public static void main(String[] args) {
    //生产一个随机数组成的int[]数组，用来测试
    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();
  
    //生成一个字符串数组，用来测试
    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();
      
    //生成一个字符串列表，用来测试
    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. 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 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

More details in Java For related articles on how to implement quick sorting algorithm using generics, please pay attention to the PHP Chinese website!