006【算法篇】線性時間排序

前面我們提到的插入排序、歸并排序及快速排序均有個特點排监，即時間復雜度漸近下界為??(nlgn)仇奶，哪怕是隨機化的快速排序也是如此。

這些排序算法有個特點驾窟，即都是基于「比較」模型而衍生的算法庆猫，都是通過某種「比較元素」的方式最終實現(xiàn)了排序。由此我們是否可以得出結論：所有基于「比較」模型的算法绅络，其時間復雜度的漸近下界均為??(nlgn)月培？

答案是肯定的，具體證明過程如下：

假設我們基于「比較」模型來針對輸入數(shù)據(jù) $A=<a_1恩急，a_2杉畜，a_3>$ 進行排序時，一定會產(chǎn)生諸如 $a_1\leq a_2,a_1>a_2$ 這樣的判斷邏輯衷恭，然后依照這些判斷邏輯作進一步的決策寻行。這些判斷邏輯形成了如下的一棵決策樹

WechatIMG206.png

由圖我們可知，假設輸入數(shù)據(jù)有n個節(jié)點匾荆，決策樹的高度為h拌蜘，葉節(jié)點為所有可能的排列結果；那么最終形成排序結果時的比較次數(shù)即為決策樹的高度牙丽，因為每比較一次就深入一層简卧，即高度加1。

由于決策樹也是一棵二叉樹烤芦，根據(jù)二叉樹的性質举娩，假設二叉樹的葉節(jié)點個數(shù)為m，我們立即有如下結論：

高度為h的二叉樹中构罗，葉節(jié)點的總數(shù)至多為 $2^h$ 铜涉，即： $m\leq 2^h$
由于決策樹的葉節(jié)點包括了輸入數(shù)據(jù)所有的排列情況，那么葉節(jié)點的總數(shù)理應至少為n!遂唧，即： $m\geq n!$

故有如下不等式：
$n!\leq m \leq 2^h\tag{1}$
針對(1)式兩邊取對數(shù)芙代，并化簡計算：
$\begin{align} h& \geq lg(n!)\\ &=lg[\sqrt{2??n}(\frac{n}{e})^n]\tag{2}\\ &\geq lg(\frac{n}{e})^n\\ &=nlgn-nlge\\ &=??(nlgn) \end{align}$
證畢。其中(2)式引用了斯特林公式盖彭。

那么由此是否可以證明纹烹，所有的排序算法漸近下界均為??(nlgn)呢页滚？答案是否定的，人類對速度的極致追求怎么可能停留在??(nlgn)這樣一個難以接受的程度铺呵？可以進一步提升排序速度裹驰，使之趨近于線性時間嗎？因為就目前已知的軟硬件情況下來片挂，無論如何也要遍歷完全部的元素幻林，所以極限排序速度也應該是在線性時間內完成。

答案是肯定的音念，但是也需要付出一定的代價滋将。

計數(shù)排序

這是一個最簡單的線性時間排序，針對元素值不是很大時比較有效症昏，它需要額外的內存開銷用于存儲排序結果以及計數(shù)緩存。

計數(shù)排序的思想是父丰，針對每個輸入元素x肝谭，如果我們能夠確認比x小的元素個數(shù)，那么排序結果中我們把x放在輸出數(shù)組對應的位置即可蛾扇。例如假設有17個元素比x小攘烛，那么就把x放在輸出數(shù)組的第18個位置上即可。下面給出偽代碼：

COUNTING_SORT(A,B,k)
    //let C[0..k] be a new array
    for i=0 to k
        C[i]=0
    for j=1 to A.length
        C[A[j]]=C[A[j]]+1       // C[j]的值為元素值為A[j]的個數(shù)
    for i=1 to k
        C[i]=C[i-1]+C[i]        // C[i]的值為元素值小于等于A[i]的個數(shù)
    for j=A.length down to 1
        B[C[A[j]]]=A[j]
        C[A[j]]=C[A[j]]-1

舉例說明镀首，假設輸入數(shù)據(jù)A=[4坟漱，1，3更哄，4芋齿，3]，我們作圖來表示整個排序過程如下：

WechatIMG207.png

下面我們來分析計數(shù)排序的時間復雜度成翩。顯然第3-4行代碼所需的時間為??(k)觅捆，5-6行代碼所需時間為??(n)，7-8行代碼所需時間為??(k)麻敌，9-11行代碼所需時間為??(n)栅炒，這樣總的時間代價為??(n+k)。

所以在實際工作中术羔，當k=??(n)時我們可以選擇計數(shù)代碼赢赊，因為它的時間復雜度為??(n)，能夠在線性時間內完成级历，但是其空間復雜度較高释移，需要兩個數(shù)組的內存空間。

當k值遠大于n時寥殖，就不建議用這個算法了……除非你的內存無限大秀鞭。

基數(shù)排序

基數(shù)排序的算法就不講了趋观，比較簡單，偽代碼如下：

RADIX_SORT(A,d) //d表示數(shù)組元素的位數(shù)锋边，其中1為最低位皱坛，d為最高位
    for i=1 to d
        //進行d輪排序，每輪排序基于位數(shù)i

每輪的輔助排序算法不建議使用基于「比較」模型的算法豆巨，因為這樣會使得時間復雜度為??(nlgn)剩辟，違背我們的初衷，所以我們想到了使用計數(shù)排序往扔，因為它是基于線性時間的贩猎，而且屬于是穩(wěn)定的算法，只要k值選擇合理萍膛。

下面我們重點分析下時間復雜度吭服，以及k的選擇。

一般不建議按位進行逐輪排序蝗罗，我們假設待排序的數(shù)字至多為b位數(shù)艇棕，如果是按位進行排序的話，那么所需時間為??(n*b)串塑。如果b=lgn的話沼琉，那么其時間正好為??(nlgn)，這不是我們想看到的桩匪。所以一般在處理的時候不會按位進行排序打瘪，一般會靈活地分解為小于b的若干塊進行排序。

由于任何數(shù)在計算機內的表示均最終為二進制數(shù)傻昙，下文中我們僅討論所排序的數(shù)字為二進制數(shù)的情況闺骚。

假設我們有n個待排序的二進制數(shù)，該二進制數(shù)的位數(shù)為b妆档，那么我們可以拆分為d=b/r的r位進行d輪排序葛碧，其中每位為r比特，可表示的數(shù)字范圍為 $0～2^r-1$ 过吻，這個數(shù)也相當于計數(shù)排序中的k值进泼，于是時間復雜度計算如下：
$\begin{align} T(n)&=??[\frac{r}*(n+k)]\\ &=??[\frac纤虽{r}*(n+2^r)]\tag{3}\\ \end{align}$
于是乳绕，問題就變成了如何選擇r的值，使得(3)式中的一元函數(shù)取最小值……于是乎逼纸，我們馬上就想到了高數(shù)的求導洋措，我們對r進行求導，針對導數(shù)為0的情況求出r的值即可杰刽。具體求導過程就不寫了菠发，比較簡單王滤，下面我們用另一種思路來推理。

從(3)式中我們可以分析滓鸠，r的值一定要能夠使得 (b/r)*n的值足夠小雁乡，因為這樣可以減少排序的輪數(shù)，這樣的話會要求r的值越大越好糜俗；但是同時不能太大踱稍，因為太大的話會導致 $(b/r)\times 2^r$ 的值飆升，適得其反悠抹，因此會要求n的值大于 $2^r$ 珠月，也即：r應該比lgn要小，所以我們得到了r的一個上界楔敌，即r=lgn啤挎，這個取值應該跟函數(shù)求導的值一樣的。于是乎當r=lgn時的時間復雜度為：
$\begin{align} T(n)&=??[\frac卵凑{r}*(n+2^r)]\\ &=??(\frac庆聘{r}*n)\tag{4} \end{align}$
顯然，這是線性時間內的排序氛谜，但是需要付出 $2^r$ 位的輔助空間。算法很美区端，但是用起來需要細細考究值漫。