快速排序(Quick Sort)因為高效而被廣泛使用,Sun 的 JDK 中 Arrays.sort 對基本型別陣列採用的正是快排。它體現了經典的分治思想(divide and conquer)。
Divide(分割):選取一個基元 X(通常取陣列第一個元素),透過分區操作(partitioning)把陣列切成兩半:左半部分小於等於 X,右半部分大於等於 X。
Conquer(求解):對左右兩個子陣列遞歸地呼叫 Divide 過程。
Combine(合併):快排是就地排序(in place sort),不需要任何合併操作。
快排的核心就在分區。以《算法導論》的經典範例說明:
初始化:選取基元 P = 2(陣列首元素),令 i = 1,j = i + 1 = 2(陣列下標從 1 開始)。
循環不變量:2 到 i 之間的元素都小於或等於 P,i+1 到 j 之間的元素都大於或等於 P。
循環過程:j 從 2 走到 n,逐一考察 j 位置的元素。若它大於或等於 P,繼續循環;若小於 P,就把 j 位置的元素與 i+1 位置的元素交換,並將 i 加一。這樣就維持了上述循環不變量。
循環結束後還有一個關鍵動作:必須把 i 位置的元素與陣列首元素交換,才能把基元放到最終的正確位置。
有人會想到更直白的做法:把基元另外存到一個同樣大小的陣列中,遇到比它小的放左半部,比它大的放右半部。這種做法時間複雜度同樣是 Θ(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; // 初始化 i, j
for (j = start + 1; j <= end; j++)
// 若此處元素小於基元,就與 i+1 處元素交換並將 i 加一;否則繼續循環
if (array[j] < key)
{
int temp = array[j];
array[j] = array[i + 1];
array[i + 1] = temp;
i++;
}
array[start] = array[i]; // 交換 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²)。實務上的改善方式是隨機選取基元,或在遞歸深度過大時改用插入排序處理小區間。