在非常非常久之前，我寫過了合併排序、堆積排序這兩個 O(nlog(n)) 的排序演算法簡介，一直都沒寫到快速排序法，因為我懶。
相信許多人都聽說過快速排序法很快，有 O(nlog(n)) 的水準，這篇我不提時間複雜度怎麼計算的，因為我也不會 XD，不過我可以稍微講述一下整個演算法的過程，讓想了解的人至少知道思路是什麼。
- 演算法核心 — Pivot 基準點
在快速排序中，pivot 是整個演算法最大的特色，假設我們有一串陣列 arr = [5, 3, 9, 7, 1]，我們可以挑選一個值作為基準點，把比他還要大的東西放到右邊，比他還要小的放左邊。
這邊我挑選 5 作為基準點，所以以這個規則來看，我們的陣列會變成 [3, 1, 5, 9, 7]，你可以發現在 5 左邊的 [3, 1] 都比 5 小，在 5 右邊的 [9, 7] 都比 5 大。
當然也不一定要是 [3, 1, 5, 9, 7]，你也可能是 [1, 3, 5, 9, 7] 甚至是 [1, 3, 5, 7, 9]，全看你的演算法是怎麼寫的。
- 分而治之
「可是如果是 [3, 1, 5, 7, 9]，這樣還沒排好呀！」
且慢，你有沒有發現這個 5 在這邊有個特點，我們已經知道了比 5 小的值都在他左邊，比 5 大的值都在他右邊，這樣我們可以確定一件事情，「若這個陣列是排序好的，這個 5 的位置就是在這邊，也就是 arr[2]」，不論你左右邊的值怎麼調動，只要遵守「左小右大」的規則，那麼 5 的位置就是確定在這邊了。
不信的話你看，[1, 3, 5, 7, 9] 是最後排序好的結果，5 的位置是在 arr[2]。而剛剛的結果 [3, 1, 5, 7, 9]，5 的位置也是在 arr[2]。
接著就是要利用這個特點，來 Divide and conquer 了，因為我們知道 5 的位置固定了，接下來就是對左邊和右邊進行處理了，怎麼處理？
我們仿照上面的流程，再做一遍。
首先先確定要排序的索引值區間是 [0, 2)，就是 for i = 0; i < 2; ++i 的意思，接著套用一樣的流程。子陣列 [3, 1]，挑選 3 為 pivot，比 3 小的都放左邊，比 3 大的都放右邊，可以得到新陣列 arr = [1, 3, 5, 9, 7]。
再來處理右邊 [3, 5), 可以得到新陣列 arr = [1, 3, 5, 7, 9]。
燈愣，陣列就這樣排好了。
- Pivot 的挑選
「那 pivot 一定只能選最前面的元素嗎？」
其實 pivot 要選哪個都可以，你可以選最前面的元素，也可以選最後面的元素，也可以選中間的某個元素，甚至你隨機挑選都可以。只要可以遵守「左小右大」的規則，快速排序就可以實現。
Pivot 的挑選主要會影響某些特殊情況的時間複雜度，例如我的陣列是 arr = [5, 4, 3, 2, 1]，而我每次都挑選最前面的元素來當 pivot，那麼不難發現快速排序法的運算時間會大大增加，退化到 O(n^2)，因為每次都要把 pivot 往後推 n-1 次。
所以理論上來說，隨機挑選 pivot 是最可以把快速排序發揮到平均水準的，不過實作上來說，挑選固定 pivot 會相對的簡單一點。
- 程式碼
| /* * * @param arr - The array that is going to be sorted. * @param beginI - The start index of the array. Note that the interval is closed. * @param endI - The end index of the array. Note that the interval is closed. */ void quickSort(vector<int> &arr, int beginI, int endI) { if(beginI >= endI) { // if the array has only one element return; } int pivot = beginI; for(int i = beginI+1; i < endI+1; ++i) { if(arr[i] <= arr[pivot] && pivot < i) { swap(arr[pivot+1], arr[i]); swap(arr[pivot], arr[pivot+1]); pivot++; } } quickSort(arr, beginI, pivot-1); quickSort(arr, pivot+1, endI); } |
達人
