快速排序是算法領域的"九陽神功"，掌握其精髓能讓你在算法修煉之路上突破瓶頸。

1. 快速排序的核心思想

快速排序（Quicksort）是一種基于分治思想的高效排序算法，核心步驟為：

1. 選擇基準值（Pivot）：通常選擇待排序區間的第一個元素（也可隨機選或取中間值）。 [元素≤pivot] + [pivot] + [元素>pivot]
2. Partition（分割）操作：
   • 將數組分為兩部分，使得基準值左側元素均 ≤ 基準值，右側元素均 ≥ 基準值。
   • 實現方法：通過交替從右向左、從左向右掃描，交換不符合條件的元素，最終確定基準值的正確位置。
3. 遞歸處理子數組：對基準值左右兩側的子數組重復上述步驟，直到所有元素有序。

---

2. Partition操作的關鍵細節

• 空位交替填充：選擇基準值后，其初始位置視為“空位”，通過交替從后向前掃描小元素、從前向后掃描大元素，將元素填入空位，最終確定基準值的位置。
• 時間復雜度：單次 Partition 操作的時間復雜度為 O(n)，需遍歷整個子數組。

示例：
原始數組 [8, 6, 3, 10, 9, 7, 2, 12]，選擇 8 為基準值：

1. 從右向左找到 2 < 8，將其填入空位 → [2, 6, 3, 10, 9, 7, _, 12]。
2. 從左向右找到 10 > 8，將其填入空位 → [2, 6, 3, _, 9, 7, 10, 12]。
3. 重復直至基準值位置確定 → [2, 6, 3, 7, 9, 8, 10, 12]。

---

3.兩種經典實現方式

1. Lomuto分區（直觀易實現）：

• 以最后一個元素為基準
• 雙指針維護分割點

  def partition(arr, low, high):pivot = arr[high]i = low  # 分割點for j in range(low, high):if arr[j] <= pivot:arr[i], arr[j] = arr[j], arr[i]i += 1arr[i], arr[high] = arr[high], arr[i]return i
  

2. Hoare分區（更高效）：

• 使用首元素為基準
• 雙指針從兩端向中間掃描

  def partition(arr, low, high):pivot = arr[low]left, right = low+1, highwhile True:while left <= right and arr[left] <= pivot: left += 1while left <= right and arr[right] >= pivot: right -= 1if left > right: breakarr[left], arr[right] = arr[right], arr[left]arr[low], arr[right] = arr[right], arr[low]return right
  

4. 時間復雜度分析

快速排序的性能高度依賴基準值的選擇：

• 最好情況：每次基準值均接近中位數，遞歸樹高度為 log?n，時間復雜度為 O(n log n)。
• 最壞情況：基準值始終為極值（如最大值或最小值），遞歸退化為鏈表，時間復雜度為 O(n2)。
• 平均情況：隨機選擇基準值時，時間復雜度接近 O(n log n)。

類比二叉樹：

• 每次 Partition 將數組分為左右子樹，遞歸深度對應樹的高度。
• 樹越平衡（層數少），效率越高；樹越不平衡（層數多），效率越低。

---

5. 快速排序的優化與應用

• 工程優化：混合排序策略（如 C++ STL 的 sort 函數結合快速排序、插入排序和堆排序）。
• 尾遞歸優化：

def quick_sort(arr, low, high):while low < high:pi = partition(arr, low, high)quick_sort(arr, low, pi-1)low = pi + 1  # 減少遞歸深度

• 三路快排：
  • 處理大量重復元素：劃分為 <pivot、=pivot、>pivot 三部分
• 實際應用：
  • 2-sum 問題：先排序再使用雙指針法高效求解。
  • 快速選擇算法（QuickSelect）：基于 Partition 操作，在 O(n) 時間內找到第 k 小元素（下節課重點）。

---

6. 學習要點與誤區

• 關鍵思維：理解 Partition 操作是掌握快速排序的核心。
• 常見誤區：
  • 忽視基準值選擇對性能的影響。
  • 混淆 Partition 實現細節（如掃描順序、交換條件）。
• 實踐建議：
  • 手動模擬 Partition 過程（如紙上畫圖）。
  • 嘗試編碼實現快速排序，并通過調試理解遞歸流程。

---

7.總結

快速排序通過“分治 + Partition”高效解決排序問題，其核心在于：

1. 分治思想：將大問題分解為小問題遞歸處理。
2. 基準值選擇：直接影響算法性能，需結合實際場景優化。
3. 時間復雜度：平均 O(n log n)，是多數場景下的首選排序算法。

掌握快速排序不僅為后續算法（如快速選擇、歸并排序）奠定基礎，更是理解分治與遞歸思維的經典案例。