快速排序（quick sort）介紹

 快速排序是什麼？

利用分治法（divide and conquer）對數列做排序。基本原理：選一個基準值（pivot）（通常選第一/最後/中間或隨機一個），將數列分成兩部份，比基準值大的數列，與比基準值小的數列，後遞迴對這兩個部分做排序，最終合併已排序的部分得到最後結果。適合數據無特定條件與特性，或大量數據。

規則

由小至大排，從左至右>元素比基準值大，從右至左<比基準值小，做交換。如比基準值小的沒有，則是正確位置不用交換。

由大至小排，從左至右>元素比基準值小，從右至左<比基準值大，做交換。如比基準值大的沒有，則是正確位置不用交換。

* 記憶：左邊爸爸頭比較大，右邊兒子頭比較小

舉例

有一個數列[9, 3, 7, 6, 2, 8, 1, 5]用快速排序。

1. 選基準值5，分二數列[ 3, 2, 1|5|9,7,6,8]。

2. 對比基準值小數列[3,2,1]，2當基準值的[1| 2|3]

3. 對比基準值大數列[9,7,6,8]，8當基準值的[7,6| 8|9]

4. 對數列[7,6]，6當基準值得，[6|7]

5. 合併所有數列得[1,2,3,5,6,7,8,9]

細節舉例（容易錯）

有一個數列[9, 3, 7, 6, 2, 8, 1, 5]用快速排序。下面為每回合（指基準值插入正確位置後算一個回合）步驟：

回合1. 選基準值為9，從兩邊找，左邊找比基準值大的沒有，右邊找比基準值小的5，左右代理人相遇在5，與基準值9交換

[|9|, 3, 7, 6, 2, 8, 1, 5]

[|5|, 3, 7, 6, 2, 8, 1, 9]

回合2. 選基準值5，從兩邊找，左邊找比基準值大的7，右邊找比基準值小的1，交換

[|5|, 3, 7, 6, 2, 8, 1, 9]

[|5|, 3, 1, 6, 2, 8, 7, 9]

（1）. 選基準值5，從兩邊找，左邊找比基準值大的6，右邊找比基準值小的2，交換

[|5|, 3, 1, 6, 2, 8, 7, 9]

[|5|, 3, 1, 2, 6, 8, 7, 9]

（2）. 左右代理人相遇在2與基準值5交換

[|5|, 3, 1, 2, 6, 8, 7, 9]

[|2|, 3, 1, 5, 6, 8, 7, 9]

（3） 選基準值2，從兩邊找，左邊找比基準值大的3，右邊找比基準值小的1，交換

[|2|, 1, 3, 5, 6, 8, 7, 9]

（4） 選基準值2，從兩邊找，左邊找比基準值大的3，右邊找比基準值小的1，相遇在1交換

[|1|, 2, 3, 5, 6, 8, 7, 9]

（5） 選基準值1，從兩邊找，左邊找比基準值大的2，右邊找比基準值小的沒有，在正確位置不換

[|1|, 2, 3, 5, 6, 8, 7, 9]

[1, |2|, 3, 5, 6, 8, 7, 9]

...

[1, 2, 3, 5, 6, |8|, 7, 9]

（5） 選基準值8，從兩邊找，左邊找比基準值大的9，右邊找比基準值小的7，相遇在7換

[1, 2, 3, 5, 6, |8|, 7, 9]

[1, 2, 3, 5, 6, |7|, 8, 9]

時間複雜度

最佳/平均時間複雜度，每次分割基準值的過程耗時log n，比較需耗時（O(n)），所以時間複雜度為O(nlogn)。

最差時間複雜度，每次選基準值在最大或最小值，造成分區不平衡，遞迴深度為n，每次分割皆掃描整個數列做分區（O(n)），所以時間複雜度O(n^2)。為避免最差，通常用隨機取基準值或三數（第一、最後、中間元素）取中間值法。

空間複雜度

快速排序的空間複雜度是平均情況下為 O(log n)。因快速排序是原地排序演算法（in-place sorting），主要使用遞迴實現，因此在遞迴過程中每次分割會佔用 O(log n) 的空間。