快速排序是一種高效的排序算法，基於分治法思想，平均時間複雜度爲O(n log n)，在實際應用中非常流行。它的核心是通過選擇一個基準元素(pivot)，將數組分爲兩部分，一部分所有元素小於基準，另一部分所有元素大於基準，然後遞歸地對這兩部分進行排序。
一、快速排序的核心思想¶
- 分治法：將一個大問題分解爲多個小問題解決。
- 選擇基準：在數組中選擇一個元素作爲基準(pivot)。
- 分區操作：重新排列數組，使所有小於基準的元素移到基準左側，大於基準的元素移到右側。
- 遞歸排序：遞歸處理基準左側和右側的子數組。
二、分區過程（Lomuto分區方案）¶
以數組最右側元素作爲基準(pivot)，具體步驟：
1. 初始化指針i指向小於基準區域的末尾（初始爲left-1）。
2. 遍歷數組從left到right-1，若當前元素小於基準，將i右移並交換當前元素到小於區域。
3. 遍歷結束後，將基準元素與i+1位置的元素交換，此時基準元素位於最終位置。
三、C++代碼實現¶
1. 分區函數（partition）¶
// 分區函數：返回基準元素的最終位置
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[right]; // 選擇最右側元素作爲基準
int i = left - 1; // 小於基準區域的邊界（初始爲空）
for (int j = left; j < right; j++) { // 遍歷除基準外的所有元素
if (nums[j] < pivot) { // 當前元素小於基準
i++; // 擴展小於區域
swap(nums[i], nums[j]); // 交換到小於區域
}
}
swap(nums[i + 1], nums[right]); // 將基準放到最終位置
return i + 1; // 返回基準位置
}
2. 快速排序主函數（quickSort）¶
// 快速排序主函數：遞歸排序數組的[left, right]區間
void quickSort(vector<int>& nums, int left, int right) {
if (left >= right) return; // 基本情況：子數組長度爲1或0，無需排序
int pivotIndex = partition(nums, left, right); // 獲取基準位置
quickSort(nums, left, pivotIndex - 1); // 遞歸排序左半部分
quickSort(nums, pivotIndex + 1, right); // 遞歸排序右半部分
}
3. 測試代碼¶
#include <iostream>
#include <vector>
using namespace std;
// 分區函數
int partition(vector<int>& nums, int left, int right) { /* 代碼同上 */ }
// 快速排序主函數
void quickSort(vector<int>& nums, int left, int right) { /* 代碼同上 */ }
int main() {
vector<int> arr = {6, 3, 8, 5, 2, 7, 1, 4};
int n = arr.size();
cout << "排序前數組：";
for (int num : arr) cout << num << " ";
cout << endl;
quickSort(arr, 0, n - 1); // 調用快速排序
cout << "排序後數組：";
for (int num : arr) cout << num << " ";
cout << endl;
return 0;
}
四、運行結果¶
排序前數組：6 3 8 5 2 7 1 4
排序後數組：1 2 3 4 5 6 7 8
五、關鍵說明¶
- 原地排序：分區操作在原數組上完成，無需額外空間。
- 遞歸終止條件：當子數組長度小於等於1時（
left >= right），遞歸結束。 - 時間複雜度：平均O(n log n)，最壞情況O(n²)（如數組已排序且選最左/右元素爲基準），通過隨機選基準可優化。
快速排序是面試和實際開發中高頻考察的算法，掌握其分區邏輯和遞歸思想是理解高效排序的關鍵。通過以上代碼和註釋，初學者可逐步掌握其實現原理。