快速排序法（Quick Sort）可以就字面意思來理解，很快速地排好大量需排序資料，算是實用性很高的算法。
想法
基本想法：從 \(A_1, A2, \dots, A_n\) 中，隨機挑一個 \(A_p\) 當基準點（pivot element），比 \(A_p\) 小的就放左邊，反之放右邊。
過程基本上就是 divide and conquer，也就是說把大問題分成小問題再處理。我們把資料分成兩邊，希望每邊的規模可以越來越小。以這樣的概念來看，worst case 便是其中一邊完全沒有資料（也就是資料的規模完全沒有變小）。換句話說，\(A_p\) 這個點怎麼挑、如何挑到有代表性的元素，就變得很重要。
如何避免worst case？
盡量找到一個（排序後）比較中間的元素。
ex：在 sequence 中挑三、五個元素，取他的中間數作為 pivot element。（但也有可能數字一樣的很多，像是1, 2, 3, 4, 9, 9, 9, 9, 9, 9,9 這種，結果都挑到最大的之類的）
也就是說 pivot element 不必是正中間，只要左右各佔一個比例就可以了。
比較的元素
- 左邊的每個元素都和 \(x\) 做過比較
- 右邊的每個元素都和 \(x\) 做過比較
- 一旦分割成左、右兩個部分，左邊和右邊之元素不會做任何的比較。
講解
一樣上圖講解一下實際操作XD
以下是我們要排序的數列，有 index i 和 j 移動，紅框是目前我們挑中的 pivot。
我們會把所有比 pivot 小的全往前丟到左手邊，i 就是是紀錄左手邊最後被丟過來的元素的 index，為的是最後我們能夠把 pivot 丟到這個 index 後面一格，而 j 是目前輪到的元素。
接下來我們一步一步看排序怎麼執行：
Step 1：9 大於 5，不用動，j 移動至下一格。
Step 2：4 小於 5，要丟到左手邊，i 先往前一格，i 和 j 元素互相交換，j 移動至下一格。
Step 3：1 小於 5，要丟到左手邊，i 先往前一格，i 和 j 元素互相交換。
Step 4：6 大於 5，不用動，j 移動至下一格。
Step 5：7 大於 5，不用動，j 移動至下一格。
Step 6：3 小於 5，要丟到左手邊，i 先往前一格，i 和 j 元素互相交換。
Step 7：8 大於 5，不用動，j 移動至下一格。
Step 8：2 小於 5，要丟到左手邊，i 先往前一格，i 和 j 元素互相交換。
Step 9：最後因為 j 已經抵達 pivot 的前一格了，結束整個迴圈。最後一個步驟就是 pivot 要移到中間，所以 i 一樣要 +1，移動到下一格後，再把 pivot 元素往左邊丟（pivot 和 index=1 元素互換），基本上這一輪就大功告成。
應該可以感受到我們不會太在乎 pivot 前（左手邊）或 pivot 後（右手邊）的元素排序，只在乎左邊是不是都是比 pivot 小，右手邊是不是都比 pivot 大，之後黃色和藍色此生不會再互相比較。
最後我們再把左右兩邊分開，黃色組和藍色組各自以上面的邏輯操作，組別將會越拆越小。
實際操作
Quick sort 會有兩個主要操作：
- 進行排序
QuickSort(A, p, r): //排序陣列A裡index從p到r的部分
if p < r:
q = Partition(A, p, r)
QuickSort(A, p, q - 1)
QuickSort(A, q + 1, r)- 分割陣列
Partition(A, p, r):
x = A[r] //把第r個位置的值記為x
i = p - 1
for j = p to r - 1:
if A[j] ≤ x: //看目前要檢查的元素是不是小於x（第r個位置的值）
i = i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1Best
空間複雜度：\(O(\log(n))\)
時間複雜度：\(O(n\log(n))\)
Average
空間複雜度：\(O(\log(n))\)
時間複雜度：\(O(n\log(n))\)
Worst
空間複雜度：\(O(\log(n))\)
時間複雜度：\(O(n^2)\)
#include <vector>
using namespace std;
void quickSortHelper(vector<int> &array, int startIdx, int pivotIdx);
int partition(vector<int> &array, int startIdx, int pivotIdx);
vector<int> quickSort(vector<int> array) {
quickSortHelper(array, 0, array.size() - 1);
return array;
}
void quickSortHelper(vector<int> &array, int startIdx, int pivotIdx){
int median;
if (startIdx < pivotIdx){
median = partition(array, startIdx, pivotIdx);
quickSortHelper(array, startIdx, median - 1);
quickSortHelper(array, median + 1, pivotIdx);
}
}
int partition(vector<int> &array, int startIdx, int pivotIdx){
int pivotValue = array[pivotIdx];
int i = startIdx - 1;
for (int j = startIdx; j <= (pivotIdx - 1); j++){
if (array[j] <= pivotValue){
i = i + 1;
swap(array[i], array[j]);
}
}
swap(array[i+1], array[pivotIdx]);
return i + 1;
}
