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

當(dāng)主元隨機(jī)選擇的時(shí)候：我們不妨令軸元素為pivot，第一次比較結(jié)果是a1<pivot，那么可以證明第二次比較a2也小于pivot的可能性是2/3！這容易證明：如果a2>pivot的話，那么a1，a2，pivot這三個(gè)元素之間的關(guān)系就完全確定了——a1<pivot<a2，剩下來(lái)的元素排列的可能性我們不妨記為P（不需要具體算出來(lái)）。而如果a2<pivot呢？那么a1和a2的關(guān)系就仍然是不確定的，也就是說(shuō)，這個(gè)分支里面含有兩種情況：a1<a2<pivot，以及a2<a1<pivot。對(duì)于其中任一種情況，剩下的元素排列的可能性都是P，于是這個(gè)分支里面剩下的排列可能性就是2P。所以當(dāng)a2<pivot的時(shí)候，還剩下2/3的可能性需要排查。

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

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

?

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

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

總結(jié)

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

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。