摘要：但是大家了解阮一峰快排事件嗎，是否知道快排的最佳實(shí)踐本文從一個(gè)爭(zhēng)執(zhí)講起，通過(guò)生動(dòng)詳實(shí)的例子讓你真正了解快排。參考文檔快速排序復(fù)雜度分析如何看待文章面試官阮一峰版的快速排序完全是錯(cuò)的快速排序算法的優(yōu)化思路總結(jié)

只要是個(gè)工程師，就或多或少的知道快排，其中很多人都能輕松的寫(xiě)出一個(gè)快排的實(shí)現(xiàn)。但是大家了解阮一峰快排事件嗎，是否知道快排的最佳實(shí)踐？本文從一個(gè)爭(zhēng)執(zhí)講起，通過(guò)生動(dòng)詳實(shí)的例子讓你真正了解快排。嗯，這確實(shí)是一篇炒冷飯的文章，但我希望能把冷飯炒成好吃的蛋炒飯。閑話(huà)少敘，馬上開(kāi)始~

整個(gè)事件用一句話(huà)來(lái)概括，就是有人diss阮一峰的快排寫(xiě)的不對(duì)，如下圖。其實(shí)從圖上也看到了，這個(gè)微博并沒(méi)有發(fā)酵起來(lái)，直到一篇發(fā)表在掘金上的文章《阮一峰版快速排序完全是錯(cuò)的》（文章已經(jīng)不能訪(fǎng)問(wèn)），然后又被人提問(wèn)到知乎上，整個(gè)事情才變得熱鬧了起來(lái)。Diss的主要點(diǎn)在于兩個(gè)：

一個(gè)是拿哨兵用的splice而不是數(shù)組下標(biāo)

一個(gè)是算法使用的是額外空間而不是原地分割

哨兵：快排中的被選中做為比較對(duì)象的基準(zhǔn)元素

這件事情上，絕大多數(shù)同學(xué)都支持阮老師。其實(shí)，我覺(jué)得這種粗糙的批評(píng)是有問(wèn)題的。有三個(gè)原因：

首先，在阮一峰的快排博客的評(píng)論里，他已經(jīng)提到，splice確實(shí)是有問(wèn)題的，見(jiàn)下圖。而且，即使使用了splice，時(shí)間復(fù)雜度也是O(n)+O(n)=O(n)，在量級(jí)上并沒(méi)有影響。

另外，快排在維基（中文|英文）的定義上只規(guī)定了時(shí)間復(fù)雜度，對(duì)于空間復(fù)雜度的定義是，

中文：根據(jù)實(shí)現(xiàn)的方式不同而不同
英文：O(n) auxiliary (naive) O(log n) auxiliary

所以用空間復(fù)雜度來(lái)攻擊算法是沒(méi)有依據(jù)的。另外，winter在上面知乎的問(wèn)題中也提及，原地快排的空間復(fù)雜度因?yàn)椴皇俏策f歸必須用棧，空間復(fù)雜度是O(log(n))，而即使快排每次都用新的空間，也無(wú)非是O(2n)=O(n)而已。

當(dāng)然，若是極端情況下（哨兵每次都把數(shù)組分成n-1和1個(gè)）阮老師的算法中空間復(fù)雜度會(huì)退化成O(n的平方)，不過(guò)這種情況是非原地快排的通病，而不是阮式算法的特例，所以也不能怪到阮老師頭上。

阮老師的博客其實(shí)一直是通俗易懂的，我也把通俗易懂作為我自己一直的追求。這個(gè)算法可能不是沒(méi)有瑕疵，但是卻絕對(duì)稱(chēng)不上錯(cuò)。而我們做的也不是抨擊瑕疵，而是考慮還有哪些改進(jìn)的方向。

阮老師的這個(gè)快排實(shí)現(xiàn)確實(shí)好記，包括我自己，就是通過(guò)阮老師的這個(gè)算法才算真正記住了快排。在這個(gè)基礎(chǔ)上，我覺(jué)得這個(gè)微博發(fā)的沒(méi)啥意義。

前面我們BB了半天阮一峰快排事件，中間我們多次提到了快排的時(shí)間復(fù)雜度和空間復(fù)雜度，在本部分，我們將分析為什么它們是這樣的。

如果足夠理想，那我們期望每次都把數(shù)組都分成平均的兩個(gè)部分，如果按照這樣的理想情況分下去，我們最終能得到一個(gè)完全二叉樹(shù)。如果排序n個(gè)數(shù)字，那么這個(gè)樹(shù)的深度就是log2n+1，如果我們將比較n個(gè)數(shù)的耗時(shí)設(shè)置為T(mén)(n)，那我們可以得到如下的公式[1]：

T(n) ≤ 2T(n/2) + n，T(1) = 0  
T(n) ≤ 2(2T(n/4)+n/2) + n = 4T(n/4) + 2n  
T(n) ≤ 4(2T(n/8)+n/4) + 2n = 8T(n/8) + 3n  
......
T(n) ≤ nT(1) + (log2n)×n = O(nlogn) 

而在最壞的情況下，這個(gè)樹(shù)是一個(gè)完全的斜樹(shù)，只有左半邊或者右半邊。這時(shí)候我們的比較次數(shù)就變?yōu)?br>=O(n的平方)

原地快排的空間占用是遞歸造成的?？臻g的使用，最好情況下是遞歸log2n次，所以空間復(fù)雜度為O(log2n)，最壞情況下是遞歸n-1次，所以空間復(fù)雜度是O(n)。

對(duì)于非原地排序，每次遞歸都要聲明一個(gè)總數(shù)為n的額外空間，所以空間復(fù)雜度變?yōu)樵嘏判虻膎倍，即最好情況下O(nlog2n)，最差情況下O(n的平方)

對(duì)于復(fù)雜度這塊還想了解更詳細(xì)內(nèi)容的同學(xué)可以參考 《快速排序復(fù)雜度分析》

經(jīng)過(guò)上面的部分，想必你對(duì)快排在前端的是是非非已經(jīng)有了一個(gè)初步的了解。那么，什么是快排的最佳實(shí)踐呢？

這是阮一峰老師的算法實(shí)現(xiàn)的變體，因?yàn)橛昧?b>es6的寫(xiě)法，從而使得代碼量變得更加精簡(jiǎn)，主體更加突出。

function quickSortRecursion (arr) {
  if (!arr || arr.length < 2) return arr;
  const pivot = arr.pop();
  let left = arr.filter(item => item < pivot);
  let right = arr.filter(item => item >= pivot);
  return quickSortRecursion(left).concat([pivot], quickSortRecursion(right));
}

這里貼一個(gè)winter的實(shí)現(xiàn)，想看更多的實(shí)現(xiàn)，可以移步大佬們?cè)趃ithub上的互噴地址

function wintercn_qsort(arr, start, end){
    var midValue = arr[start];
    var p1 = start, p2 = end;
    while(p1 < p2) {
        swap(arr, p1, p1 + 1);
        while(compare(arr[p1], midValue) >= 0 && p1 < p2) {
            swap(arr, p1, p2--);
        }
        p1 ++;
    }
    if(start < p1 - 1) 
        wintercn_qsort(arr, start, p1 - 1);
    if(p1 < end) 
        wintercn_qsort(arr, p1, end);
}

剛才也說(shuō)到，快排其實(shí)是存在最差情況的。實(shí)際上，在日常工作中，如果真的有這樣大數(shù)據(jù)量級(jí)的優(yōu)化需要，我們往往會(huì)根據(jù)實(shí)際情況對(duì)快排進(jìn)行各種各樣的優(yōu)化。

主要的思路有以下幾點(diǎn)[3]：

合理選擇哨兵，盡量避免出現(xiàn)斜樹(shù)

對(duì)于重復(fù)的元素，一次性的從排來(lái)

使用選擇排序來(lái)處理小數(shù)組（V8中設(shè)定為10）

使用堆排序來(lái)處理最壞情況的分區(qū)

用從兩邊向中間遍歷來(lái)代替從左向右遍歷

使用尾遞歸

在不同的線(xiàn)程中并發(fā)處理問(wèn)題

因?yàn)楸疚膶?shí)在有點(diǎn)長(zhǎng)，這塊就不再做詳細(xì)的闡述，有需要的同學(xué)可以自行參閱《快速排序算法的優(yōu)化思路總結(jié)》。

本文從阮一峰快排事件入手，分析了快排在不同情況下的空間復(fù)雜度和時(shí)間復(fù)雜度，并給出了快排的最佳實(shí)踐和優(yōu)化方法。希望能對(duì)大家了解快排有所幫助。

《快速排序復(fù)雜度分析》

《如何看待文章《面試官：阮一峰版的快速排序完全是錯(cuò)的》？》

《快速排序算法的優(yōu)化思路總結(jié)》