線性時間排序

算法設(shè)計與分析2023年2月1日講授內(nèi)容：動態(tài)規(guī)劃I

教師：胡學(xué)鋼、吳共慶至今為止，我們見過的排序都是

比較排序

:僅僅使用比較來比較各項的相對順序

.?

比如：插入排序,合并排序,快速排序,

堆排序.我們見過的比較排序的最好的最壞運行時間是O(nlgn).

O(nlgn)是不是我們能做到的極限?

決策樹

可以幫助我們回答這個問題

.排序可以做到多快？2/1/2023算法設(shè)計與分析-線性時間排序2排序〈a1,a2,…,an〉每個內(nèi)部節(jié)點標(biāo)識為

i:j

i,j

∈{1,2,…,n}.?左子樹表示當(dāng)ai

≤aj時的比較序列

.?右子樹表示當(dāng)ai

≥aj時的比較序列

.2/1/2023算法設(shè)計與分析-線性時間排序3決策樹舉例排序

〈a1,a2,a3〉=〈9,4,6〉:每個內(nèi)部節(jié)點標(biāo)識為i:j,i,j∈{1,2,…,n}.?左子樹表示當(dāng)ai≤aj時的比較序列

.?右子樹表示當(dāng)ai≥aj時的比較序列

.2/1/2023算法設(shè)計與分析-線性時間排序4決策樹舉例每個內(nèi)部節(jié)點標(biāo)識為i:j,i,j∈{1,2,…,n}.?左子樹表示當(dāng)ai≤aj時的比較序列

.?右子樹表示當(dāng)ai≥aj時的比較序列

.排序

〈a1,a2,a3〉=〈9,4,6〉:2/1/2023算法設(shè)計與分析-線性時間排序5決策樹舉例每個內(nèi)部節(jié)點標(biāo)識為i:j,i,j∈{1,2,…,n}.?左子樹表示當(dāng)ai≤aj時的比較序列

.?右子樹表示當(dāng)ai≥aj時的比較序列

.排序

〈a1,a2,a3〉=〈9,4,6〉:2/1/2023算法設(shè)計與分析-線性時間排序6決策樹舉例每個內(nèi)部節(jié)點標(biāo)識為i:j,i,j∈{1,2,…,n}.?左子樹表示當(dāng)ai≤aj時的比較序列.?右子樹表示當(dāng)ai≥aj時的比較序列.排序

〈a1,a2,a3〉=〈9,4,6〉:2/1/2023算法設(shè)計與分析-線性時間排序7決策樹舉例

決策樹可以模擬任何的比較排序的執(zhí)行過程:每個輸入大小為n的序列都可以用這棵樹表示.將算法視為每次兩個項相比后就分叉.樹包含了所有可能比較的指令路徑.算法的運行時間

=

路徑的長度.最壞運行時間

=樹的高度.2/1/2023算法設(shè)計與分析-線性時間排序8決策樹模型定理.對n個項排序的任何決策樹的高度是Ω(nlgn).證明.

樹肯定包含≥n!個葉子,因為有n!種可能的排列.高度h

的二叉樹有≤2h個葉子.因此,n!≤2h.(lg

單調(diào)遞增)(Stirling’s公式)2/1/2023算法設(shè)計與分析-線性時間排序9決策樹排序的下界

推論.在最差情況下，任何一種比較排序至少需要O(nlogn)比較操作。這是比較操作所獲的信息有限所導(dǎo)致的，或者說是全序集的模糊代數(shù)結(jié)構(gòu)所導(dǎo)致的。從這個意義上講，堆排序和合并排序是漸進(jìn)最佳的比較排序算法

.2/1/2023算法設(shè)計與分析-線性時間排序10比較排序的下界計數(shù)排序:

各項之間不進(jìn)行比較.?輸入:A[1..n],A[j]∈{1,2,…,k}.?輸出:B[1..n],有序.?輔助存儲:C[1..k].2/1/2023算法設(shè)計與分析-線性時間排序11線性時間排序fori←1

tokdoC[i]←0forj←1

tondoC[A[j]]←C[A[j]]+1?

C[i]=|{key=i}|fori←2

tokdoC[i]←C[i]+C[i–1]?

C[i]=|{key≤i}|forj←n

downto1doB[C[A[j]]]←A[j]

C[A[j]]←C[A[j]]–12/1/2023算法設(shè)計與分析-線性時間排序12計數(shù)排序2/1/2023算法設(shè)計與分析-線性時間排序13計數(shù)排序舉例fori←1

tokdoC[i]←02/1/2023算法設(shè)計與分析-線性時間排序14循環(huán)1forj←1

tondoC[A[j]]←C[A[j]]+1?

C[i]=|{key=i}|2/1/2023算法設(shè)計與分析-線性時間排序15循環(huán)2forj←1

tondoC[A[j]]←C[A[j]]+1?

C[i]=|{key=i}|2/1/2023算法設(shè)計與分析-線性時間排序16循環(huán)2forj←1

tondoC[A[j]]←C[A[j]]+1?

C[i]=|{key=i}|2/1/2023算法設(shè)計與分析-線性時間排序17循環(huán)2forj←1

tondoC[A[j]]←C[A[j]]+1?

C[i]=|{key=i}|2/1/2023算法設(shè)計與分析-線性時間排序18循環(huán)2forj←1

tondoC[A[j]]←C[A[j]]+1?

C[i]=|{key=i}|2/1/2023算法設(shè)計與分析-線性時間排序19循環(huán)2fori←2

tokdoC[i]←C[i]+C[i–1]?

C[i]=|{key≤i}|2/1/2023算法設(shè)計與分析-線性時間排序20循環(huán)3fori←2

tokdoC[i]←C[i]+C[i–1]?

C[i]=|{key≤i}|2/1/2023算法設(shè)計與分析-線性時間排序21循環(huán)3fori←2

tokdoC[i]←C[i]+C[i–1]?

C[i]=|{key≤i}|2/1/2023算法設(shè)計與分析-線性時間排序22循環(huán)3forj←n

downto

1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–12/1/2023算法設(shè)計與分析-線性時間排序23循環(huán)4forj←n

downto

1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–12/1/2023算法設(shè)計與分析-線性時間排序24循環(huán)4forj←n

downto

1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–12/1/2023算法設(shè)計與分析-線性時間排序25循環(huán)4forj←n

downto

1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–12/1/2023算法設(shè)計與分析-線性時間排序26循環(huán)4forj←n

downto

1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–12/1/2023算法設(shè)計與分析-線性時間排序27循環(huán)4forforforfortototodowntododododo2/1/2023算法設(shè)計與分析-線性時間排序L5.28分析如果

k=O(n),那么計數(shù)排序用的時間為

(n).?但是,排序的時間是Ω(nlgn)!?問題出在什么地方?答案:?比較排序

的時間是

Ω(nlgn)

.?計數(shù)排序不是

比較排序.?實際上,各項之間根本沒有比較!2/1/2023算法設(shè)計與分析-線性時間排序29運行時間計數(shù)排序是一種穩(wěn)定排序:它會保持相等的項的相對順序.

練習(xí):哪種其他的排序有這種特征?2/1/2023算法設(shè)計與分析-線性時間排序30穩(wěn)定排序?

發(fā)源

:HermanHollerith為

1890年美國人口普查設(shè)計的卡排序機(jī)

(參考附錄)?一位一位的排序.?Hollerith最初(不好)的想法:從最高位開始排序.?好的想法:使用輔助的穩(wěn)定排序方法從

最低位開始排序

.2/1/2023算法設(shè)計與分析-線性時間排序31基數(shù)排序2/1/2023算法設(shè)計與分析-線性時間排序32基數(shù)排序過程數(shù)位推導(dǎo)?

假設(shè)數(shù)字已經(jīng)按照其低階t–1位排序.?

按照t位排序

2/1/2023算法設(shè)計與分析-線性時間排序33基數(shù)排序的正確性數(shù)位推導(dǎo)?假設(shè)數(shù)字已經(jīng)按照其低階t–1位排序.?按照t位排序

兩個在位t不同的數(shù)被正確排序.2/1/2023算法設(shè)計與分析-線性時間排序34基數(shù)排序的正確性數(shù)位推導(dǎo)?假設(shè)數(shù)字已經(jīng)按照其低階t–1位排序.?按照t位排序

兩個在位t不同的數(shù)被正確排序.

兩個t

位相同的數(shù)保持與輸入相同的次序

?正確的順序.2/1/2023算法設(shè)計與分析-線性時間排序35基數(shù)排序的正確性?假設(shè)使用計數(shù)排序作為輔助的穩(wěn)定排序方法。

?對n個b比特字進(jìn)行排序。?每個字可以看成有b/r個以2r為基的數(shù).例子:

32-位字r=8?b/r=4遍基于28位的計數(shù)排序;或者r=16?b/r=2遍基于216位的計數(shù)排序.我們要作多少遍?2/1/2023算法設(shè)計與分析-線性時間排序36基數(shù)排序分析回憶:

計數(shù)排序使用

(n+k)的時間對n個范圍在0到k–1的數(shù)進(jìn)行排序。如果每個b-位字分成r-比特份,每遍計數(shù)排序花費

(n+2r).因為有b/r遍,我們有選擇r使得T(n,b)最小:?增加r意味著更少的遍數(shù),但是因為

r?lgn,時間成指數(shù)增長。2/1/2023算法設(shè)計與分析-線性時間排序37基數(shù)排序分析（續(xù)）通過求導(dǎo)并將方程置0求得最小值T(n,b)

。.或者,觀察我們不要2r?n

,在滿足這個限制的條件下選擇盡可能大的r對對稱性沒有影響。選擇r=lgn意味著T(n,b)=(bn/lgn).?

對于界于在0到nd–1的數(shù),我們有b=dlgn

?基數(shù)排序運行時間為

(dn).2/1/2023算法設(shè)計與分析-線性時間排序38選擇r實際上,在大量輸入的情況下，基排序速度很快，算法也很容易編碼和維護(hù)

.例子

(32-比特數(shù)):?

對

≥2000個數(shù)排序適合最多走3遍.?

合并排序和快速排序至少要lg2000=11遍.

缺點:

與快速排序不同,基排序基本上沒有引用局部性,這樣在現(xiàn)代的處理器上一個調(diào)優(yōu)的快速排序，利用內(nèi)存的分層體系，可以在性能上超過基數(shù)排序。2/1/2023算法設(shè)計與分析-線性時間排序39結(jié)論?HermanHollerith(1860-1929)?穿孔卡?Hollerith

的制表系統(tǒng)?排序工人的操作?基數(shù)排序起源?“現(xiàn)代的”IBM卡片?關(guān)于穿孔卡技術(shù)的網(wǎng)絡(luò)資源

2/1/2023算法設(shè)計與分析-線性時間排序40附錄:穿孔技術(shù)?在1880年美國人口普查花費了近10年的時間處理.?在

MIT擔(dān)任講師期間,Hollerith發(fā)明了穿孔卡技術(shù)的原型.?他的機(jī)器,包括一個“卡排序員”,使得1890的統(tǒng)計結(jié)果在6個周的時間內(nèi)就處理完了。?他在1911年創(chuàng)建了制表機(jī)器公司，這個公司在1924年和其他公司合并后組成了國際商用機(jī)器公司(IBM).2/1/2023算法設(shè)計與分析-線性時間排序41HermanHollerith(1860-1929)?穿孔卡

=

數(shù)據(jù)記錄.?洞

=

值.?算法

=

機(jī)器

+操作員.1900美國人口普查使用的穿孔卡的復(fù)制品.

[Howells2000]2/1/2023算法設(shè)計與分析-線性時間排序42穿孔卡Hollerith’s制表系統(tǒng)圖片請參考[Howells2000].?

穿孔?

手壓閱讀器?

轉(zhuǎn)盤計數(shù)器?

排序盒圖片請參考[Howells2000].圖片請參考[Howells2000].2/1/2023算法設(shè)計與分析-線性時間排序43?

操作員插入一個卡片。?

按住穿過穿孔卡的孔的鍵，使得電流接觸卡下面的水銀杯.?每當(dāng)一個數(shù)位被穿孔后,對應(yīng)排序盒的蓋子升起。?

操作員將卡片放入盒子并且合上蓋子.?

當(dāng)所有的卡片處理完畢后,前端的面板打開

,卡片已經(jīng)安裝順序排放,完成了一遍穩(wěn)定排序。2/1/2023算法設(shè)計與分析-線性時間排序44排序員的操作Hollerith在1889年的最初專利展示了最高位優(yōu)先的基數(shù)排序:“Themostcomplicatedcombinationscanreadilybecounted