麻省理工學院公開課：算法導論贞让。B站地址凌外，網易公開課也有對應的資源乐疆。
https://www.bilibili.com/video/av1149902/?p=5
這節(jié)課的主要內容是用決策樹模型證明比較排序算法的時間復雜度不會快于nlgn筋夏。以及另外兩個非比較類型的排序算法及其分析：計數排序扑眉、基數排序。
前面講過的算法有：
1基公、快速排序 Θ(nlgn) 或者 Θ(n2)
2幅慌、歸并排序 Θ(nlgn)
3、插入排序 Θ(n2)
4轰豆、堆排序【這個課程上沒有講過胰伍，可能是在練習課上講過】 Θ(nlgn)
提問：排序算法最快可以有多快？
回答：看情況酸休，取決于你使用的計算模型里骂租，哪些操作是被允許的。我們需要關心元素的排列順序雨席，以及我們可以如何對元素操作菩咨？
前面的算法最快是nlgn，如何能使它比nlgn更好呢陡厘？
這些排序都屬于比較排序的算法模型抽米，這是解決排序問題的一個模型。也就是只能使用比較（如大于糙置、小于云茸、等于、大于等于谤饭、小于等于）來決定元素的相對順序标捺。
事實上，比較排序的算法運行速度不會快于nlgn揉抵。下面用決策樹模型來證明
決策樹模型
決策樹模型：這是算法中另一個規(guī)定你可以進行哪些操作的模型亡容，比比較模型適用范圍更廣。
圖中數字表示數組中元素的索引
上面是對數組[a1, a2, a3]進行排序的決策樹模型冤今。每一個節(jié)點表示一個比較操作闺兢，如果a1 < a2則往左，a1 > a2則往右繼續(xù)戏罢。
決策樹模型的定義如下：
有數組（a1, a2, ... , an）屋谭，每一個非葉節(jié)點都會有一個下標i:j，i,j∈{1,2, ... , n}龟糕，表示比較ai和aj的大小桐磁。
每個非葉節(jié)點下會分出2棵子樹，左邊的子樹表示ai≤aj的情況下讲岁，算法的后續(xù)操作我擂。右邊的子樹表示ai>aj的情況下衬以，算法的后續(xù)操作。
每個葉節(jié)點表示一個排序結果扶踊，如[π(1), π(2), ... , π(n)]表示：aπ(1)≤aπ(2)≤...≤aπ(n)
決策樹模型是算法的一種圖形表示泄鹏，比較排序的算法都可以用決策樹模型表示郎任，為什么不用決策樹模型來表示排序算法呢秧耗？因為決策樹模型根據輸入n的數值而有不同的大小。
把比較排序的一個算法舶治，轉換成決策樹形式的算法表達：
1分井、為每一個n值繪制一棵決策樹
2、進行比較時霉猛，把樹分成兩個分支尺锚，左子樹和右子樹。
3惜浅、決策樹就是把算法中這些比較的所有可能的結果分別列出來瘫辩。即指出了所有可能的路線。
根據輸入n的數值坛悉，畫出來的決策樹會非常龐大伐厌。
決策樹中葉節(jié)點的個數至少是n的階乘，即n!（列出了所有可能的排序結果）裸影，而決策樹的高度為lg(n!)挣轨。根據斯特林公式，n!的近似值為(n/e)n轩猩，即高度為lg(n/e)n = nlg(n/e) = n(lgn-lge)卷扮，其中l(wèi)ge是常數，所以決策樹的高度為Ω(nlgn)均践。
即所有比較排序算法對應的決策樹的深度至少是nlgn晤锹。
線性時間的非比較類型的排序算法
計數排序 counting sort
輸入為：數組A[1, ... , n]，其中Ai∈{1, 2, ..., k}
輸出為：數組B[1, ... , n]彤委，即已排序的A
其中鞭铆，需要輔助存儲的數組C
這里的數組索引是從1到n，不是平時代碼寫的0到n-1
計數排序算法的偽代碼如下
for i <- 1 to k
do C[i] <- 0
for j <- 1 to n
do C[A[j]] <- C[A[j]]+1
// C[i] = |{key = i}|
for i <- 2 to k
do C[i] <- C[i] + C[i-1]
// C[i] = |{key <= i}|
for j <- n downto 1
do B[C[A[j]]] <- A[j]
C[A[j]] <- C[A[j]] - 1
偷偷放一下js版本
for(var i=1;i<=k;i++){
C[i] = 0;
}
// 遍歷A葫慎，得到數組C衔彻，即A中各元素的個數
for(var j=1;j<=n;j++){
C[A[j]]++;
}
for(i=2;i<=k;i++){
C[i] = C[i] + C[i-1];
}
// 分配
for(j=n;j>=1;j--){
B[C[A[j]]] = A[j];
C[A[j]] = C[A[j]] - 1;
}
看偽代碼一共有4個for循環(huán)，舉個例子來看下代碼是如何運行的：
A=[4, 1, 3, 4, 3]
- 第一個for循環(huán)對數組C進行初始化偷办，其中k=4（數組A中的最大值）艰额，得到C=[0, 0, 0, 0]
- 第二個for循環(huán)遍歷A中的元素，對A中的元素進行計數椒涯，并把每個元素的數量按順序存儲在C中柄沮，得到C=[1, 0, 2, 2]
- 第三個for循環(huán)遍歷C中的元素，進行累加。得到C=[1, 1, 3, 5]
- 第四個for循環(huán)對A中的元素進行分配祖搓，放到數組B中對應的位置狱意，可得到B=[1, 3, 3, 4, 4]
運行時間分析
四個for循環(huán)的運行時間一次為k+n+k+n，即k+n拯欧。
如果k=O(n)详囤，那么運行時間為O(n)，那這個算法是合適的镐作。如果k=2n之類的值藏姐，那么運行時間就不太好了。该贾。
而且這里需要保證數組中的元素均為正整數羔杨，范圍夠小。
基數排序算法
基數排序是用來在線性時間內處理大范圍數據的杨蛋。這個算法有一個非常重要的性質兜材，即穩(wěn)定性。算法的整體思想為：按位排序逞力。
這里一段小插曲曙寡，這個算法是一個非常老的算法，最早起源于1890年掏击，是MIT的一位講師發(fā)明的卵皂。這位講師因此賺了很多錢【笑
下面用一個例子來說明一下基數排序。
有下列數字[329, 457, 657, 839, 436, 720, 355]砚亭，進行排序：
329 720 720 329
457 355 329 355
657 436 436 436
839 457 839 457
436 657 355 657
720 329 457 720
355 839 657 839
排序過程：
- 第一列數字為數組內元素的初始排序灯变，即[329, 457, 657, 839, 436, 720, 355]
- 針對這些元素的最后一位進行排序，得到第二列數字[720, 355, 436, 457, 657, 329, 839]
- 針對倒數第二位元素進行排序捅膘，得到第三列數字[720, 329, 436, 839, 355, 457, 657]
- 針對第一位元素進行排序添祸，得到最后一列數字[329, 355, 436, 457, 657, 720,
839]，即最終的結果寻仗。
在每一輪排序中刃泌，相同大小的元素保持原有順序不變。
分析
1署尤、 如果每一輪排序都用計數排序耙替，其時間復雜度為O(k+n)。
2曹体、 用二進制來表示數組中的元素俗扇。一共有n個整數，每一個整數均為b比特的長度箕别，那么數組中元素的取值范圍為(0, 2b-1)铜幽。
一共需要進行b輪排序滞谢，每一輪排序花費的時間為n，那么總時間為b·n除抛。
假如b很小狮杨，為lgn，那么數字的取值范圍為(0, n-1)到忽。前面的計數排序已經可以做到在線性時間內對(0, n-1)范圍內的數進行排序橄教，這里卻需要nlgn的時間，顯然不太好绘趋。颤陶。颗管。
可以把連續(xù)的比特看作是一位數來進行比較陷遮，看看用計數排序可以一次處理的最多比特為多少。
算法：把每個整數拆分成b/r位數字垦江，每個數字都是r比特的長度帽馋。也就是將數組中的元素用2r進制來表示。
這里一共需要進行b/r輪運算比吭，其中每一輪比較中绽族，最大的數字為2r，即每位數字的取值范圍為(0, 2r)衩藤，也就是k=2r吧慢，所以每一輪使用計數排序需要(2r+n)的時間。
所以算法的總時長為(b/r)·(2r+n)赏表，即O((b/r)·(2r+n))检诗。
這里要選擇合適的r，使運行時間最小瓢剿。
(b/r)·(2r+n)逢慌，可以拆分為 (b/r)·n + (b/r)·2r 兩項
對于(b/r)·n，r越大间狂，其值越小攻泼。
對于(b/r)·2r，r越小鉴象，其值越小忙菠。
當n≥2r，r = lgn
如果r=lgn纺弊，總時長為(b/r)·(2r+n) = (b/lgn)·(n+n)牛欢，即為O(bn/(lgn))。
待排序數列是某個范圍內的整數俭尖，即(0, 2b-1)氢惋，b是數的比特位數洞翩，對應于數的取值范圍。
將取值范圍寫成(0, nd-1)焰望，d = b/r = b/lgn骚亿，d是一個常數。
對于n∈{0, ..., nd-1}熊赖，總時長為O(dn)
計數排序 vs 基數排序
計數排序可以用線性時間處理0到某個常數乘以d范圍內的數来屠。
基數排序可以在線性時間內處理0到n的某個常數次方范圍內的數。
假設處理32比特的數震鹉，即取值范圍為(0, 232)俱笛，使用基數排序分四輪進行計算，每輪處理8比特的數传趾，需要28=256的存儲空間進行計數排序迎膜，時間復雜度為4*(8+n)，時間復雜度不高浆兰。但在實際情況中磕仅，計數排序因為需要比較多的存儲空間，所以并沒有理想中那么快簸呈。
