快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），一種[排序算法]，最早由[東尼 · 霍爾]提出。在平均狀況下，排序n個項目要[Ο](n log n) 次比較。在最壞狀況下則需要Ο(n^2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：
- 從數列中挑出一個元素，稱為 "基準"（pivot），
- 重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（相同的數可以到任一邊）。在這個分區(qū)結束之后，該基準就處于數列的中間位置。這個稱為分區(qū)（partition）操作。
- 遞歸地（recursively）把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個算法一定會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
public class QuickSort {
public static void sort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
/**
* 遞歸劃分子序列
*
* @param arr
* @param left
* @param right
*/
public static void quickSort(int[] arr, int left, int right) {
System.out.println("quickSort：" + print(arr));
if (left >= right) {
return;
}
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos - 1);
quickSort(arr, pivotPos + 1, right);
}
/**
* 稍優(yōu)的劃分邏輯
* 一次劃分流程
*
* 按照把左邊第一個數字作為基準數的話，邏輯如下：
* 1. 右指針從右往左找到比基準數小的數字，找到時指針停止移動，且給左指針數字賦值為右指針對應的數字
* 2. 左指針從左往右找到比基準數大的數字，找到時指針停止移動，且給右指針數字賦值為左指針對應的數字
* 3. 交換相遇時的數字和基準數
* 4. 此時基準數左邊都是比基準數小的數字，基準數右邊都是比基準數大的數字
* 5. 此時一輪劃分執(zhí)行完畢
*
* @param arr
* @param left 左指針
* @param right 右指針
* @return
*/
public static int partition(int[] arr, int left, int right) {
int pivotKey = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivotKey) {
right--;
}
arr[left] = arr[right]; //把小的數字移動到左邊
System.out.println(print(arr));
while (left < right && arr[left] <= pivotKey) {
left++;
}
arr[right] = arr[left]; //把大的移動到右邊
System.out.println(print(arr));
}
arr[left] = pivotKey; //最后把pivot賦值到中間
System.out.println(print(arr));
return left;
}
/**
* 代碼中基準數已經在 pivotKey 中保存了，所以不需要每次交換都設置一個 temp 變量，
* 在交換左右指針的時候只需要先后覆蓋就可以了。
* 這樣既能減少空間的使用還能降低賦值運算的次數
*
* 一次劃分流程
*
* 按照把左邊第一個數字作為基準數的話，邏輯如下：
* 1. 右指針從右往左找到比基準數小的數字，找到時指針停止移動
* 2. 左指針從左往右找到比基準數大的數字，找到時指針停止移動
* 3. 交換這兩個數字
* 4. 重復步驟1和步驟2，如果兩者相遇時，則停止移動
* 5. 交換相遇時的數字和基準數
* 6. 此時基準數左邊都是比基準數小的數字，基準數右邊都是比基準數大的數字
* 7. 此時一輪劃分執(zhí)行完畢
*
* @param arr
* @param left 左指針
* @param right 右指針
* @return
*/
public static int partitionOld(int[] arr, int left, int right) {
int pivotKey = arr[left];
int initLeft = left;
while (left < right) {
while (left < right && arr[right] >= pivotKey) {
right--;
}
while (left < right && arr[left] <= pivotKey) {
left++;
}
swap(arr, left, right);
System.out.println(print(arr));
}
swap(arr, initLeft, left);
System.out.println(print(arr));
return left;
}
public static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
