快捷導(dǎo)航

詳解Java中使用泛型實(shí)現(xiàn)快速排序算法的方法

更新時(shí)間：2016年05月04日 15:52:21 作者：飛翔的貓咪

這篇文章主要介紹了Java中使用泛型實(shí)現(xiàn)快速排序算法的方法,快速排序的平均時(shí)間復(fù)雜度為(n\log n),文中的方法立足于基礎(chǔ)而并沒(méi)有考慮優(yōu)化處理,需要的朋友可以參考下

快速排序算法概念
快速排序一般基于遞歸實(shí)現(xiàn)。其思路是這樣的：
1.選定一個(gè)合適的值（理想情況中值最好，但實(shí)現(xiàn)中一般使用數(shù)組第一個(gè)值）,稱為“樞軸”(pivot)。
2.基于這個(gè)值，將數(shù)組分為兩部分，較小的分在左邊，較大的分在右邊。
3.可以肯定，如此一輪下來(lái)，這個(gè)樞軸的位置一定在最終位置上。
4.對(duì)兩個(gè)子數(shù)組分別重復(fù)上述過(guò)程，直到每個(gè)數(shù)組只有一個(gè)元素。
5.排序完成。

基本實(shí)現(xiàn)方式：

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);    //將數(shù)組分為兩部分
    qsort(arr, low, pivot-1);          //遞歸排序左子數(shù)組
    qsort(arr, pivot+1, high);         //遞歸排序右子數(shù)組
  }
}
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;
}

使用泛型實(shí)現(xiàn)快排算法

下面設(shè)計(jì)一個(gè)QuickSort類，包含了靜態(tài)函數(shù)sort()，可以對(duì)任意類型數(shù)組進(jìn)行排序。如果為對(duì)象類型數(shù)組，則該對(duì)象類型必須實(shí)現(xiàn)Comparable接口，這樣才能使用compareTo函數(shù)進(jìn)行比較。

使用了最基本的快排算法，沒(méi)有進(jìn)行優(yōu)化處理。

源代碼如下：

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
 
public class QuickSort {
  @SuppressWarnings("unchecked")
  //對(duì)上述快排函數(shù)原型修改，使其可以對(duì)任意對(duì)象類型數(shù)組進(jìn)行排序。這個(gè)函數(shù)為內(nèi)部使用，外部排序函數(shù)接口為sort()，sort函數(shù)要求對(duì)象必須實(shí)現(xiàn)Comparable接口，可以提供編譯時(shí)類型檢測(cè)，見(jiàn)后文。
  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++) {
      //該對(duì)象類型數(shù)組必須實(shí)現(xiàn)Comparable接口，這樣才能使用compareTo函數(shù)進(jìn)行比較
      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;
  }
   
  //使用泛型，對(duì)任意對(duì)象數(shù)組排序，該對(duì)象類型數(shù)組必須實(shí)現(xiàn)Comparable接口
  public static <T extends Comparable<? super T>> void sort(T[] input){
    quickSort(input,0,input.length);
  }
   
  //添加對(duì)List對(duì)象進(jìn)行排序的功能，參考了Java中的Java.util.Collections類的sort()函數(shù)
  public static <T extends Comparable<? super T>> void sort(List<T> list){
    Object[] t = list.toArray();//將列表轉(zhuǎn)換為數(shù)組
    quickSort(t,0,t.length); //對(duì)數(shù)組進(jìn)行排序
    //數(shù)組排序完成后再寫回到列表中
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<t.length; j++) {
      i.next();
      i.set((T)t[j]);
    }
  }
   
  //由于Java中原始數(shù)據(jù)類型（int、double、byte等）無(wú)法使用泛型，所以只能使用函數(shù)重載機(jī)制實(shí)現(xiàn)對(duì)這些原始類型數(shù)組（int[]、double[]、byte[]等）的排序。這里為了共用同一個(gè)排序函數(shù)，利用原始類型的(AutoBoxing，UnBoxing)機(jī)制將其封裝為對(duì)應(yīng)對(duì)象類型，組成新的對(duì)象數(shù)組，排序后再解封裝，這樣的缺點(diǎn)是需要額外的轉(zhuǎn)換步驟、額外的空間保存封裝后的數(shù)組。另一種方式是將排序代碼復(fù)制到各個(gè)重載函數(shù)中，官方API中的Java.util.Arrays這個(gè)類中的sort()函數(shù)就是使用這種方法，可以從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[]數(shù)組的重載函數(shù)
  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[]數(shù)組的重載函數(shù)
  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[]數(shù)組的重載函數(shù)
  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[]數(shù)組的重載函數(shù)
  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[]數(shù)組的重載函數(shù)
  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];
    }
  }
   
  //測(cè)試用的main函數(shù)
   public static void main(String[] args) {
    //生產(chǎn)一個(gè)隨機(jī)數(shù)組成的int[]數(shù)組，用來(lái)測(cè)試
    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();
 
    //生成一個(gè)字符串?dāng)?shù)組，用來(lái)測(cè)試
    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();
     
    //生成一個(gè)字符串列表，用來(lái)測(cè)試
    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();
  }
}

運(yùn)行main函數(shù)測(cè)試，從輸出可以看出QuickSort類工作正常：

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

您可能感興趣的文章: