快速排序：如何選擇基準？分區過程圖解¶
一、快速排序是什麼？¶
快速排序是一種經典的排序算法，它基於 分治法 的思想：先將一個大問題分解成多個小問題，逐個解決後合併結果。核心步驟是 選一個基準（pivot），然後把數組分成兩部分——左邊都小於基準，右邊都大於基準，再遞歸排序左右兩部分。
快速排序的優勢是 平均效率極高（平均時間複雜度 O(n log n)），但如果基準選擇不當，可能退化爲 O(n²)，所以“基準選擇”和“分區過程”是快速排序的關鍵。
二、基準（pivot）怎麼選？¶
基準是快速排序的“導航燈”，選得好，分區更平衡，排序更快；選得差，可能導致數組“一邊倒”，效率暴跌。常見的基準選擇方法有以下幾種：
1. 最左/最右元素（最簡單但易踩坑）¶
直接選數組第一個或最後一個元素作爲基準。
- 缺點：若數組已排序（如 [1,2,3,4,5]），選最左元素（1）會導致分區後左邊爲空，右邊全是大於1的元素，此時每輪分區都只處理 n-1 個元素，時間複雜度退化爲 O(n²)。
- 例子：數組 [1,2,3,4,5]，選基準 1 → 分區後右邊是 [2,3,4,5]，遞歸處理 [2,3,4,5] 同理，最終時間複雜度 O(n²)。
2. 中間元素（避免極端情況）¶
選數組中間位置的元素作爲基準，比如長度爲 n 的數組，基準索引爲 n//2。
- 優點：比最左/最右更平衡，減少極端情況概率。
- 缺點：若數組接近有序，中間元素仍可能導致分區不平衡（如 [1,3,5,7,9]，中間元素 5 分區後左邊 [1,3]，右邊 [7,9]，遞歸處理沒問題，但極端情況仍可能出問題）。
3. 三數取中法（最推薦）¶
取數組 首、尾、中間三個元素的中值 作爲基準，既能避免有序數組的退化，又能保證分區平衡。
- 例子：數組 [1,2,3,4,5]，首=1，尾=5，中間=3，中值是 3 → 分區後左邊 [1,2]，右邊 [4,5]，遞歸處理更高效。
- 優勢：幾乎不會出現分區不平衡，時間複雜度穩定在 O(n log n)。
三、分區過程：把數組“一分爲二”¶
分區（Partition）是快速排序的核心步驟，目標是讓基準歸位，並將數組分爲“左小右大”兩部分。這裏用 左右指針法 演示分區過程，以數組 [5,3,8,4,2,7,1,6] 爲例（假設基準選最左元素 5）：
步驟 1：初始化¶
數組：[5,3,8,4,2,7,1,6]，基準 pivot = 5（左指針 i=0，右指針 j=7，i 和 j 分別指向數組兩端）。
步驟 2：移動右指針找“小”¶
右指針 j 從右往左找 第一個小於 pivot（5） 的數：
- j=7：arr[j]=6 >5 → 繼續左移；
- j=6：arr[j]=1 <5 → 找到！交換 arr[i] 和 arr[j] → 數組變爲 [1,3,8,4,2,7,5,6]，此時 i=1（基準已處理過第一個元素，左指針右移）。
步驟 3：移動左指針找“大”¶
左指針 i 從左往右找 第一個大於 pivot（5） 的數：
- i=1：arr[i]=3 ≤5 → 繼續右移；
- i=2：arr[i]=8 >5 → 找到！交換 arr[i] 和 arr[j] → 數組變爲 [1,3,5,4,2,7,8,6]，此時 j=5（右指針左移）。
步驟 4：重複直到指針相遇¶
繼續循環：
- j=5：arr[j]=7 >5 → 左移；
- j=4：arr[j]=2 <5 → 交換 arr[i] 和 arr[j] → 數組變爲 [1,3,2,4,5,7,8,6]，i=3；
- i=3：arr[i]=4 ≤5 → 右移；
- i=4：arr[i]=5 ≤5 → 右移；
- i=5：arr[i]=7 >5 → 交換 arr[i] 和 arr[j] → 數組變爲 [1,3,2,4,5,7,8,6]，此時 i=j=5，循環結束。
最終結果¶
基準 5 歸位到索引 5，數組分爲左右兩部分：
左子數組：[1,3,2,4]（全小於 5），右子數組：[7,8,6]（全大於 5）。
四、總結¶
快速排序的核心是 “選對基準+高效分區”：
- 基準選擇：優先用“三數取中法”避免極端情況，保證分區平衡；
- 分區過程：通過左右指針移動，將數組分爲“左小右大”，基準歸位後遞歸排序子數組。
這種方法讓快速排序在大多數情況下能以 O(n log n) 高效排序，是工程中最常用的排序算法之一。
小練習：試着用“三數取中法”對數組 [3,1,4,1,5,9,2,6] 選基準，並手動模擬分區過程吧！