[[341282]]

基本上所有正而八經(jīng)的算法教材都會(huì)解釋像快速排序quicksort和堆排序heapsort這樣的排序算法有多快，但并不需要復(fù)雜的數(shù)學(xué)就能證明你可以逐漸趨近的速度有多快。

關(guān)于標(biāo)記的一個(gè)嚴(yán)肅說明：

大多數(shù)計(jì)算機(jī)專業(yè)的科學(xué)家使用大寫字母 O 標(biāo)記來指代“趨近，直到到達(dá)一個(gè)常數(shù)比例因子”，這與數(shù)學(xué)專業(yè)所指代的意義是有所區(qū)別的。這里我使用的大 O 標(biāo)記的含義與計(jì)算機(jī)教材所指相同，但至少不會(huì)和其他數(shù)學(xué)符號(hào)混用。

基于比較的排序

先來看個(gè)特例，即每次比較兩個(gè)值大小的算法（快速排序、堆排序，及其它通用排序算法）。這種思想后續(xù)可以擴(kuò)展至所有排序算法。

一個(gè)簡(jiǎn)單的最差情況下的計(jì)數(shù)角度

假設(shè)有 4 個(gè)互不相等的數(shù)，且順序隨機(jī)，那么，可以通過只比較一對(duì)數(shù)字完成排序嗎？顯然不能，證明如下：根據(jù)定義，要對(duì)該數(shù)組排序，需要按照某種順序重新排列數(shù)字。換句話說，你需要知道用哪種排列方式？有多少種可能的排列？第一個(gè)數(shù)字可以放在四個(gè)位置中的任意一個(gè)，第二個(gè)數(shù)字可以放在剩下三個(gè)位置中的任意一個(gè)，第三個(gè)數(shù)字可以放在剩下兩個(gè)位置中的任意一個(gè)，最后一個(gè)數(shù)字只有剩下的一個(gè)位置可選。這樣，共有  4×3×2×1=4!=24 種排列可供選擇。通過一次比較大小，只能產(chǎn)生兩種可能的結(jié)果。如果列出所有的排列，那么“從小到大”排序?qū)?yīng)的可能是第 8 種排列，按“從大到小”排序?qū)?yīng)的可能是第 24 種排列，但無法知道什么時(shí)候需要的是其它 22 種排列。

通過 2 次比較，可以得到 2×2=4 種可能的結(jié)果，這仍然不夠。只要比較的次數(shù)少于 5（對(duì)應(yīng) 2⁵ = 32  種輸出），就無法完成 4 個(gè)隨機(jī)次序的數(shù)字的排序。如果 W(N) 是最差情況下對(duì) N 個(gè)不同元素進(jìn)行排序所需要的比較次數(shù)，那么，

兩邊取以 2 為底的對(duì)數(shù)，得：

N! 的增長(zhǎng)近似于 NN （參閱 Stirling 公式），那么，

這就是最差情況下從輸出計(jì)數(shù)的角度得出的 O(N log N) 上限。

從信息論角度的平均狀態(tài)的例子

使用一些信息論知識(shí)，就可以從上面的討論中得到一個(gè)更有力的結(jié)論。下面，使用排序算法作為信息傳輸?shù)木幋a器：

1. 任取一個(gè)數(shù)，比如 15
2. 從 4 個(gè)數(shù)字的排列列表中查找第 15 種排列
3. 對(duì)這種排列運(yùn)行排序算法，記錄所有的“大”、“小”比較結(jié)果
4. 用二進(jìn)制編碼發(fā)送比較結(jié)果
5. 接收端重新逐步執(zhí)行發(fā)送端的排序算法，需要的話可以引用發(fā)送端的比較結(jié)果
6. 現(xiàn)在接收端就可以知道發(fā)送端如何重新排列數(shù)字以按照需要排序，接收端可以對(duì)排列進(jìn)行逆算，得到 4 個(gè)數(shù)字的初始順序
7. 接收端在排列表中檢索發(fā)送端的原始排列，指出發(fā)送端發(fā)送的是 15

確實(shí)，這有點(diǎn)奇怪，但確實(shí)可以。這意味著排序算法遵循著與編碼方案相同的定律，包括理論所證明的不存在通用的數(shù)據(jù)壓縮算法。算法中每次比較發(fā)送 1 比特的比較結(jié)果編碼數(shù)據(jù)，根據(jù)信息論，比較的次數(shù)至少是能表示所有數(shù)據(jù)的二進(jìn)制位數(shù)。更技術(shù)語言點(diǎn)，平均所需的最小比較次數(shù)是輸入數(shù)據(jù)的香農(nóng)熵，以比特為單位。熵是衡量信息等不可預(yù)測(cè)量的數(shù)學(xué)度量。

包含 N 個(gè)元素的數(shù)組，元素次序隨機(jī)且無偏時(shí)的熵最大，其值為 log2​ N! 個(gè)比特。這證明 O(N log N) 是一個(gè)基于比較的對(duì)任意輸入排序的最優(yōu)平均值。

以上都是理論說法，那么實(shí)際的排序算法如何做比較的呢？下面是一個(gè)數(shù)組排序所需比較次數(shù)均值的圖。我比較的是理論值與快速排序及 Ford-Johnson 合并插入排序 的表現(xiàn)。后者設(shè)計(jì)目的就是最小化比較次數(shù)（整體上沒比快速排序快多少，因?yàn)樯钪邢鄬?duì)于最大限度減少比較次數(shù)，還有更重要的事情）。又因?yàn)?ruby>合并插入排序merge-insertion sort是在 1959 年提出的，它一直在調(diào)整，以減少了一些比較次數(shù)，但圖示說明，它基本上達(dá)到了最優(yōu)狀態(tài)。

一點(diǎn)點(diǎn)理論導(dǎo)出這么實(shí)用的結(jié)論，這感覺真棒！

小結(jié)

證明了：

1. 如果數(shù)組可以是任意順序，在最壞情況下至少需要 O(N log N) 次比較。
2. 數(shù)組的平均比較次數(shù)最少是數(shù)組的熵，對(duì)隨機(jī)輸入而言，其值是 O(N log N) 。

注意，第 2 個(gè)結(jié)論允許基于比較的算法優(yōu)于 O(N log N)，前提是輸入是低熵的（換言之，是部分可預(yù)測(cè)的）。如果輸入包含很多有序的子序列，那么合并排序的性能接近 O(N)。如果在確定一個(gè)位之前，其輸入是有序的，插入排序性能接近 O(N)。在最差情況下，以上算法的性能表現(xiàn)都不超出 O(N log N)。

一般排序算法

基于比較的排序在實(shí)踐中是個(gè)有趣的特例，但從理論上講，計(jì)算機(jī)的 CMP 指令與其它指令相比，并沒有什么特別之處。在下面兩條的基礎(chǔ)上，前面兩種情形都可以擴(kuò)展至任意排序算法：

1. 大多數(shù)計(jì)算機(jī)指令有多于兩個(gè)的輸出，但輸出的數(shù)量仍然是有限的。
2. 一條指令有限的輸出意味著一條指令只能處理有限的熵。

這給出了 O(N log N) 對(duì)應(yīng)的指令下限。任何物理上可實(shí)現(xiàn)的計(jì)算機(jī)都只能在給定時(shí)間內(nèi)執(zhí)行有限數(shù)量的指令，所以算法的執(zhí)行時(shí)間也有對(duì)應(yīng) O(N log N) 的下限。

什么是更快的算法？

一般意義上的 O(N log N) 下限，放在實(shí)踐中來看，如果聽人說到任何更快的算法，你要知道，它肯定以某種方式“作弊”了，其中肯定有圈套，即它不是一個(gè)可以處理任意大數(shù)組的通用排序算法。可能它是一個(gè)有用的算法，但最好看明白它字里行間隱含的東西。

一個(gè)廣為人知的例子是基數(shù)排序radix sort算法，它經(jīng)常被稱為 O(N) 排序算法，但它只能處理所有數(shù)字都能放入 k 比特的情況，所以實(shí)際上它的性能是 O(kN)。

什么意思呢？假如你用的 8 位計(jì)算機(jī)，那么 8 個(gè)二進(jìn)制位可以表示 2⁸=256 個(gè)不同的數(shù)字，如果數(shù)組有上千個(gè)數(shù)字，那么其中必有重復(fù)。對(duì)有些應(yīng)用而言這是可以的，但對(duì)有些應(yīng)用就必須用 16 個(gè)二進(jìn)制位來表示，16 個(gè)二進(jìn)制位可以表示 2¹⁶=65,536 個(gè)不同的數(shù)字。32 個(gè)二進(jìn)制位可以表示 2³²=4,294,967,296 不同的數(shù)字。隨著數(shù)組長(zhǎng)度的增長(zhǎng)，所需要的二進(jìn)制位數(shù)也在增長(zhǎng)。要表示 N 個(gè)不同的數(shù)字，需要 k ≥ log2​ N 個(gè)二進(jìn)制位。所以，只有允許數(shù)組中存在重復(fù)的數(shù)字時(shí)， O(kN) 才優(yōu)于 O(N log N)。

一般意義上輸入數(shù)據(jù)的 O(N log N) 的性能已經(jīng)說明了全部問題。這個(gè)討論不那么有趣因?yàn)楹苌傩枰?32 位計(jì)算機(jī)上對(duì)幾十億整數(shù)進(jìn)行排序，如果有誰的需求超出了 64 位計(jì)算機(jī)的極限，他一定沒有告訴別人。