在這篇文章里，我們從信息論的角度證明了，基于比較的排序算法需要的比較次數（在最壞情況下）至少為log2(n!)，而log(n!)=Θ(nlogn)，這給出了比較排序的一個下界。但那里我們討論的只是最理想的情況。一個事件本身所含的信息量是有大小之分的。看到這篇文章之后，我的思路突然開闊了不少：信息論是非常強大的，它并不只是一個用來分析理論最優決策的工具。從信息論的角度來分析算法效率是一件很有趣的事，它給我們分析排序算法帶來了一種新的思路。
假如你手里有一枚硬幣。你希望通過拋擲硬幣的方法來決定今天晚上干什么，正面上網反面看電影。投擲硬幣所產生的結果將給你帶來一些“信息”，這些信息的多少就叫做“信息量”。如果這個硬幣是“公正”的，正面和反面出現的概率一樣，那么投擲硬幣后不管結果咋樣，你都獲得了1 bit的信息量。如果你事先就已經知道這個硬幣并不是均勻的，比如出現正面的概率本來就要大得多，這時我們就說事件結果的不確定性比剛才更小。如果投擲出來你發現硬幣果然是正面朝上，這時你得到的信息量就相對更小（小于1 bit）；反之如果投擲出來居然反面朝上了，那你就得到了一個相對較大的信息量（大于1 bit）。但平均下來，我們得到的信息量是小于1 bit的，因為前者發生的可能性畢竟要大一些。最極端的情況就是，這是一枚被搗了鬼的魔術硬幣，你怎么投都是正面。此時，你投了硬幣等于沒投，反正結果都是正面朝上，你得到的信息量永遠為0。
這個理論是很符合生活實際的。昨天晚上我出去吃飯時，坐在我后面的那個人是男的還是女的？這種問題就比較有價值，因為大家都猜不到答案究竟是什么；但要問我昨天跟誰一起出去上自習去了，問題的答案所含的信息量就變小了，因為大家都知道如果我破天荒地跑去自習了的話多半是有MM陪著一起去的。如果有網友問我是男的還是女的，那就更不可思議了，因為我不但多次在這個Blog里提到我一直想找一個合適的MM，還在AboutMe里面發了我的照片。如果某人剛操完一個MM，突然扭過頭去問“對了，你是男的還是女的呀”，那這個人絕對是一個不折不扣的大傻B，因為這個問題所能帶來的信息量幾乎為0。
總之，當每種結果出現的概率都相等，事件的不確定性達到最大，其結果最難預測時，事件的發生將會給我們帶來最大的信息量。我們把一個事件的不確定程度叫做“熵”，熵越大表明這個事件的結果越難以預測，同時事件的發生將給我們帶來越多的信息。如果在排序算法里每次比較的熵都是最大的，理論上來說這種（基于比較的）排序算法就應當是最優的。但我們一會兒將看到，我們已知的排序算法總是不完美的，每種算法都會或多或少地存在一些價值明顯不大的比較。
首先我們來看三種經典的平方復雜度算法。它們的效率并不高，原因就在于算法過程中會出現越來越多概率嚴重不均的比較。隨著冒泡排序的進行，整個序列將變得越來越有序，位置顛倒的泡泡將越來越少；選擇排序的每一趟選擇中，你都會不斷得到越來越大的數，同時在以后的比較中找到更大的數的概率也越來越低；在插入排序中，你總是把新的數與已經排好的數按從大到小的順序依次進行比較，可以想到新的數一開始就比前面所有的數中最大的那個還大的概率是相當小的。受此啟發，我們可以很自然地想到一個插入排序的改進：處理一個新的數時，為何不一開始就與前面處理過的數中的中位數進行比較？這種比較的熵顯然更大，能獲取的信息量要大得多，明顯更有價值一些。這就是插入排序的二分查找改進。
下面我們再來看一看幾種O(nlogn)的排序算法。在快速排序算法中，比較的信息熵不會因為排序算法的進行而漸漸減小，這就是快速排序比上面幾個排序算法更優秀的根本原因。仔細回顧快速排序算法的過程，我們立即看出，每次比較的兩種結果出現的概率完全由這一趟劃分過程所選擇的基準關鍵字決定：選擇的基準關鍵字剛好是當前處理的數字集合的中位數，則比較結果的不確定性達到最大；如果選擇的基準關鍵字過大或過小，都會出現比較產生的結果不均等的情況，這使得每次比較平均帶來的信息量大大減少。因此，快速排序算法是很看人品的：如果基準選的好，算法完全有可能達到理論上的最優；如果基準選的不好，復雜度很容易退化到O(n^2)。
堆排序所需要的比較次數更多，因為在堆的刪除操作中有一種明顯不平衡的比較。在刪除操作中，我們把根節點用整個堆的最末一個節點來代替，然后不斷下沉直到它的兒子都比它大。判斷它的兩個兒子是否比它大，其信息熵是相當小的，因為這個節點本身就來自堆的底部，除非這個節點已經沉到很底下了，否則兒子比它大的概率是很小的。因此，我們想到了一個堆排序的優化：反正堆建好了以后不需要再插入新元素了，為何不舍棄堆的完全二叉樹性質？我們可以直接把根元素改成無窮大，讓它沉到底，不用再考慮兒子比它大的問題了，也不再顧及堆的形狀。這樣的話，堆排序是否就完美了呢？仔細想想你會發現，改進之后的比較操作仍然是不對稱的。這種不對稱主要來自兩個方面：左子樹和右子樹的節點個數不同，以及被刪除的根節點原先是來自左子樹還是右子樹。比方說，根節點原本就是從右子樹提上來的，現在刪除了根節點后，左子樹的最小值比右子樹的最小值更小的概率就偏大一些；此時萬一右子樹節點本來就比左邊少，這樣的話這個比較的熵就更小了。
最后看一下歸并排序。在有序隊列的合并操作中，絕大多數情況下的比較操作都是比較平衡的。左邊一半中的最小值和右邊一半中的最小值進行比較，結果顯然是等概率的。當然，隨后將發生其中一邊的最小值與另一邊的次小值進行比較，這時的比較操作略微有了一些不平衡，并存在較小的可能使得比較操作變得更加不平衡（最小值與第三小的值相比）。有趣的是，比較越是不平衡，重新歸于平衡的概率就越大，就好像歸并排序中的信息熵會自動調整一樣。這就是歸并排序比平方復雜度的排序算法效率更高的原因。當然，完全有可能出現這樣的情況：右邊的數奇小無比，左邊的最小值比右邊的所有值都大。結果最后右邊的隊列都處理完了左邊還沒開始取數，此時合并操作提前結束，所花費的比較次數出人意料地少。從信息熵的角度來看，這種“比較提前結束”的現象是非常自然的：這種情況畢竟是“出人意料”的，事實越出人意料，獲得的信息量就越大，因此算法就提前結束了。但這種情況畢竟是相當罕見的，平均情況下每次比較的信息量仍然不足1 bit。
最后，為什么線性排序的算法可以達到O(n)的復雜度？這是因為，線性排序算法并不是基于比較的。一次比較事件（假設沒有相等的情況）所能產生的信息量最多1 bit，而一次Hash分類可以獲得的信息量遠遠超過了1 bit，因為它可以一次確定出n種等概率的可能情況。
Matrix67原創，轉貼請注明出處~~