快速排序法原理
快速排序使用分治法（Divide and conquer）策略，藉由一個基準值來把一個序列（list）分為較小（左）和較大（右）的 2 個子序列，然後遞迴地排序兩個子序列。
圖片來源
快速排序法運作
快速排序法運作有三個步驟：挑出基準值、分割、遞迴排序子序列。
這邊用使用原地（in-place）分割演算法的版本以及[9, 4, 1, 6, 7, 3, 8, 2, 5]來做範例：
1. 挑出基準值
通常是以最後一個元素為基準值，所以此範例基準值pivot = 5。
[9, 4, 1, 6, 7, 3, 8, 2, 5]
^
pivot
2. 分割
需要兩個 index 紀錄『小於 pivot 陣列』的最後位置 i 以及大於 pivot 陣列』的最後位置 j。
- 預期所有數值都比 pivot 大，所以初始值
i = -1，而j = 0。 - 比較中若發現 index(j) < pivot，則 i + 1。
- 乘上，i + 1 後與 pivot 比較，若 index(i) > pivot，則 index(i) 和 index(j) 交換位子，然後 j + 1。
- 不段重複上述 2, 3 直到比較到最後。
- 若 index(j) = pivot，代表已經比較完所有元素，此時 i, j 分別為小於 pivot 陣列的最後位置以及大於 pivot 陣列的最後位置。
- 將 index(i + 1) 和 pivot 交換，完成一輪比較。
setp 1
i j->
[9, 4, 1, 6, 7, 3, 8, 2, 5]
^
pivot
i = -1, j = 0;
index(j) = 9;
9 > 5， 所以 i 不變，j + 1
setp 2
i-> j
[9, 4, 1, 6, 7, 3, 8, 2, 5]
^
pivot
i = -1, j = 1;
index(j) = 4;
4 < 5，所以 i + 1
setp 3
i j->
[9, 4, 1, 6, 7, 3, 8, 2, 5]
<--> ^
pivot
i = 0, j = 1;
index(i) = 9; index(j) = 4;
9 > 5，所以 i 跟 j 換位子，然後 j + 1
setp 4
i-> j
[4, 9, 1, 6, 7, 3, 8, 2, 5]
^
pivot
i = 0, j = 2;
index(i) = 4; index(j) = 1;
1 < 5，所以 i + 1
setp 5
i j->
[4, 9, 1, 6, 7, 3, 8, 2, 5]
<--> ^
pivot
i = 1, j = 2;
index(i) = 9; index(j) = 1;
9 > 5，所以 i 跟 j 換位子，然後 j + 1
setp 6
i j->
[4, 1, 9, 6, 7, 3, 8, 2, 5]
^
pivot
i = 1, j = 3;
index(i) = 1; index(j) = 6;
6 > 5 ，所以 i 不變，j + 1
setp 7
i j->
[4, 1, 9, 6, 7, 3, 8, 2, 5]
^
pivot
i = 1, j = 4;
index(i) = 1; index(j) = 7;
7 > 5 ，所以 i 不變，j + 1
setp 8
i-> j
[4, 1, 9, 6, 7, 3, 8, 2, 5]
^
pivot
i = 1, j = 5;
index(i) = 1; index(j) = 3;
3 < 5 ，所以 i + 1
setp 9
i j->
[4, 1, 9, 6, 7, 3, 8, 2, 5]
<------> ^
pivot
i = 2, j = 5;
index(i) = 9; index(j) = 3;
9 > 5 ，所以 i 跟 j 換位子，然後 j + 1
setp 10
i j->
[4, 1, 3, 6, 7, 9, 8, 2, 5]
^
pivot
i = 2, j = 6;
index(i) = 3; index(j) = 8;
8 > 5 ，所以 i 不變，j + 1
setp 11
i-> j
[4, 1, 3, 6, 7, 9, 8, 2, 5]
^
pivot
i = 2, j = 7;
index(i) = 3; index(j) = 2;
2 < 5 ，所以 i + 1
setp 12
i j->
[4, 1, 3, 6, 7, 9, 8, 2, 5]
<-----------> ^
pivot
i = 3, j = 7;
index(i) = 6; index(j) = 2;
6 > 5 ，所以 i 跟 j 換位子。j + 1
setp 13
i j
[4, 1, 3, 2, 7, 9, 8, 6, 5]
^
pivot
這時 j 已經到達 pivot 的位子，代表所有的數列都已經和 pivot 比較過了。現在數列的中以 i 為分界，在 i 前面（包含 i )的數字比 pivot 小，在後面則比 pivot 大。
接下來要把 i 移動到比 pivot 大的數列中的第一個，並和 pivot 交換。所以 i + 1，i 跟 pivot 換位子。
setp 14
i j
[4, 1, 3, 2, 7, 9, 8, 6, 5]
<---------->^
pivot
如此一來我們就完成了第一輪排序。
result
[4, 1, 3, 2, 5, 9, 8, 6, 7]
^
3. 遞迴排序子序列
針對左右兩邊的元素重複上述1, 2 步驟直到完成所有元素的排序。
經過上述的三個步驟，挑出基準值、分割、遞迴排序子序列，即可完成快速排序法。
快速排序法的時間複雜度（Time complexity）
快速排序法因為是類似於對半分割的方法，所以時間複雜度為 log2(n)。而需要每個陣列都需要比較過，所以時間複雜度為 n。合併兩者的平均時間複雜度為 O(n log2(n))。但若是 pivot 沒有選擇好（最大獲最小），可能讓左或右邊的子陣列為空，則最壞情況時間複雜度為 O(n2)。
快速排序法實作
根據運作法則，挑出基準值、分割、遞迴排序子序列，三個動作來考量，我們可以分為兩個步驟：
- 挑出基準值、分割然後排序，並傳回最後基準值的 index 提供遞迴函數使用
sort_a_little_bit中利用 pivot 將陣列分成大小兩邊，並將 pivot 的 index 回傳出去。
- 使用遞迴排序子序列
sort_all中利用sort_a_little_bit取回的 pivot 的 index，將大小序列分別使用遞迴的方式繼續做排序。
def sort_a_little_bit(array, front, end):
pivot = array[end];
i = front -1;
for j in range(front, end):
if (array[j] < pivot):
i+=1
data = array[i]
array[i] = array[j]
array[j] = data
i += 1
data = array[i]
array[i] = array[end]
array[end] = data
return i;
def sort_all(array, front, end):
if (front < end):
pivot = sort_a_little_bit(array, front, end);
sort_all(array, front, pivot - 1);
sort_all(array, pivot + 1, end);
def quick_sort(array):
sort(array, 0, len(array)-1)
print(array)
data = [9, 4, 1, 6, 7, 3, 8, 2, 5]
quickSort(data)
最後，個人覺得快速排序一開始有點難以理解，需要慢慢地思考整個流程才比較可以了解是怎麼回事，可以自己列出一個陣列，一個一個換會比較有感。
- 練習程式碼
Resource
- Comparison Sort: Quick Sort(快速排序法)
- 快速排序