HTML5學堂-碼匠：前幾期“算法之旅”跟大家分享了冒泡排序法和選擇排序法，它們都屬于時間復雜度為O(n^2)的“慢”排序。今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法
—— 快速排序法 [ 平均時間復雜度為O (n logn) ]。

Tips 1：關于“算法”及“排序”的基礎知識，在此前“選擇排序法”中已詳細講解，可點擊文后的相關文章鏈接查看，在此不再贅述。
Tips 2：如果無特殊說明，本文的快速排序是從小到大的排序。

快速排序法的原理

快速排序是一種劃分交換排序，它采用分治的策略，通常稱其為分治法。

分治法

基本思想：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解決這些子問題，然后將這些子問題的結果組合成原問題的結果。

基本原理

從序列中任選一個數作為“基準”；
所有小于“基準”的數，都挪到“基準”的左邊；所有大于等于“基準”的數，都挪到“基準”的右邊；
在這次移動結束之后，該“基準”就處于兩個序列的中間位置，不再參與后續的排序；
針對“基準”左邊和右邊的兩個子序列，不斷重復上述步驟，直到所有子序列只剩下一個數為止。

原理圖解

現有一個序列為 [8, 4, 7, 2, 0, 3, 1]，如下演示快速排序法如何對其進行排序。

實現快速排序的步驟分解

選擇“基準”，并將其從原始數組分離

先獲取基準的索引值，再使用splice數組方法取出基準值。

Tips：該實例中， 基準的索引值 = parseInt（序列長度 / 2）
Tips：splice方法會改變原始數組。例如，arr = [1, 2, 3]; 基準索引值為1，基準值為2，原始數組變為arr = [1, 3];

遍歷序列，拆分序列

與“基準”比較大小，并拆分為兩個子序列
小于“基準”的數存儲于leftArr數組當中，大于等于“基準”的數存儲于rightArr數組當中

Tips：當然，也可以將 小于等于“基準”的數存于leftArr，大于“基準”的數存于rightArr
由于要遍歷序列，將每一個數與“基準”進行大小比較，所以，需要借助for語句來實現

遞歸調用，遍歷子序列并組合子序列的結果

定義一個函數，形參用于接收數組

function quickSort(arr) { };

實現遞歸調用遍歷子序列，用concat數組方法組合子序列的結果

判斷子序列的長度

遞歸調用的過程中，子序列的長度等于1時，則停止遞歸調用，返回當前數組。

快速排序法完整代碼

快速排序法的效率

時間復雜度

最壞情況：每一次選取的“基準”都是序列中最小的數/最大的數，這種情況與冒泡排序法類似（每一次只能確定一個數[基準數]的順序），時間復雜度為O（n^2）
最好情況：每一次選取的“基準”都是序列中最中間的一個數（是中位數，而不是位置上的中間），那么每次都把當前序列劃分成了長度相等的兩個子序列。這時候，第一次就有n/2、n/2兩個子序列，第二次就有n/4、n/4、n/4、n/4四個子序列，依此類推，n個數一共需要logn次才能排序完成（2^x=n，x=logn），然后每次都是n的復雜度，時間復雜度為O（n logn）

空間復雜度

最壞情況：需要進行n‐1 次遞歸調用，其空間復雜度為 O（n）
最好情況：需要logn次遞歸調用，其空間復雜度為O（logn）

算法的穩定性

快速排序是一種不穩定排序算法
例如：現有序列為[1, 0, 1, 3]，“基準”數字選擇為第二個1
在第一輪比較之后，變成了[0, 1, 1, 3]，左序列為[0]，右序列為[1, 3]（右序列的1是此前的第一個1）
不難發現，原序列的兩個1的先后順序被破壞了，改變了先后順序，自然就是“不穩定”的排序算法了

關于O

在此前的“冒泡排序法”一文當中，我們詳細講解過O是什么，在此就不多說了，直接上圖吧

相關文章鏈接

算法之旅 | 選擇排序法
算法之旅 | 冒泡排序法

開開心心每一天

生活艱辛，代碼不易，但，不要忘記微笑！

---