摘要：但是大家了解阮一峰快排事件嗎，是否知道快排的最佳實踐本文從一個爭執講起，通過生動詳實的例子讓你真正了解快排。參考文檔快速排序復雜度分析如何看待文章面試官阮一峰版的快速排序完全是錯的快速排序算法的優化思路總結

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

整個事件用一句話來概括，就是有人diss阮一峰的快排寫的不對，如下圖。其實從圖上也看到了，這個微博并沒有發酵起來，直到一篇發表在掘金上的文章《阮一峰版快速排序完全是錯的》（文章已經不能訪問），然后又被人提問到知乎上，整個事情才變得熱鬧了起來。Diss的主要點在于兩個：

一個是拿哨兵用的splice而不是數組下標

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

哨兵：快排中的被選中做為比較對象的基準元素

這件事情上，絕大多數同學都支持阮老師。其實，我覺得這種粗糙的批評是有問題的。有三個原因：

首先，在阮一峰的快排博客的評論里，他已經提到，splice確實是有問題的，見下圖。而且，即使使用了splice，時間復雜度也是O(n)+O(n)=O(n)，在量級上并沒有影響。

另外，快排在維基（中文|英文）的定義上只規定了時間復雜度，對于空間復雜度的定義是，

中文：根據實現的方式不同而不同
英文：O(n) auxiliary (naive) O(log n) auxiliary

所以用空間復雜度來攻擊算法是沒有依據的。另外，winter在上面知乎的問題中也提及，原地快排的空間復雜度因為不是尾遞歸必須用棧，空間復雜度是O(log(n))，而即使快排每次都用新的空間，也無非是O(2n)=O(n)而已。

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

阮老師的博客其實一直是通俗易懂的，我也把通俗易懂作為我自己一直的追求。這個算法可能不是沒有瑕疵，但是卻絕對稱不上錯。而我們做的也不是抨擊瑕疵，而是考慮還有哪些改進的方向。

阮老師的這個快排實現確實好記，包括我自己，就是通過阮老師的這個算法才算真正記住了快排。在這個基礎上，我覺得這個微博發的沒啥意義。

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

如果足夠理想，那我們期望每次都把數組都分成平均的兩個部分，如果按照這樣的理想情況分下去，我們最終能得到一個完全二叉樹。如果排序n個數字，那么這個樹的深度就是log2n+1，如果我們將比較n個數的耗時設置為T(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) 

而在最壞的情況下，這個樹是一個完全的斜樹，只有左半邊或者右半邊。這時候我們的比較次數就變為
=O(n的平方)

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

對于非原地排序，每次遞歸都要聲明一個總數為n的額外空間，所以空間復雜度變為原地排序的n倍，即最好情況下O(nlog2n)，最差情況下O(n的平方)

對于復雜度這塊還想了解更詳細內容的同學可以參考 《快速排序復雜度分析》

經過上面的部分，想必你對快排在前端的是是非非已經有了一個初步的了解。那么，什么是快排的最佳實踐呢？

這是阮一峰老師的算法實現的變體，因為用了es6的寫法，從而使得代碼量變得更加精簡，主體更加突出。

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));
}

這里貼一個winter的實現，想看更多的實現，可以移步大佬們在github上的互噴地址

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);
}

剛才也說到，快排其實是存在最差情況的。實際上，在日常工作中，如果真的有這樣大數據量級的優化需要，我們往往會根據實際情況對快排進行各種各樣的優化。

主要的思路有以下幾點[3]：

合理選擇哨兵，盡量避免出現斜樹

對于重復的元素，一次性的從排來

使用選擇排序來處理小數組（V8中設定為10）

使用堆排序來處理最壞情況的分區

用從兩邊向中間遍歷來代替從左向右遍歷

使用尾遞歸

在不同的線程中并發處理問題

因為本文實在有點長，這塊就不再做詳細的闡述，有需要的同學可以自行參閱《快速排序算法的優化思路總結》。

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

《快速排序復雜度分析》

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

《快速排序算法的優化思路總結》