先祝大家中秋節快樂！🌕

連假開始，別人在切柚子，我也在切——
只不過我切的是 Array。😂

前面學 Bubble Sort 時，是透過相鄰兩個數字不斷比較、交換，慢慢把最大的數字往後推。

今天開始認識另一種排序方式：Quick Sort（快速排序）。

既然名字直接叫「快速排序」，到底有多快速？Quick Sort 平均時間複雜度是 O(n log n)，不過最差情況仍可能來到 O(n²)。

但今天先不急著研究時間複雜度，我想先搞懂：

Quick Sort 到底是怎麼把資料排好的？

Quick Sort 到底在做什麼？

我目前把 Quick Sort 理解成三個步驟：

選擇基準值 Pivot → 分割 Partition → 對左右兩邊重複 Quick Sort

假設現在有一組資料：

[17, 3, 42, 8, 91, 26, 55, 13, 74, 6]

第一步：選擇基準值 Pivot

Quick Sort 會先選出一個 Pivot（基準值）。

Pivot 並不是規定一定要選第一個數字，常見的方式包含選擇第一個、最後一個、中間的元素，甚至隨機選擇。

今天為了方便理解，我先固定使用第一個數字：

Pivot = 17

第二步：「分割」Partition

選好 Pivot 後，接著拿其他數字跟 17 比較：

• 比 17 小 → 放左邊
• 比 17 大 → 放右邊

於是原本的 Array 可以拆成：

[3, 8, 13, 6] | 17 | [42, 91, 26, 55, 74]

這個依照 Pivot 將資料分成不同區域的過程，就是 Partition（分割／分區）。

但這時候要注意：

Partition 完成 ≠ 排序完成。

例如左邊：

[3, 8, 13, 6]

雖然全部都比 17 小，但裡面的 6 還是在 8、13 後面，所以還需要繼續處理。

繼續處理左邊

現在先看：

[3, 8, 13, 6]

一樣選第一個 3 當 Pivot：

[] | 3 | [8, 13, 6]

左邊已經沒有資料，所以繼續處理 [8, 13, 6]。

選擇 8：

[6] | 8 | [13]

當資料只剩下一個元素時，就不需要繼續分割。

最後左半邊得到：

[3, 6, 8, 13]

再處理右邊

回到最開始的 17，右邊是：

[42, 91, 26, 55, 74]

選擇 42：

[26] | 42 | [91, 55, 74]

接著處理 [91, 55, 74]：

[55, 74] | 91 | []

再處理 [55, 74]：

[] | 55 | [74]

最後右半邊得到：

[26, 42, 55, 74, 91]

把結果放回最開始 17 的左右兩邊：

[3, 6, 8, 13] | 17 | [26, 42, 55, 74, 91]

→ [3, 6, 8, 13, 17, 26, 42, 55, 74, 91]

排序完成！

原來這就是 Divide and Conquer

做到這裡，我才比較理解為什麼介紹 Quick Sort 時，常常會看到 Divide and Conquer（分治法）。

Divide = 把大問題分割成比較小的問題

Conquer = 分別解決這些小問題

套到 Quick Sort：

原本的大問題

[17, 3, 42, 8, 91, 26, 55, 13, 74, 6]

                │
                ▼
         Divide（分割）
                │
                ▼
 [3,8,13,6] | 17 | [42,91,26,55,74]
       │                    │
       ▼                    ▼
   Conquer               Conquer
       │                    │
       ▼                    ▼
繼續 Quick Sort       繼續 Quick Sort

所以 Quick Sort 最核心的流程就是：

選 Pivot → Partition → 左右兩邊繼續 Quick Sort → 直到不需要再分

Pivot 選誰都可以嗎？

前面提到 Pivot 有很多種選法，所以我一開始也很好奇：

「既然 Pivot 是基準值，那是不是選哪一個數字都可以？」

概念上是可以的，只是 Pivot 選得不同，Partition 之後切出來的結果也會不同。

例如同一組資料：

[17, 3, 42, 8, 91]

如果選 17：

[3, 8] | 17 | [42, 91]

左邊 2 個元素，右邊也有 2 個，分割得很平均。

如果改選 42：

[17, 3, 8] | 42 | [91]

這次變成左邊 3 個、右邊 1 個。

如果選最大的 91：

[17, 3, 42, 8] | 91 | []

其他數字全部都比 91 小，所以資料全部被分到左邊。

所以，Pivot 的選擇會影響每次 Partition 切出來的大小。

如果每次都像 17 一樣切得比較平均，左右兩邊的問題可以很快縮小；但如果常常像 91 一樣，幾乎所有資料都集中在同一邊，就需要更多次的分割。

這也和 Quick Sort 的時間複雜度有關：

• 平均情況：O(n log n)
• 最差情況：O(n²)

所以 Quick Sort 雖然叫「快速排序」，也不代表每一次都一定很快，Pivot 的選擇以及 Partition 是否平均，都可能影響排序效率。

參考資料

iT 邦幫忙，〈Day17 [演算法] 快速排序法 Quick Sort〉
https://ithelp.ithome.com.tw/articles/10278644

Amber，〈演算法學習筆記 12－快速排序法 Quick Sort〉，Medium
https://medium.com/@amber.fragments/演算法-學習筆記-12-快速排序法-quick-sort-841420575b24

GeeksforGeeks，〈Quick Sort〉
https://www.geeksforgeeks.org/dsa/quick-sort-algorithm/