快速排序是一種高效的排序算法，它基於分治（Divide and Conquer）的思想，通過選擇一個“基準元素”，將數組分成兩部分，一部分所有元素都比基準小，另一部分所有元素都比基準大，然後遞歸地對這兩部分進行排序。這種方法能快速處理大規模數據，平均時間複雜度爲 O(n log n)，是實際應用中最常用的排序算法之一。
快速排序的基本步驟¶
以數組 [6, 3, 8, 5, 2, 7] 爲例，我們來一步步演示快速排序的過程：
- 選擇基準元素（Pivot）：這裏選擇數組最右邊的元素
7作爲基準。 - 分區（Partition）：遍歷數組，將小於基準的元素移到基準左側，大於基準的元素移到右側。分區後數組變爲
[6, 3, 5, 2, 7, 8]，基準7最終位於位置4（索引從 0 開始）。 - 遞歸排序：此時，基準左側的子數組
[6, 3, 5, 2]和右側的子數組[8]（長度爲 1，無需排序）需要分別遞歸排序。 - 處理左側子數組：對
[6, 3, 5, 2]重複上述步驟，選擇最右邊元素2作爲基準，分區後得到[3, 5, 2, 6]，基準2位於位置0，左側子數組爲空，右側子數組[3, 5, 6]繼續遞歸排序。 - 最終結果：經過多次遞歸後，數組將完全有序：
[2, 3, 5, 6, 7, 8]。
分區函數的核心邏輯¶
分區是快速排序的關鍵步驟，其目標是將數組分爲“小於基準”和“大於基準”兩部分，並返回基準元素的最終位置。以選擇最右側元素爲基準爲例，分區過程如下：
- 定義變量
pivot = arr[right]（基準元素）。 - 定義指針
i指向“小於基準區域”的末尾（初始爲left - 1）。 - 遍歷數組（從
left到right - 1）：
- 若當前元素arr[j] <= pivot，則將其加入“小於基準區域”，即i++後交換arr[i]和arr[j]。 - 遍歷結束後，將基準元素
pivot交換到i + 1的位置（“小於基準區域”的末尾 + 1），此時基準元素左側均小於它，右側均大於它。
Java 代碼實現¶
下面是使用 Java 實現快速排序的完整代碼，包含分區函數和遞歸排序邏輯：
public class QuickSort {
// 快速排序主方法：遞歸排序數組的 [left, right] 區間
public static void quickSort(int[] arr, int left, int right) {
// 遞歸終止條件：區間長度小於等於1時無需排序
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]; // 選擇最右側元素作爲基準
int i = left - 1; // i 指向“小於基準區域”的末尾（初始爲空）
// 遍歷數組，將小於等於基準的元素移到左側
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++; // 擴展“小於基準區域”
// 交換 arr[i] 和 arr[j]，將當前元素加入“小於基準區域”
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 將基準元素交換到最終位置（i+1）
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
// 返回基準元素的索引
return i + 1;
}
// 測試方法：驗證快速排序的正確性
public static void main(String[] args) {
int[] arr = {6, 3, 8, 5, 2, 7};
System.out.println("排序前數組：");
for (int num : arr) {
System.out.print(num + " ");
}
quickSort(arr, 0, arr.length - 1);
System.out.println("\n排序後數組：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
代碼運行結果¶
運行上述代碼，輸出如下：
排序前數組：
6 3 8 5 2 7
排序後數組：
2 3 5 6 7 8
時間複雜度與空間複雜度¶
- 時間複雜度：平均情況下爲 O(n log n)（每次分區操作將數組分爲大致相等的兩部分，遞歸深度爲 log n）；最壞情況下（如數組已排序或逆序）爲 O(n²)（每次分區僅將數組分爲 1 和 n-1 兩部分，遞歸深度爲 n）。
- 空間複雜度：主要來自遞歸調用棧，平均爲 O(log n)，最壞爲 O(n)。
總結¶
快速排序通過分治思想高效排序數組，核心在於分區操作和遞歸處理。其優點是平均效率高，適合大規模數據；缺點是不穩定排序（相等元素的相對順序可能改變），且最壞情況性能較差。掌握快速排序不僅能理解分治算法，也能爲後續學習更復雜的排序算法打下基礎。