快速排序大概是最常被拿來當排序預設值的演算法,JDK 裡的 Arrays.sort 對基本型別陣列採用的就是這套思路(現代版本是雙軸快排)。它之所以快,關鍵在於「幾乎不需要搬動資料」,全部都在原陣列上原地交換完成。
Divide(分割):挑一個基準元 pivot,這裡取陣列第一個元素,然後做分區操作,讓左半邊都小於等於 pivot、右半邊都大於等於 pivot。
Conquer(解決):對左右兩個子陣列遞迴呼叫同一套分割流程。
Combine(合併):快排屬於原地排序(in-place sort),分割完成時資料已經各就各位,因此完全不需要合併步驟。這也是它比合併排序省記憶體的原因。
以《算法導論》的經典示意為例,初始化時取 pivot = 2(首元素),令 i = 1、j = i + 1 = 2(下標從 1 起算)。此時維持的循環不變式是:2 到 i 之間的元素都小於等於 pivot,i + 1 到 j 之間的元素都大於等於 pivot。
接著 j 從 2 掃到 n:若 a[j] 大於等於 pivot 就繼續往右;若小於 pivot,就把 a[j] 與 a[i+1] 交換,並將 i 加一。這樣不變式在每一步都成立。掃描結束後,還要把 a[i] 與首元素交換,把 pivot 放到它最終的正確位置。

聰明的讀者可能會想到另一種更直觀的做法:另開一個同大小陣列,比 pivot 小的丟左邊、大的丟右邊。時間複雜度同樣是 Θ(n),但空間複雜度直接翻倍,這正是原地排序的價值所在。
public class QuickSort {
private static void quickSort(int[] array, int start, int end) {
if (start < end) {
int key = array[start]; // 基準元
int i = start, j;
for (j = start + 1; j <= end; j++) {
if (array[j] < key) { // 比基準元小,換到左側並前移 i
int temp = array[j];
array[j] = array[i + 1];
array[i + 1] = temp;
i++;
}
}
array[start] = array[i]; // 基準元歸位
array[i] = key;
quickSort(array, start, i - 1); // 遞迴處理左右子區間
quickSort(array, i + 1, end);
}
}
public static void main(String[] args) {
int[] array = new int[]{11, 213, 134, 44, 77, 78, 23, 43};
quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.println((i + 1) + "th:" + array[i]);
}
}
}
平均時間複雜度 O(n log n),最壞情況 O(n²),多出現在陣列已排序或接近排序、而 pivot 又固定取首/尾元素的時候。實務上的解法是隨機選 pivot 或改用三數取中,並在子區間夠小時(例如長度小於 10)遞迴改用插入排序,這正是多數標準函式庫的實作策略。