# 快速排序 (Quick sort)

## 簡介
快速排序是對泡沫排序的一種改進。通過一輪排序將要排序的數據分割成獨立的兩部分，其中一部分的數據都比另外一部分的數據要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞迴進行，以此達到整個數據變成有序。

## 基本思想

1. 先從陣列中取出一個數作為基準數。
2. 以基準數做分區，將比基準數大的數放到它的右邊，小於或等於它的數全放到它的左邊。
3. 再對左右區間重複第二步，直到各區間只有一個數。

## 算法

**一、設有一組數據 `[2,10,5,11,34,28,21]` 使用快速排序法由小到大排序**

其過程為：


上面的例子使用圖解，下面的例子用文字敘述。

**二、使用快速排序法將陣列 [19,97,9,17,1,8] 由小到大排序**

1. 首先我們需要有 i , j 兩個索引
2. 暫定陣列第一個值，也就是 19 為基準值
3. i 索引由 0 開始由左至右移動，j 索引由 陣列最末尾開始由右至左移動 [19(i), 97, 9, 17, 1, 8(j)]
4. 因為我們是將基準值設為左邊第一個，因此我們比較要從最末尾開始比較。
這個陣列的最末尾為 8，將之與基準值 19 做比較，如果比基準值小，放置於i位置，如果比基準值大則不動。8 < 19，因此 8 要放到 i 位置，此時 i+1 進行下一位數比較。
此時陣列為 [8, 97(i), 9, 17, 1, 19(j)]
5. 此時 i 指向的數為 97，與基準值比較 97 > 19，因此將 97放到 j 位置，此時 j-1，繼續下一位比較。此時陣列為 [8, 19(i), 9, 17, 1(j), 97]
6. 此時 j 指向 1，與基準值比較 1 < 19，因此要將 1 放到 i 位置，然後 i+1繼續進行下一個比較。此時陣列為 [8, 1, 9(i), 17, 19(j), 97]
7. 此時 i 指向 9，與基準值比較 9 < 19，因此9要放到左邊，但9本來就在左邊，所以不用動，但是要記得 i+1 指向下一個數比較。此時陣列還是 [8, 1, 9, 17(i), 19(j), 97]
8. 此時 i 指向 17，與基準值比較 17 < 19，因此依然不動，還是一樣 i+1 指向下一個位置，此時陣列還是 [8, 1, 9, 17, 19(i,j), 97]。
9. 直到此刻，i索引和j索引重疊，指向同一個位置，即將基準值 19 擺在重疊的位置，完成排序。

但是我們能發現 [8, 1, 9, 17, 19, 97] 其實還並沒有完成由小到大排序，我們需要再對基準值左右子序列再繼續以上步驟排序，這邊比基準值 19 小的左子序列為 [8, 1, 9, 17]，右子序列為[97]，只剩下一個數的序列已然排序，所以我們只需要再對左子序列進行以上步驟排序。

最終得到排序後的陣列為 [1, 8, 9, 17, 19, 97]。

### 優化

#### Middle-of-Three
1. 令 middle = (left + right) /2
2. 比較 A[left]、A[middle] 與 A[right] 這三筆資料，排出中間值。
3. 將此中間值再與 A[left] 做交換
4. 讓現在新的 A[left] 作為 pivot

#### 詳細請參考
- [Worse case 改進](https://kopu.chat/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-quick-sort/#lwptoc4)

## 參考資料
- [quick sort geeksforgeeks](https://www.geeksforgeeks.org/quick-sort/)
- [Ithome 詳解](https://ithelp.ithome.com.tw/articles/10202330?sc=iThelpR)