快速排序：選一個王，左邊小、右邊大

想像你在分高矮

100 個人要排隊，你不想一個一個排。

Quick Sort 的做法：

隨便挑一個人當「基準 (pivot)」，叫他先站旁邊。
比他矮的全去左邊、比他高的全去右邊。
左邊和右邊各自再玩一次這個遊戲（遞迴）。

看一遍

排 [7, 2, 8, 1, 4, 9, 3, 5]，挑最後一個 5 當 pivot：

Partition（把比 5 小的丟左、大的丟右）：

原始：    [7, 2, 8, 1, 4, 9, 3, 5]
                              ↑ pivot

分區後：  [2, 1, 4, 3] [5] [7, 8, 9]
          <─── 比 5 小 ──>     <─ 比 5 大 ─>

5 已經在它最終的位置了！ 接下來各自玩：

左邊 [2,1,4,3] 挑 3 當 pivot:
  → [2,1] [3] [4]
  → [1][2][3][4]

右邊 [7,8,9] 挑 9 當 pivot:
  → [7,8] [9]
  → [7][8][9]

最後組起來：[1,2,3,4,5,7,8,9] ✓

💡關鍵直覺

每次都讓 pivot 站到它最終的位置，然後左右兩堆各自玩。跟 Merge Sort 的差別：Merge Sort 是「先切、再合」，Quick Sort 是「先分類、不用合」。

Pseudocode

Algorithm QuickSort(A, low, high):

if low < high:

p ← Partition(A, low, high)

QuickSort(A, low, p-1) // 排 pivot 左邊

QuickSort(A, p+1, high) // 排 pivot 右邊

Algorithm Partition(A, low, high):

pivot ← A[high] // 挑最後一個當 pivot

i ← low - 1

for j ← low to high-1:

if A[j] < pivot:

i ← i + 1

swap(A[i], A[j])

swap(A[i+1], A[high])

return i + 1

複雜度

情境	Big-O	何時發生
最壞	O(n²)	每次 pivot 都選到最小或最大（例如已排序陣列選最後一個當 pivot）
平均	O(n log n)	pivot 大致把陣列分成兩半時
最好	O(n log n)	pivot 剛好是中位數
空間	O(log n)	遞迴堆疊深度

⚠️最壞情況的陷阱

Quick Sort 的最壞是 O(n²)，這跟 Bubble Sort 一樣慘。 怎麼避免？ 隨機選 pivot，或用「三點取中法」（取頭、中、尾的中位數當 pivot）。

Quick Sort vs Merge Sort

	Quick Sort	Merge Sort
平均	O(n log n)	O(n log n)
最壞	O(n²) ⚠️	O(n log n)
空間	O(log n)	O(n)
穩定？	否	是
實務	最常用（cache-friendly）	鏈結串列、外部排序

📝考試會這樣考

題型一：給陣列和 pivot 選法，跑 Partition 一輪。

例：[3, 7, 1, 9, 4, 2, 8]，用最後一個元素當 pivot，跑一次 Partition 後陣列長什麼樣？

怎麼下筆：

pivot = 8
比 8 小的：3, 7, 1, 4, 2 → 全在左
比 8 大的：9 → 在右
結果：[3, 7, 1, 4, 2, 8, 9]，pivot 位置 index = 5

題型二：為什麼最壞 O(n²)？ 答：當每次 partition 都只切掉 pivot 自己（pivot 剛好是最大或最小），就變成 T(n) = T(n-1) + O(n)，解出來是 O(n²)。

題型三：為什麼實務上用 Quick Sort 不用 Merge Sort？ 答：Quick Sort 不需要額外空間（in-place）、cache-friendly（連續記憶體存取），常數倍率比 Merge Sort 小。雖然最壞 O(n²)，但用隨機 pivot 機率上幾乎不會發生。

這章記住

選 pivot → 分區 → 兩邊各自玩。
平均 O(n log n)，最壞 O(n²)（要小心 pivot 選擇）。
in-place、cache-friendly，所以實務最常用。