快速排序算法概念
快速排序一般基於遞歸實現。其思路是這樣的：
1.選定一個合適的值（理想情況中值最好，但實現中一般使用數組第一個值）,稱為“樞軸”(pivot)。
2.基於這個值，將數組分為兩部分，較小的分在左邊，較大的分在右邊。
3.可以肯定，如此一輪下來，這個樞軸的位置一定在最終位置上。
4.對兩個子數組分別重複上述過程，直到每個數組只有一個元素。
5.排序完成。
基本實現方式：
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;}使用泛型實現快排算法
下面設計一個QuickSort類，包含了靜態函數sort()，可以對任意類型數組進行排序。如果為對像類型數組，則該對像類型必須實現Comparable接口，這樣才能使用compareTo函數進行比較。
使用了最基本的快排算法，沒有進行優化處理。
源代碼如下：
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(); }}運行main函數測試，從輸出可以看出QuickSort類工作正常：
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