大師級的文章，總是能夠使你更接近于事物的本質。 ? 最近看了pongba的數學之美番外篇：快排為什么那么快。文中提到了Mackay的一篇文章（這里是譯文），里面提到了使用信息論來解釋快排與堆排的速度差異的本質原因。看罷，內心有種莫名的激動。雖不懂信息論，但Mackay（大師畢竟是大師），最簡單的解釋，卻直接觸到了本質。有興趣的可以看看Mackay的這篇文章。這里，只是我自己的一點感悟。
信息熵是什么？
一個事件，它的信息量大小和它的不確定性有直接的關系。比如說，我們要搞清楚一件非常非常不確定的事，或是我們一無所知的事情，就需要了解大量的信息。相反，如果我們對某件事已經有了較多的了解，我們不需要太多的信息就能把它搞清楚。所以，從這個角度，我們可以認為，信息量的度量就等于不確定性的多少。? 我們把這個信息的度量叫做“熵”，熵越大表明這個事件的結果越難以預測，同時事件的發生將給我們帶來越多的信息。
大家都擲過硬幣。我們把擲（正常的）硬幣這個事件的熵看做是1bit，為什么把一次比較的結果看成是1bit的信息呢？
可以這么解釋： 一個拋硬幣 正反各 1/2 概率。 如果信號源是這個， 所含有的信息量就是 - 1/2 * log (1/2)?+ -1/2 * log(1/2) = 1 bit 。
所以, 一個能生成 1/2、 1/2 概率（等概率）分布的信號所含的信息量就是 1bit 。比較就是這樣的運算, 看作 cmp(a, b) 看作是拋硬幣. 每次返回的是1個 bit。?有人會質疑，因為有時候要滿足序的性質, ?如 a>b, b>c 則 a>c 導致第三次問 cmp(a, c) 的時候不能以 1/2 1/2 的?概率生成隨機信號. 其實， 一個好的排序算法就是避免使用了 cmp(a, b) cmp(b, c) 得到 a>b b>c 后還比較一次 a,?c. 最佳的排序算法, 就是每次都能從 cmp 得到1bit 的信息。
但是，如果這個硬幣被做過手腳，使得正面的概率大于反面的概率（或者反相反），那么這個事件的熵將<1bit。因為，我們對于結果的情況已經有所知道，顯然，得到的信息也就少了。 更極端的情況，如果這個硬幣是兩個正面（或者相反），那么這個事件的熵將為0 bit，因為，我們完全知道結果是怎么樣的。 1、排序與信息熵
為什么可以將信息論延伸到（基于比較的）排序？
熵是信息科學中的一個重要概念, 用來表示事物的不確定性. 排序就是使序列從無序到有序的過程, 無序就是不確定性, 因此可以用信息熵的概念來描述序列的無序程度,進而研究基于比較的排序算法的效率。
所以，想讓基于比較的排序更快，等價于讓每次比較的信息熵達到最大。所以，讓每次比較的結果概率相等（使得每次比較的信息熵接近1bit），這是算法改進的核心思想。
給出一個題目：有5個數，最少需要幾次比較，來實現數據的排序？
設序列S 長度為n, 則該系列共有x = n!種不同的排列, 若將該序列看做信源的輸出, 設每種排列出現的概率相同, 則根據離散隨機變量的信息熵的定義, 序列S 的平均信息量, 即信息熵定義為： Hn = l(x ) = log2(x ) =log2n! (bit)
5個整數，產生的全排列有?5!=120?種，從信息論的角度，信息量就是log2{120} = 6.90689059560852 bit，而兩個數比較一次，最多可以產生1bit的信息量，所以7次比較幾乎就是極限了。 ? ?? 當然這不是說你比較7次就可以得出排序結果的，而是當你嘗試了無數次之后，發現，7次是它的極限次數。 ? 下面，我們來看看，運用每次比較得到的信息熵接近于1bit的思想，來具體的實現，上訴的排序過程：
??? 設原序列由(a, b, c, d , e ) 5 個元素組成, ??? 首先分別對(a, b) 和(c, d ) 進行排序, 設排序結果分別為[a b ] 和[ c d ] ( [ x y ] 表示已排序) (對于其他排序結果, 以下分析過程相同) , 顯然這一步需要2 次比較. ??? 然后比較a 與c, 若a < c, 則排序結果為[a c d ], 用折半插入法經過2 次比較將e 插入到[ac d ] 當中, ??? 最后將b 插入到已排序的序列, 由于已知b > a, 所以用折半插入法插入b, 最壞情況下只需要2 次比較. 若a > c, 排序結果為[ c a b ], 同樣用折半插入法經2 次比較將e 插入, 由于c 已與d比較過, 因此最后將d 插入到已排序的序列最多也只需要2 次比較. ??? 綜上, 整個排序過程最多只需要7次比較. 第一步a 與b 及c 與d 的比較顯然各減少1 bit 信息熵, 此時序列還有30 種不同的排列, 剩余的信息熵為4. 9069 b it. a 與c 比較后, 序列還剩15 種排列, 剩余的信息熵為3. 9069 b it, 所以這次比較也減少信息熵1 bit. 插入e 后, 若e < a, 序列可能出現3 種排列, 若e > a, 則有16 種可能的排列, 因此其平均信息熵為： 所以2 次比較減少信息熵1.9724 bit, 最后2 次比較減少1.9345 bit. 可見每次比較減少信息熵接近1 bit, 因此排序效率達到最高。 ? 2、冒泡、選擇、插入，為什么那么慢？ ? 首先我們來看三種經典的平方復雜度算法。它們的效率并不高，原因就在于算法過程中會出現越來越多概率嚴重不均的比較。 1、冒泡 隨著冒泡排序的進行，整個序列將變得越來越有序，位置顛倒的泡泡將越來越少； 2、選擇排序 選擇排序的每一趟選擇中，你都會不斷得到越來越大的數，同時在以后的比較中找到更大的數的概率也越來越低； 3、插入排序 在插入排序中，你總是把新的數與已經排好的數按從大到小的順序依次進行比較，可以想到新的數一開始就比前面所有的數中最大的那個還大的概率是相當小的。受此啟發，我們可以很自然地想到一個插入排序的改進：處理一個新的數時，為何不一開始就與前面處理過的數中的中位數進行比較？這種比較的熵顯然更大，能獲取的信息量要大得多，明顯更有價值一些。這就是插入排序的二分查找改進。
3、快排為什么那么快？ ? ??? 快速排序算法中，比較的信息熵不會因為排序算法的進行而漸漸減小，這就是快速排序比上面幾個排序算法更優秀的根本原因。 ??? 仔細回顧快速排序算法的過程，我們可以看出，每次比較的兩種結果出現的概率完全由這一趟劃分過程所選擇的基準關鍵字決定：如果選擇的基準關鍵字剛好是當前處理的數字集合的中位數，則比較結果的不確定性達到最大（一次比較的信息熵達到1bit）。這個時候，快排的比較次數，也就等于排序所需要的總信息熵：log2n! (bit)?這也正是快排的時間復雜度。 ? 4、快排又為不那么快？ 如果選擇的基準關鍵字過大或過小，都會出現比較產生的結果不均等的情況，這使得每次比較平均帶來的信息量大大減少。 比如：選擇的主元為最小值，那么跟這個主元進行的比較得到的信息熵為0bit。因為，每次的結果都是肯定的。 ? 看看主元隨機時候的情況：

當主元隨機選擇的時候：我們不妨令軸元素為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！

這就是快排也不那么快的原因，它不能保證每次比較結果的概率都是相同的（1/2 ：1/2），因此，每次比較的信息熵不是都=1bit。

?

如果你想改進快排，那么可以試試把精力放在提高每次比較的信息熵。

from:?http://blog.csdn.net/cyh_24/article/details/8120045

總結

以上是生活随笔為你收集整理的快排Quick Sort到底有多快？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。