實務上最常用的排序 —— 選一個基準,把小的丟左、大的丟右,再各自快排。
1. 選基準 —— 從這段挑一個元素當 pivot(可以是最後一個、中間、或隨機)。
2. 分兩堆 —— 掃一遍,比基準小的排到左邊、比基準大的排到右邊。
3. 基準歸位 —— 掃完後把基準放到中間,它左邊全比它小、右邊全比它大,這個位置就是它最終的家。
4. 各自再來 —— 對左堆、右堆分別遞迴做一樣的事,直到每堆只剩一個。
隨手挑一顆當標準,比它小的丟左籃、大的丟右籃,再對兩籃各自照做。
找一個人當基準,矮的站他左邊、高的站右邊,兩邊再各自分。
抽一本當中間點,薄的一疊、厚的一疊,分完再各自整理。
示範一趟 partition:基準是最後一個(黃色)。指標 j 從左掃到右,紫色是正在看的,綠色是已經確定「比基準小」的左堆。按「下一步」走一遍,看基準最後怎麼歸位。
從最好懂的版本,到經典就地 partition、隨機化、選基準技巧、Quickselect 等應用。
❌ 對已排序資料又固定選第一個/最後一個當基準 —— 會退化成最壞的 O(n²)。解法:隨機基準或三數取中。
❌ 遞迴忘了縮小範圍 —— partition 回傳位置後,左邊要 p - 1、右邊要 p + 1,基準本身不用再排。
❌ 以為它穩定 —— 快速排序通常不穩定(相同鍵的原順序可能被打亂)。需要穩定就用合併排序。
[3, 1, 2] 選最後一個(2)當基準,做一趟 partition 後陣列長怎樣?基準 2 落在第幾格?把答案打到對話裡,我幫你對。