快速排序由 C. A. R. Hoare 在 1960 年提出。
随機化快速排序基本思想：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。
快速排序是一種比較快速的排序算法，它的平均運作時間是 O(nlogn)，之是以特别快是由于非常精練和高度優化的内部循環，最壞的情形性能為 O(n^2)。像歸并一樣，快速排序也是一種分治的遞歸算法。從空間性能上看，快速排序隻需要一個元素的輔助空間，但快速排序需要一個棧空間來實作遞歸，空間複雜度也為O(logn)。
在一個數組中選擇一個基點，比如第一個位置的 4，然後把4挪到正确位置，使得之前的子數組中資料小于 4，之後的子數組中資料大于 4，然後逐漸遞歸下去完成整個排序。
如何和把標明的基點資料挪到正确位置上，這是快速排序的核心，我們稱為 Partition。
過程如下所示，其中 i 為目前周遊比較的元素位置：
這個 partition 過程用代碼表示為：
...
private static int partition(Comparable[] arr, int l, int r){
Comparable v = arr[l];
int j = l;
for( int i = l + 1 ; i <= r ; i ++ )
if( arr[i].compareTo(v) < 0 ){
j ++;
//數組元素位置交換
swap(arr, j, i);
}
swap(arr, l, j);
return j;
}
...
如果是對近乎有序的數組進行快速排序，每次 partition 分區後子數組大小極不平衡，容易退化成 O(n^2) 的時間複雜度算法。我們需要對上述代碼進行優化，随機選擇一個基點做為比較，稱為随機化快速排序算法。隻需要在上述代碼前加上下面一行，随機選擇數組中一資料和基點資料進行交換。
源碼包下載下傳：Download
package runoob;
/**
* 随機化快速排序
*/
public class QuickSort {
// 對arr[l...r]部分進行partition操作
// 傳回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
private static int partition(Comparable[] arr, int l, int r){
// 随機在arr[l...r]的範圍中, 選擇一個數值作為标定點pivot
swap( arr, l , (int)(Math.random()*(r-l+1))+l );
Comparable v = arr[l];
// arr[l+1...j] < v ; arr[j+1...i) > v
int j = l;
for( int i = l + 1 ; i <= r ; i ++ )
if( arr[i].compareTo(v) < 0 ){
j ++;
swap(arr, j, i);
}
swap(arr, l, j);
return j;
}
// 遞歸使用快速排序,對arr[l...r]的範圍進行排序
private static void sort(Comparable[] arr, int l, int r){
if (l >= r) {
return;
int p = partition(arr, l, r);
sort(arr, l, p-1 );
sort(arr, p+1, r);
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
// 測試 QuickSort
public static void main(String[] args) {
// Quick Sort也是一個O(nlogn)複雜度的算法
// 可以在1秒之内輕松處理100萬數量級的資料
int N = 1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
SortTestHelper.printArray(arr);