數學之美番外篇：快排為什么那樣快

By 劉未鵬(pongba)

C++的羅浮宮( http://blog.csdn.net/pongba )

TopLanguage( http://groups.google.com/group/pongba )

目錄

0. 前言

1. 猜數字

2. 稱球

3. 排序

3.1 為什么堆排比快排慢

3.2 為什么快排其實也不是那么快

3.3 基排又為什么那么快呢

4. 信息論！信息論？

5. 小結

0. 前言

知道這個理論是在 TopLanguage 上的一次討論，先是g9 轉了David MacKay的一篇文章 ，然后引發了牛人們的 一場關于信息論的討論 。Anyway，正如g9很久以前在 Blog 里面所 說 的：

有時無知是福。俺看到一點新鮮的科普也能覺得造化神奇。剛才讀Gerald Jay Sussman（ SICP 作者）的文章， Building Robust Systems – an essay ，竟然心如小鹿亂撞，手心濕潤，仿佛第一次握住初戀情人溫柔的手。

而看到 MacKay 的這篇文章我也有這種感覺——以前模糊的東西忽然有了深刻的解釋，一切頓時變得明白無比。原來看問題的角度或層面能夠帶來這么大的變化。再一次印證了越是深刻的原理往往越是簡單和強大。所以說，土鱉也有土鱉的幸福:P

這篇文章相當于MacKay 原文 的白話文版。MacKay在原文中用到了信息論的知識，后者在我看來并不是必須的，盡管計算的時候方便，但與本質無關。所以我用大白話解釋了一通。

1. 猜數字

我們先來玩一個猜數字游戲：我心里默念一個1~64之間的數，你來猜（你只能問答案是“是”或“否”的問題）。為了保證不論在什么情況下都能以盡量少的次數猜中，你應該采取什么策略呢？很顯然，二分。先是猜是不是位于1~32之間，排除掉一半可能性，然后對區間繼續二分。這種策略能夠保證無論數字怎么跟你捉迷藏，都能在log_2{n}次以內猜中。用算法的術語來說就是它的下界是最好的。

我們再來回顧一下這個游戲所蘊含的本質：為什么這種策略具有最優下界？答案也很簡單，這個策略是平衡的。反之如果策略不是平衡的，比如問是不是在1~10之間，那么一旦發現不是在1~10之間的話就會剩下比N/2更多的可能性需要去考察了。

徐宥 在討論中提到，這種策略的本質可以概括成“讓未知世界無機可乘”。它是沒有“弱點的”， 答案的任何一個分支都是等概率的 。反之，一旦某個分支蘊含的可能性更多，當情況落到那個分支上的時候你就郁悶了。比如猜數字游戲最糟糕的策略就是一個一個的猜：是1嗎？是2嗎？... 因為這種猜法最差的情況下需要64次才能猜對，下界非常糟糕。二分搜索為什么好，就是因為它每次都將可能性排除一半并且 無論如何 都能排除一半（它是最糟情況下表現最好的）。

2. 稱球

12個小球，其中有一個是壞球。有一架天平。需要你用最少的稱次數來確定哪個小球是壞的并且它到底是輕還是重。

這個問題是一道流傳已久的智力題。網絡上也有很多講解，還有泛化到N個球的情況下的嚴格證明。也有零星的一些地方提到從信息論的角度來看待最優解法。本來我一直認為這道題目除了試錯之外沒有其它高妙的思路了，只能一個個方法試，并盡量從結果中尋找信息，然后看看哪種方案最少。

然而，實際上它的確有其它的思路，一個更本質的思路，而且根本用不著信息論這么拗口的知識。

我們先回顧一下猜數字游戲。為了保證任何情況下以最少次數猜中，我們的策略是每次都排除恰好一半的可能性。類比到稱球問題上：壞球可能是12個球中的任意一個，這就是12種可能性；而其中每種可能性下壞球可能輕也可能重。于是“壞球是哪個球，是輕是重”這個問題的答案就有12×2=24種可能性?，F在我們用天平來稱球，就等同于對這24種可能性發問，由于天平的輸出結果有三種“平衡、左傾、右傾”，這就相當于我們的問題有三個答案，即可以將所有的可能性切成三份，根據猜數字游戲的啟發，我們應當盡量讓這三個分支概率均等，即平均切分所有的可能性為三等份。如此一來的話一次稱量就可以將答案的可能性縮減為原來的1/3，三次就能縮減為1/27。而總共才有24種可能性，所以理論上是完全可以3次稱出來的。

如何稱的指導原則有了，構造一個稱的策略就不是什么太困難的事情了。首先不妨解釋一下為什么最直觀的稱法不是最優的——6、6稱：在6、6稱的時候，天平平衡的可能性是0。剛才說了，最優策略應該使得天平三種狀態的概率均等，這樣才能三等分答案的所有可能性。

為了更清楚的看待這個問題，我們不妨假設有6個球，來考慮一下3、3稱和2、2稱的區別：

在未稱之前，一共有12種可能性：1輕、1重、2輕、2重、...、6輕、6重?，F在將1、2、3號放在左邊，4、5、6放在右邊3、3稱了之后，不失一般性假設天平左傾，那么小球的可能性就變成了原來的一半（6種）：1重、2重、3重、4輕、5輕、6輕。即這種稱法能排除一半可能性。

現在再來看2、2稱法，即1、2放左邊，3、4放右邊，剩下的5、6不稱，放一邊。假設結果是天平平衡，那么可能性剩下——4種：5重、5輕、6重、6輕。假設天平左傾，可能性也剩下4種：1重、2重、3輕、4輕。右傾和左傾的情況類似?？傊?，這種稱法，不管天平結果如何，情況都被我們縮小到了原來的三分之一！我們充分利用了“天平的結果狀態可能有三種”這個條件來三等分所有可能性，而不是二等分。

說到這里，剩下的事情就實在很簡單了：第二步稱法，只要記著這樣一個指導思想——你選擇的稱法必須使得當天平平衡的時候答案剩下的可能性和天平左傾（右傾）的時候答案剩下的可能性一樣多。實際上，這等同于你得選擇一種稱法，使得天平輸出三種結果的概率是均等的，因為天平輸出某個結果的概率就等同于所有支持這個結果（左傾、右傾、平衡）的答案可能性的和，并且答案的每個可能性都是等概率的。

MacKay在他的書《Information Theory: Inference and Learning Algorithms》（ 作者開放免費電子書 ）里面4.1節專門講了這個稱球問題，還畫了一張不錯的圖，我就照抄了：

圖中“1+”是指“1號小球為重”這一可能性。一開始一共有24種可能性。4、4稱了之后不管哪種情況（分支），剩下來的可能性總是4種。這是一個完美的三分。然后對每個分支構造第二次稱法，這里你只要稍加演算就可以發現，分支1上的第二次稱法，即“1、2、6對3、4、5”這種稱法，天平輸出三種結果的可能性是均等的（嚴格來說是幾乎均等）。這就是為什么這個稱法能夠在最壞的情況下也能表現最好的原因，沒有哪個分支是它的弱點，它必然能將情況縮小到原來的1/3。

3. 排序

用前面的看問題視角，排序的本質可以這樣來表述：一組未排序的N個數字，它們一共有N!種重排，其中只有一種排列是滿足題意的（譬如從大到小排列）。換句話說，排序問題的可能性一共有N!種。任何基于比較的排序的基本操作單元都是“比較a和b”，這就相當于猜數字游戲里面的一個問句，顯然這個問句的答案只能是“是”或“否”，一個只有兩種輸出的問題最多只能將可能性空間切成兩半，根據上面的思路，最佳切法就是切成1/2和1/2。也就是說，我們希望在比較了a和b的大小關系之后，如果發現a<b的話剩下的排列可能性就變成N!/2，如果發現a>b也是剩下N!/2種可能性。由于假設每種排列的概率是均等的，所以這也就意味著支持a<b的排列一共有N!/2個，支持a>b的也是N!/2個，換言之，a<b的概率等于a>b的概率。

我們希望每次在比較a和b的時候，a<b和a>b的概率是均等的，這樣我們就能保證無論如何都能將可能性縮小為原來的一半了！最優下界。

一個直接的推論是，如果每次都像上面這樣的完美比較，那么N個元素的N!種可能排列只需要log_2{N!}就排查玩了，而log_2{N!}近似于NlogN。這正是快排的復雜度。

3.1 為什么堆排比快排慢

回顧一下堆排的過程：

1. 建立最大堆（堆頂的元素大于其兩個兒子，兩個兒子又分別大于它們各自下屬的兩個兒子... 以此類推）

2. 將堆頂的元素和最后一個元素對調（相當于將堆頂元素（最大值）拿走，然后將堆底的那個元素補上它的空缺），然后讓那最后一個元素從頂上往下滑到恰當的位置（重新使堆最大化）。

3. 重復第2步。

這里的關鍵問題就在于第2步，堆底的元素肯定很小，將它拿到堆頂和原本屬于最大元素的兩個子節點比較，它比它們大的可能性是微乎其微的。實際上它肯定小于其中的一個兒子。而大于另一個兒子的可能性非常小。于是，這一次比較的結果就是概率不均等的，根據前面的分析，概率不均等的比較是不明智的，因為它并不能保證在糟糕情況下也能將問題的可能性削減到原本的1/2。可以想像一種極端情況，如果a肯定小于b，那么比較a和b就會什么信息也得不到——原本剩下多少可能性還是剩下多少可能性。

在堆排里面有大量這種近乎無效的比較，因為被拿到堆頂的那個元素幾乎肯定是很小的，而靠近堆頂的元素又幾乎肯定是很大的，將一個很小的數和一個很大的數比較，結果幾乎肯定是“小于”的，這就意味著問題的可能性只被排除掉了很小一部分。

這就是為什么堆排比較慢（堆排雖然和快排一樣復雜度都是O(NlogN)但堆排復雜度的常系數更大）。

MacKay也提供了一個修改版的堆排：每次不是將堆底的元素拿到上面去，而是直接比較堆頂（最大）元素的兩個兒子，即選出次大的元素。由于這兩個兒子之間的大小關系是很不確定的，兩者都很大，說不好哪個更大哪個更小，所以這次比較的兩個結果就是概率均等的了。具體參考 這里 。

3.2 為什么快排其實也不是那么快

我們考慮快排的過程：隨機選擇一個元素做“軸元素”，將所有大于軸元素的移到左邊，其余移到右邊。根據這個過程，快排的第一次比較就是將一個元素和軸元素比較，這個時候顯而易見的是，“大于”和“小于”的可能性各占一半。這是一次漂亮的比較。

然而，快排的第二次比較就不那么高明了：我們不妨令軸元素為pivot，第一次比較結果是a1<pivot，那么可以證明第二次比較a2也小于pivot的可能性是2/3！這容易證明：如果a2>pivot的話，那么a1，a2，pivot這三個元素之間的關系就完全確定了——a1<pivot<a2，剩下來的元素排列的可能性我們不妨記為P（不需要具體算出來）。而如果a2<pivot呢？那么a1和a2的關系就仍然是不確定的，也就是說，這個分支里面含有兩種情況：a1<a2<pivot，以及a2<a1<pivot。對于其中任一種情況，剩下的元素排列的可能性都是P，于是這個分支里面剩下的排列可能性就是2P。所以當a2<pivot的時候，還剩下2/3的可能性需要排查。

再進一步，如果第二步比較果真發現a2<pivot的話，第三步比較就更不妙了，模仿上面的推理，a3<pivot的概率將會是3/4！

這就是快排也不那么快的原因，因為它也沒有做到每次比較都能將剩下的可能性砍掉一半。

3.3 雞排為什么又那么快呢？

傳統的解釋是： 基排 不是基于比較的，所以不具有后者的局限性。話是沒錯，但其實還可以將它和基于比較的排序做一個類比。

基排的過程也許是源于我們理順一副牌的過程：如果你有N（N<=13）張牌，亂序，如何理順呢？我們假象桌上有十三個位置，然后我們將手里的牌一張一張放出去，如果是3，就放在位置3上，如果是J，就放在位置11上，放完了之后從位置1到位置13收集所有的牌（沒有牌的位置上不收集任何牌）。

我們可以這樣來理解基排高效的本質原因：假設前i張牌都已經放到了它們對應的位置上，第i+1張牌放出去的時候，實際上就相當于“一下子”就確立了它和前i張牌的大小關系，用O(1)的操作就將這張牌正確地插入到了前i張牌中的正確位置上，這個效果就相當于插入排序的第i輪原本需要比較O(i)次的，現在只需要O(1)了。

但是，為什么基排能夠達到這個效果呢？上面只是解釋了過程，解釋了過程不代表解釋了本質。

當i張牌放到位之后，放置第i+1張牌的時候有多少種可能性？大約i+1種，因為前i張牌將13個位置分割成了i+1個區間——第i+1張牌可以落在任意一個區間。所以放置第i+1張牌就好比是詢問這樣一個問題：“這張牌落在哪個區間呢？”而這個問題的答案有i+1種可能性？所以它就將剩下來的可能性均分成了i+1份（換句話說，砍掉了i/i+1的可能性?。Ｔ倏纯椿诒容^的排序吧：由于每次比較只有兩種結果，所以最多只能將剩下的可能性砍掉一半。

這就是為什么基排要快得多。而所有基于比較的排序都逃脫不了NlogN的宿命。

4. 信息論！信息論？

本來呢，MacKay寫那篇文章是想用信息論來解釋為什么堆排慢，以及為什么快排也慢的。MacKay在他的文章中的解釋是，只有提出每種答案的概率都均等的問題，才能獲得最大信息量。然而，仔細一想，其實這里信息論并不是因，而是果。這里不需要用信息論就完全能夠解釋，而且更明白。信息論只是對這個解釋的一個形式化。當然，信息論在其它地方還是有應用的。但這里其實用不著信息論這么重量級的東西（也許具體計算一些數據的時候是需要的），而是只需要一種看問題的本質視角：將排序問題看成和猜數字一樣，是通過問問題來縮小/排除（narrow down）結果的可能性區間，這樣一來，就會發現，“最好的問題”就是那些能夠均分所有可能性的問題，因為那樣的話不管問題的答案如何，都能排除掉k-1/k（k為問題的答案有多少種輸出——猜數字里面是2，稱球里面是3）種可能性，而不均衡的問題總會有一個或一些答案分支排除掉的可能性要小于k-1/k。于是策略的下界就被拖累了。

5. 小結

這的確是“小結”，因為兩點：

1. 這個問題可以有信息論的理論解釋，而信息論則是一個相當大的領域了。

2. 文中提到的這種看問題的視角除了用于排序、稱球，還能夠運用到哪些問題上（比如搜索）。

Update(06/13/2008) : 徐宥 在討論中 繼續提到 ：

另外，這幾天我重新把TAOCP 第三卷(第二版)翻出來看了看 Knuth 怎么說這個問題的, 發現真是牛大了：

先說性能：

pp148, section 5.2.3 說：

When N = 1000, the approximate average runiing time on MIX are 160000u for heapsort 130000u for shellsort 80000u for quicksort

這里, Knuth 同學發現一般情況下 heapsort 表現很不好. 于是，在下文他就說，習題18 (pp156, 難度21)

(R.W.Floyd) During the selection phase of heapsort, the key K tends to be quite small, so that nearly all the comparisons in step H6 find K<K_j. Show how to modify the algorithm so that K is not compared with K_j in the main loop of the computation, thereby nearly cutting the average number of comparisons in half.

答案里面的方法和DMK的方法是一樣的。(我覺得DMK是看了這個論文或者TAoCP的) 這里說 by half，就正好和快排差不多了。

再說信息論分析：

在5.3.1 (pp181) 高爺爺就說, “排序問題可以看成是一個樹上的鳥兒排排站的問題. (還特地畫了一棵樹), 下一段就說, 其實這個也 有等價說法, 就是信息論, 我們從稱球問題說起...”

然后后面一直講信息論和最小比較排序...

高爺爺真不愧是姓高的，囧rz..

數學之美番外篇：快排為什么那樣快