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

www.zhouhua.site

原回答：

為什麼自己寫的qsort比不上C語言庫里自帶的qsort效率高？?

www.zhihu.com

快速排序水很深啊。我不貼代碼，主要講講優化思路和手段吧。

1. 合理選擇pivot

你就直接選擇分區的第一個或最後一個元素做 pivot 肯定是不合適的。對於已經排好序，或者接近排好序的情況，會進入最差情況，時間複雜度衰退到 。

pivot選取的理想情況是：讓分區中比 pivot 小的元素數量和比 pivot 大的元素數量差不多。較常用的做法是三數取中（ midian of three ），即從第一項、最後一項、中間一項中取中位數作為 pivot。當然這並不能完全避免最差情況的發生。所以很多時候會採取更小心、更嚴謹的 pivot 選擇方案（對於大數組特別重要）。比如先把大數組平均切分成左中右三個部分，每個部分用三數取中得到一個中位數，再從得到的三個中位數中找出中位數。

我在 javascript v8 引擎中看到了另外一種選擇 pivot 的方式：認為超過1000項的數組是大數組，每隔200左右（不固定）選出一個元素，從這些元素中找出中位數，再加入首尾兩個元素，從這個三個元素中找出中位數作為 pivot。

By the way，現實環境中，你要對一個預先有一定順序的數組做排序的需求太太太普遍了，這個優化必須要有。

2. 更快地分區

我看到題主的做法是從左向右依次與 pivot 比較，做交換，這樣做其實效率並不高。舉個簡單的例子，一個數組 [2, 1, 3, 1, 3, 1, 3]，選第一個元素作為 pivot，如果按題主的方式，每次發現比2小的數會引起一次交換，一共三次。然而，直觀來說，其實只要將第一個3和最後一個1交換就可以達到這三次交換的效果。所以更理想的分區方式是從兩邊向中間遍歷的雙向分區方式。實現的話你可以參考樓上 @林麵包的實現。

3. 處理重複元素的問題

假如一個數組裡的元素全部一樣大（或者存在大量相同元素），會怎麼樣？這是一個邊界 case，但是會令快速排序進入最差情況，因為不管怎麼選 pivot，都會使分區結果一邊很大一邊很小。那怎麼解決這個問題呢？還是修改分區過程，思路跟上面說的雙向分區類似，但是會更複雜，我們需要小於 pivot、等於 pivot、大於 pivot 三個分區。既然說了不貼代碼，那就點到為止吧，有興趣可以自己找別人實現看看。

4. 優化小數組效率

這一點很多人都提到了。為什麼要優化小數組？因為對於規模很小的情況，快速排序的優勢並不明顯（可能沒有優勢），而遞歸型的演算法還會帶來額外的開銷。於是對於這類情況可以選擇非遞歸型的演算法來替代。好，那就有兩個問題：多小的數組算小數組？替換的演算法是什麼？

通常這個閾值設定為16（ v8 中設定的是10），替換的演算法一般是選擇排序。據說閾值的設定是要考慮更好地利用 cpu 緩存，這個問題我就不是很清楚了，不深入。同樣，對於分區得到的小數組是要立刻進行選擇排序，還是等分區全部結束了之後，再統一進行選擇排序，這個問題也會存在一定的緩存命中的區別，我也不懂，不深入。

5. 監控遞歸過程

這裡我要說的是內省排序。想想看，我們已經做了一些努力來避免快速排序演算法進入最壞的情況。但事實上可能並不如我們想像地那麼理想。理想情況下，快速排序演算法的遞歸嘗試會到多深呢？這個很好回答： 。好，如果現在遞歸深度已經到了 ，我會覺得很正常，畢竟不太可能每次都是最好情況嘛；那如果此時遞歸深度達到 呢？我想你應該慌了，比理想情況遞歸深了一倍還沒有結束。而此時，我覺得可以認為可能已經進入最差情況了，繼續使用快速排序只會更遭，可以考慮對這個分區採用其他排序演算法來處理。通常我們會使用堆排序。為啥要用堆排序？因為它的平均和最差時間複雜度都是 。這就是內省排序的思想。

6. 優化遞歸

我想先說明一點：內省排序雖然會避免遞歸過深，但它的目的並不是為了優化遞歸。

在分區過程中，我們其實是把一個大的問題分解成兩個小一點的問題分別處理。這時我們需要考慮一下，這兩個小問題哪個更小。先處理更小規模的問題，再處理更大規模的問題，這樣可以減小遞歸深度，節約棧開銷。

樓上也有人提到了尾遞歸。對於支持尾遞歸的語言，自然是極好的，小規模的問題先遞歸，減少遞歸深度，大規模的問題直接通過尾遞歸優化掉，不進入遞歸棧。

然而並不是所有的語言都支持尾遞歸 ⊙︿⊙，比如 python（據說）和 javascript。在 javascript 的 v8 引擎中，我看到它是用一個循環變相手動實現了一個與尾遞歸效果一樣的優化，棒棒噠。

7. 並行

既然快速排序演算法是典型的分治演算法，那麼對於分解下來的小問題是可以在不同的線程中並行處理的。當然對於 javascript 還是不適用，嗯，我是做前端的。