快速排序概述
快速排序(Quiksort)是一種通過基準劃分區塊並不斷交換左右項的排序方式，其採用了分治法，減少了交換的次數。平均算法複雜度：O(NlogN)。
步驟是：
- 先找到一個基準點(pivot)，為了便於理解一般是位於數組中間的那一項。
- 逐個循環數組將小於基準的項放左側，將大於基準的數放右側。一般通過交換的方式來實現。
- 將基點左側全部項和基點右側全部項分別通過遞歸(或遍歷)形式重複第1項，直到所有數組都交換完成。
快速排序執行過程分析
圖1 快速排序執行過程
從上圖可以看出：
- 先找到基準項。比如是中間項(根據left與right之和除以2), 得到基準值arr[2] = 3。
- 再將基準項左側大於3的項挪到右側，將右側小於3的項挪至左側。得到 [2,1,3,5,4]
- 開始新的分區。基準項左側2,1為新的分區，右側5,4為新的分區。將它們分別按照1、2步驟進行處理。
- 2,1位於數組的第0,1項,得到中間項0，基準值為2，交換後得到1,2
- 5,4位於數組的第3,4項,中間項(3+4)/2取整得到3，基準值為5，交換後得到4,5
- 全部分區都按照1，2步驟完成後，得到最後的排序結果
快速排序實現
1、遞歸新建數組版。無需交換，每個分區都是新數組。
圖2 快速排序遞歸新建數組版
這個版本最容易理解，先找準基準項(用中間項表示)，把小於基準項的全添加到左側新數組，大於等於基準項的放在右側新數組，然後分別遞歸調用左、右新數組，再重複第一步找基準項，再據此一分為二。直到把數組項拆分為一個個length為1的數組。最後自左往右將最小值與中間項和最大值連接起來。這裡利用到JS語法中的concat，可以有效地連接數組。
這個版本好處是代碼簡單，非常容易理解，除了要注意基準項不要放入到left和right，而是concat到結果即可。但是帶來的問題是要新建很多數組，所以這個方式並不是很優的方式。
2、標準遞歸版本。需要交換，無需新建數組。
圖3 標準遞歸版本
圖4 標準遞歸版本執行結果
這個版本好處是無需新建數組，而整個排序過程都是基於原數組的位置交換。其機制和排序過程與上一個方案基本類似(不同在於新方案的基準項可交換會，因此遞歸有時需要帶上基準項)，直到把所有分區都比較過後就表示已經排序完成。
其排序過程為：
- 先找到基準項，這裡以中間項表示，pivot=3。left表示最左側位置，i一開始取值left，right表示最右側位置,j取值為j, 因此i = 0, j = 4。
- 自左往右逐個查找大於基準項的數，同時自右往左逐個查找小於基準項的數，類似兩邊收攏朝中間查找，到基準項停止。當左側遇到大的數，右側遇到小的數字，將左右兩項交換，同時i增1位，j減1位，縮小範圍繼續查找，直到將全部小的數移到左側，大的數字移到右側。
- 上一趟交換完成之後，左側全部小於基準項，右側全部大於基準項。這時，將基準左側第1位到基準項-1項放入遞歸按照步驟1、2進行交換排序，再將基準右側第1項到最後項放入遞歸按照步驟1、2進行交換排序。在遞歸時，有時左側或者右側沒有可交換的項，這時就與基準項進行了交換，那需要將基準項位置一併傳入遞歸。
- 分區遞歸完成後排序完成。
3、非遞歸版本。需要交換，無需新建數組，利用stack或queue遍歷。
圖5 快速排序非遞歸版本
非遞歸版本基於標準遞歸版本，交換邏輯與排序規則完全一樣。所不同的是，將遞歸改為棧或隊列的循環。不同點是：
- 首先在交換排序的外循環加入一個stack，將初始的left,right添加進去
- 如果stack不為空，則將left與right取出，分別賦值給i和j。數組方法pop()表示從後開始取,shift()從前開始取。
- 在之前遞歸調用處，分別用push成員來替換。也就是當需要遞歸時說明要繼續交換循環，則給stack添加成員，讓循環繼續即可。中止條件是stack為空，也就是無需遞歸時結束。
總結
快速排序是一種相對巧妙的排序方式，相對選擇、插入、冒泡來講效率要高，也要稍微複雜一些。其交換過程也有點類似冒泡，但是不像冒泡兩兩逐個交換，而是根據基準值比較大小按需要來交換，然後遞歸分區排序，這樣以來交換就減少了。但快排並不穩定，如果遇到已排過序或全一樣的數字這種最壞情況那跟冒泡等一樣了。
PS：請對比之前關於選擇、插入、冒泡三種冒泡排序的文章。
閱讀更多 刀法如飛 的文章
關鍵字: JavaScript 快速 遞歸
