一、算法基礎

1.1 什么是快速排序

快速排序（Quick Sort）是一種高效的分治排序算法，由英國計算機科學家Tony Hoare于1960年提出。它的核心思想是：

• 選擇一個基準元素（pivot）
• 將數組分成兩部分：小于基準的元素和大于基準的元素
• 遞歸地對這兩部分進行排序

快速排序是實際應用中最常用的排序算法之一，平均情況下時間復雜度為O(n log n)，空間復雜度為O(log n)。

1.2 快速排序的基本思想

1. 選擇基準：從數組中選擇一個元素作為基準（通常是第一個元素、最后一個元素或中間元素）
2. 分區操作：將數組中小于基準的元素放在基準的左邊，大于基準的元素放在右邊
3. 遞歸排序：對基準左右兩部分分別進行遞歸排序

這個過程被稱為分區（Partition），是快速排序的核心操作。

1.3 時間復雜度分析

• 最佳情況：O(n log n) —— 每次分區操作都將數組均勻地分成兩部分
• 平均情況：O(n log n) —— 大多數情況下的性能表現
• 最差情況：O(n2) —— 當數組已經有序或幾乎有序時，選擇第一個或最后一個元素作為基準

二、快速排序的實現

2.1 基本實現

public class QuickSort {public static void sort(int[] arr) {if (arr == null || arr.length <= 1) {return;}quickSort(arr, 0, arr.length - 1);}private static void quickSort(int[] arr, int left, int right) {if (left < right) {// 獲取分區點int pivotIndex = partition(arr, left, right);// 遞歸排序左半部分quickSort(arr, left, pivotIndex - 1);// 遞歸排序右半部分quickSort(arr, pivotIndex + 1, right);}}private static int partition(int[] arr, int left, int right) {// 選擇最右邊的元素作為基準int pivot = arr[right];// i是小于基準區域的邊界int i = left - 1;// 遍歷區間，將小于基準的元素放到左邊for (int j = left; j < right; j++) {if (arr[j] <= pivot) {i++;// 交換元素swap(arr, i, j);}}// 將基準元素放到正確的位置swap(arr, i + 1, right);// 返回基準元素的索引return i + 1;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

2.2 遞歸過程分析

假設有數組：[8, 4, 2, 9, 5, 7, 6, 1, 3]

1. 第一次分區：

   • 選擇基準值 3（最后一個元素）
   • 分區后：[1, 2, 3, 9, 5, 7, 6, 8, 4]
   • 基準索引：2

2. 左子數組遞歸：[1, 2]

   • 選擇基準值 2
   • 分區后：[1, 2]
   • 基準索引：1

3. 右子數組遞歸：[9, 5, 7, 6, 8, 4]

   • 選擇基準值 4
   • 分區后：[4, 5, 7, 6, 8, 9]
   • 基準索引：0

4. 繼續遞歸...

最終得到排序結果：[1, 2, 3, 4, 5, 6, 7, 8, 9]

三、快速排序的優化

3.1 基準選擇優化

選擇好的基準可以顯著提高快速排序的性能。最常用的優化方法是三數取中（Median-of-Three）：

private static int selectPivot(int[] arr, int left, int right) {int mid = left + (right - left) / 2;// 將三個元素排序if (arr[left] > arr[mid]) {swap(arr, left, mid);}if (arr[left] > arr[right]) {swap(arr, left, right);}if (arr[mid] > arr[right]) {swap(arr, mid, right);}// 將中間值（基準）交換到right-1位置swap(arr, mid, right - 1);return arr[right - 1];
}

3.2 小數組使用插入排序

對于小規模數組（通常小于10個元素），插入排序比快速排序更高效：

private static void quickSort(int[] arr, int left, int right) {// 小數組使用插入排序if (right - left <= 10) {insertionSort(arr, left, right);return;}// 正常的快速排序過程if (left < right) {int pivotIndex = partition(arr, left, right);quickSort(arr, left, pivotIndex - 1);quickSort(arr, pivotIndex + 1, right);}
}private static void insertionSort(int[] arr, int left, int right) {for (int i = left + 1; i <= right; i++) {int key = arr[i];int j = i - 1;while (j >= left && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}

3.3 尾遞歸優化

通過將遞歸調用替換為迭代，可以避免棧溢出：

private static void quickSort(int[] arr, int left, int right) {while (left < right) {int pivotIndex = partition(arr, left, right);// 遞歸處理較小的子數組，迭代處理較大的子數組if (pivotIndex - left < right - pivotIndex) {quickSort(arr, left, pivotIndex - 1);left = pivotIndex + 1;} else {quickSort(arr, pivotIndex + 1, right);right = pivotIndex - 1;}}
}

四、典型應用：荷蘭國旗問題

荷蘭國旗問題是快速排序的一個典型應用，它要求將數組分成三個部分：小于、等于、大于某個值的元素。這種分區方法也稱為三向切分。

4.1 問題描述

給定一個數組和一個基準值，將數組重新排列，使得所有小于基準的元素在左邊，等于基準的元素在中間，大于基準的元素在右邊。

4.2 解法實現

public static void dutchFlagPartition(int[] arr, int pivot) {int left = 0;       // 小于pivot的區域右邊界int current = 0;    // 當前處理的元素int right = arr.length - 1;  // 大于pivot的區域左邊界while (current <= right) {if (arr[current] < pivot) {// 小于pivot的元素放左邊swap(arr, left, current);left++;current++;} else if (arr[current] > pivot) {// 大于pivot的元素放右邊swap(arr, current, right);right--;// 注意：此時不增加current，因為交換來的元素還未處理} else {// 等于pivot的元素保持原位current++;}}
}

4.3 應用到快速排序

使用三向切分可以優化快速排序，特別是處理有大量重復元素的數組：

private static void quickSort3Way(int[] arr, int left, int right) {if (left >= right) {return;}// 記錄小于、等于、大于pivot的三個區域邊界int lt = left;      // 小于pivot的區域右邊界int gt = right;     // 大于pivot的區域左邊界int i = left + 1;   // 當前處理的元素int pivot = arr[left];while (i <= gt) {if (arr[i] < pivot) {swap(arr, lt++, i++);} else if (arr[i] > pivot) {swap(arr, i, gt--);} else {i++;}}// 遞歸處理小于和大于的部分quickSort3Way(arr, left, lt - 1);quickSort3Way(arr, gt + 1, right);
}

五、完整實現與示例

以下是一個包含各種優化的完整快速排序實現：

public class OptimizedQuickSort {private static final int INSERTION_SORT_THRESHOLD = 10;public static void sort(int[] arr) {if (arr == null || arr.length <= 1) {return;}quickSort(arr, 0, arr.length - 1);}private static void quickSort(int[] arr, int left, int right) {// 小數組使用插入排序if (right - left <= INSERTION_SORT_THRESHOLD) {insertionSort(arr, left, right);return;}// 使用三數取中法選擇基準medianOfThree(arr, left, right);int pivot = arr[right - 1];// 分區int i = left;int j = right - 1;for (;;) {while (arr[++i] < pivot) {}while (arr[--j] > pivot) {}if (i >= j) break;swap(arr, i, j);}// 將基準放回正確位置swap(arr, i, right - 1);// 遞歸排序quickSort(arr, left, i - 1);quickSort(arr, i + 1, right);}private static void medianOfThree(int[] arr, int left, int right) {int mid = left + (right - left) / 2;if (arr[left] > arr[mid]) {swap(arr, left, mid);}if (arr[left] > arr[right]) {swap(arr, left, right);}if (arr[mid] > arr[right]) {swap(arr, mid, right);}// 將基準（中間值）放到right-1位置swap(arr, mid, right - 1);}private static void insertionSort(int[] arr, int left, int right) {for (int i = left + 1; i <= right; i++) {int key = arr[i];int j = i - 1;while (j >= left && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {8, 4, 2, 9, 5, 7, 6, 1, 3};System.out.println("原始數組: " + Arrays.toString(arr));sort(arr);System.out.println("排序后數組: " + Arrays.toString(arr));}
}

六、總結

核心要點

1. 分治思想：快速排序采用分治策略，通過分區操作將問題分解為子問題
2. 基準選擇：基準元素的選擇直接影響算法效率，好的選擇可以避免最壞情況
3. 就地排序：快速排序是一種原地排序算法，不需要額外的數組空間
4. 不穩定性：快速排序不是穩定排序算法，相同元素的相對順序可能改變

優缺點

優點：

• 平均情況下，性能優于其他 O(n log n) 排序算法
• 不需要額外的存儲空間（原地排序）
• 對緩存友好，局部性好

缺點：

• 最壞情況下，時間復雜度為 O(n2)
• 不穩定排序，無法保持相等元素的相對順序
• 對于小數組，可能不如插入排序高效

適用場景

• 需要高效排序大數組時
• 內存受限、不能使用額外空間時
• 當平均性能比最壞情況性能更重要時
• 不要求排序穩定性時

快速排序是一種高效且實用的排序算法，在大多數情況下都表現出色。通過本文介紹的各種優化技巧，可以使快速排序在實際應用中獲得最佳性能。掌握快速排序是每位程序員的基本功，也是理解分治算法思想的重要一步。