摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時(shí)間復(fù)雜度為。快速排序法的原理快速排序是一種劃分交換排序，它采用分治的策略，通常稱其為分治法。

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

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

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

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

從序列中任選一個(gè)數(shù)作為“基準(zhǔn)”；
所有小于“基準(zhǔn)”的數(shù)，都挪到“基準(zhǔn)”的左邊；所有大于等于“基準(zhǔn)”的數(shù)，都挪到“基準(zhǔn)”的右邊；
在這次移動(dòng)結(jié)束之后，該“基準(zhǔn)”就處于兩個(gè)序列的中間位置，不再參與后續(xù)的排序；
針對(duì)“基準(zhǔn)”左邊和右邊的兩個(gè)子序列，不斷重復(fù)上述步驟，直到所有子序列只剩下一個(gè)數(shù)為止。

現(xiàn)有一個(gè)序列為 [8, 4, 7, 2, 0, 3, 1]，如下演示快速排序法如何對(duì)其進(jìn)行排序。

先獲取基準(zhǔn)的索引值，再使用splice數(shù)組方法取出基準(zhǔn)值。

Tips：該實(shí)例中， 基準(zhǔn)的索引值 = parseInt（序列長度 / 2）
Tips：splice方法會(huì)改變?cè)紨?shù)組。例如，arr = [1, 2, 3]; 基準(zhǔn)索引值為1，基準(zhǔn)值為2，原始數(shù)組變?yōu)閍rr = [1, 3];

與“基準(zhǔn)”比較大小，并拆分為兩個(gè)子序列
小于“基準(zhǔn)”的數(shù)存儲(chǔ)于leftArr數(shù)組當(dāng)中，大于等于“基準(zhǔn)”的數(shù)存儲(chǔ)于rightArr數(shù)組當(dāng)中

Tips：當(dāng)然，也可以將 小于等于“基準(zhǔn)”的數(shù)存于leftArr，大于“基準(zhǔn)”的數(shù)存于rightArr
由于要遍歷序列，將每一個(gè)數(shù)與“基準(zhǔn)”進(jìn)行大小比較，所以，需要借助for語句來實(shí)現(xiàn)

定義一個(gè)函數(shù)，形參用于接收數(shù)組

function quickSort(arr) { };

實(shí)現(xiàn)遞歸調(diào)用遍歷子序列，用concat數(shù)組方法組合子序列的結(jié)果

遞歸調(diào)用的過程中，子序列的長度等于1時(shí)，則停止遞歸調(diào)用，返回當(dāng)前數(shù)組。

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

最壞情況：需要進(jìn)行n‐1 次遞歸調(diào)用，其空間復(fù)雜度為 O（n）
最好情況：需要logn次遞歸調(diào)用，其空間復(fù)雜度為O（logn）

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

在此前的“冒泡排序法”一文當(dāng)中，我們?cè)敿?xì)講解過O是什么，在此就不多說了，直接上圖吧

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

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