線性時(shí)間排序

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

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

比較排序

:僅僅使用比較來(lái)比較各項(xiàng)的相對(duì)順序

.?

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

堆排序.我們見(jiàn)過(guò)的比較排序的最好的最壞運(yùn)行時(shí)間是O(nlgn).

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

決策樹(shù)

可以幫助我們回答這個(gè)問(wèn)題

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

i:j

i,j

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

≤aj時(shí)的比較序列

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

≥aj時(shí)的比較序列

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

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

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

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

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

.排序

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

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

.排序

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

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

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

=

路徑的長(zhǎng)度.最壞運(yùn)行時(shí)間

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

樹(shù)肯定包含≥n!個(gè)葉子,因?yàn)橛衝!種可能的排列.高度h

的二叉樹(shù)有≤2h個(gè)葉子.因此,n!≤2h.(lg

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

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

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

各項(xiàng)之間不進(jìn)行比較.?輸入:A[1..n],A[j]∈{1,2,…,k}.?輸出:B[1..n],有序.?輔助存儲(chǔ):C[1..k].2/1/2023算法設(shè)計(jì)與分析-線性時(shí)間排序11線性時(shí)間排序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è)計(jì)與分析-線性時(shí)間排序12計(jì)數(shù)排序2/1/2023算法設(shè)計(jì)與分析-線性時(shí)間排序13計(jì)數(shù)排序舉例fori←1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

downto

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

downto

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

downto

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

downto

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

downto

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

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

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

的時(shí)間是

Ω(nlgn)

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

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

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

發(fā)源

:HermanHollerith為

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

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

最低位開(kāi)始排序

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

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

按照t位排序

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

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

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

兩個(gè)t

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

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

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

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

計(jì)數(shù)排序使用

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

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

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

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

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

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

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

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

.例子

(32-比特?cái)?shù)):?

對(duì)

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

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

缺點(diǎn):

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

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

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

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

=

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

=

值.?算法

=

機(jī)器

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

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

穿孔?

手壓閱讀器?

轉(zhuǎn)盤(pán)計(jì)數(shù)器?

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

操作員插入一個(gè)卡片。?

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

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

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

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