快速排序在做什麼
快速排序也是分而治之，但「難的工作」放在拆分這一步：
- 挑基準：從區間挑一個數字當基準，先換到區間最右邊。
- 分割：用 j 由左往右掃描。比基準小的數字，就和 i 位置的數字交換，放進左邊的「小於基準區」，i 往前一格；不比基準小的就留在右邊。
- 放定基準：掃描完畢，把基準換到 i 的位置。它左邊都比它小，右邊都不比它小，所以這個數字已經在最終位置。
- 遞迴：分別對基準左邊、右邊的區間重複同樣的事。只剩一個數字的區間不用再處理。
基準怎麼選，差很多
- 首、尾：最簡單，但遇到已排序的資料會是最差情況。
- 三數取中：取首、中、尾三個數字的中位數，已排序的資料也能切得很平均。
在上方切換三種選法，再按「已排序」比較：用首或尾時，比較次數是 n(n − 1) / 2，遞迴深度是 n；改用三數取中，兩個數字都小很多。
為什麼最差是 O(n²)、平均是 O(n log n)
最差情況時，每次只切掉一個數字：第一輪比較 n − 1 次，第二輪 n − 2 次……加起來 n(n − 1) / 2，呼叫堆疊也疊到 n 層。
如果每次都切在中間，只需要 log n 層，每一層總共比較約 n 次，就是 n log n。按「平衡分割」可以看到這種最佳情況，8 個數字只要 4 層（最差情況要 8 層）。隨機的資料平均下來很接近這種情況，這就是平均 O(n log n) 的由來。
複雜度
| 最佳 | O(n log n) |
|---|---|
| 平均 | O(n log n) |
| 最差 | O(n²) |
| 額外空間 | O(log n) |
| 穩定 | 否 |
常見問題
- 快速排序的最差情況是什麼時候？
- 每次選到的基準剛好是最小或最大的數字，分割後一邊是空的、另一邊只少了一個數字。例如對已排序的資料用「首」或「尾」當基準，就會變成 O(n²)，遞迴也會深到 n 層。
- 怎麼避免最差情況？
- 常見做法是「三數取中」（取首、中、尾的中位數）或隨機選基準。本頁可以切換基準的選法，再按「已排序」看比較次數和遞迴深度的差別。
- 快速排序比合併排序快嗎？
- 實務上常常是，因為它在原陣列上就地分割，額外空間只有遞迴堆疊 O(log n)，對快取也友善。代價是最差情況 O(n²)，而且不穩定。
- 快速排序是穩定的嗎？
- 不是。把基準或較小的數字換到前面時，可能讓原本相等的兩個值改變相對順序。
- 為什麼要先把基準換到最右邊？
- 這樣掃描時基準不會被移動，等掃描完，再一次換到它的最終位置就好。