算法導論(五):線性時間排序

麻省理工學院公開課:算法導論贞让。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]

  1. 第一個for循環(huán)對數組C進行初始化偷办,其中k=4(數組A中的最大值)艰额,得到C=[0, 0, 0, 0]
  2. 第二個for循環(huán)遍歷A中的元素,對A中的元素進行計數椒涯,并把每個元素的數量按順序存儲在C中柄沮,得到C=[1, 0, 2, 2]
  3. 第三個for循環(huán)遍歷C中的元素,進行累加。得到C=[1, 1, 3, 5]
  4. 第四個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

排序過程:

  1. 第一列數字為數組內元素的初始排序灯变,即[329, 457, 657, 839, 436, 720, 355]
  2. 針對這些元素的最后一位進行排序,得到第二列數字[720, 355, 436, 457, 657, 329, 839]
  3. 針對倒數第二位元素進行排序捅膘,得到第三列數字[720, 329, 436, 839, 355, 457, 657]
  4. 針對第一位元素進行排序添祸,得到最后一列數字[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),時間復雜度不高浆兰。但在實際情況中磕仅,計數排序因為需要比較多的存儲空間,所以并沒有理想中那么快簸呈。

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末榕订,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子蜕便,更是在濱河造成了極大的恐慌劫恒,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,378評論 6 516
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件轿腺,死亡現(xiàn)場離奇詭異两嘴,居然都是意外死亡,警方通過查閱死者的電腦和手機吃溅,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,970評論 3 399
  • 文/潘曉璐 我一進店門溶诞,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人决侈,你說我怎么就攤上這事螺垢。” “怎么了赖歌?”我有些...
    開封第一講書人閱讀 168,983評論 0 362
  • 文/不壞的土叔 我叫張陵枉圃,是天一觀的道長。 經常有香客問我庐冯,道長孽亲,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 59,938評論 1 299
  • 正文 為了忘掉前任展父,我火速辦了婚禮返劲,結果婚禮上玲昧,老公的妹妹穿的比我還像新娘。我一直安慰自己篮绿,他們只是感情好孵延,可當我...
    茶點故事閱讀 68,955評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著亲配,像睡著了一般尘应。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上吼虎,一...
    開封第一講書人閱讀 52,549評論 1 312
  • 那天犬钢,我揣著相機與錄音,去河邊找鬼思灰。 笑死玷犹,一個胖子當著我的面吹牛,可吹牛的內容都是我干的官辈。 我是一名探鬼主播箱舞,決...
    沈念sama閱讀 41,063評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼拳亿!你這毒婦竟也來了?” 一聲冷哼從身側響起愿伴,我...
    開封第一講書人閱讀 39,991評論 0 277
  • 序言:老撾萬榮一對情侶失蹤肺魁,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后隔节,有當地人在樹林里發(fā)現(xiàn)了一具尸體鹅经,經...
    沈念sama閱讀 46,522評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,604評論 3 342
  • 正文 我和宋清朗相戀三年怎诫,在試婚紗的時候發(fā)現(xiàn)自己被綠了瘾晃。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,742評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡幻妓,死狀恐怖蹦误,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情肉津,我是刑警寧澤强胰,帶...
    沈念sama閱讀 36,413評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站妹沙,受9級特大地震影響偶洋,放射性物質發(fā)生泄漏。R本人自食惡果不足惜距糖,卻給世界環(huán)境...
    茶點故事閱讀 42,094評論 3 335
  • 文/蒙蒙 一玄窝、第九天 我趴在偏房一處隱蔽的房頂上張望牵寺。 院中可真熱鬧,春花似錦恩脂、人聲如沸缸剪。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,572評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽杏节。三九已至,卻和暖如春典阵,著一層夾襖步出監(jiān)牢的瞬間奋渔,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,671評論 1 274
  • 我被黑心中介騙來泰國打工壮啊, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留嫉鲸,地道東北人。 一個月前我還...
    沈念sama閱讀 49,159評論 3 378
  • 正文 我出身青樓歹啼,卻偏偏與公主長得像玄渗,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子狸眼,可洞房花燭夜當晚...
    茶點故事閱讀 45,747評論 2 361

推薦閱讀更多精彩內容

  • -分析基于比較的排序能夠達到的最快效率-介紹幾種非比較的線性時間排序算法 排序最快能夠達到多快的速度藤树?取決于你使用...
    Alex90閱讀 773評論 0 1
  • 一. 寫在前面 要學習算法,“排序”是一個回避不了的重要話題拓萌,在分析完并查集算法和常用數據結構之后岁钓,今天我們終于可...
    Leesper閱讀 2,535評論 0 40
  • 1 序 2016年6月25日夜,帝都微王,天下著大雨屡限,拖著行李箱和同學在校門口照了最后一張合照,搬離寢室打車去了提前租...
    RichardJieChen閱讀 5,108評論 0 12
  • 總結一下常見的排序算法炕倘。 排序分內排序和外排序钧大。內排序:指在排序期間數據對象全部存放在內存的排序。外排序:指在排序...
    jiangliang閱讀 1,351評論 0 1
  • 李茂書法
    洗墨人閱讀 168評論 0 0