線性時間排序ppt課件

1、算法設(shè)計與分析2022年7月18日講授內(nèi)容：動態(tài)規(guī)劃I教師：胡學(xué)鋼、吳共慶至今為止，我們見過的排序都是 比較排序 : 僅僅運(yùn)用比較來比較各項的相對順序 . 比如：插入排序,合并排序,快速排序, 堆排序.我們見過的比較排序的最好的最壞運(yùn)轉(zhuǎn)時間是O(nlgn). O(nlgn)是不是我們能做到的極限? 決策樹 可以協(xié)助我們回答這個問題 . 排序可以做到多快？排序a1, a2, , an每個內(nèi)部節(jié)點(diǎn)標(biāo)識為 i:j i, j 1, 2, n.左子樹表示當(dāng)ai aj時的比較序列 .右子樹表示當(dāng)ai aj時的比較序列 .決策樹舉例排序 a1, a2, a3= 9 , 4 , 6 :每個內(nèi)部節(jié)點(diǎn)標(biāo)識為i:j

2、,i,j1, 2, n.左子樹表示當(dāng)aiaj時的比較序列 .右子樹表示當(dāng)aiaj時的比較序列 .決策樹舉例每個內(nèi)部節(jié)點(diǎn)標(biāo)識為i:j,i,j1, 2, n.左子樹表示當(dāng)aiaj時的比較序列 .右子樹表示當(dāng)aiaj時的比較序列 .排序 a1, a2, a3= 9 , 4 , 6 :決策樹舉例每個內(nèi)部節(jié)點(diǎn)標(biāo)識為i:j,i,j1, 2, n.左子樹表示當(dāng)aiaj時的比較序列 .右子樹表示當(dāng)aiaj時的比較序列 .排序 a1, a2, a3= 9 , 4 , 6 :決策樹舉例每個內(nèi)部節(jié)點(diǎn)標(biāo)識為i:j,i,j1, 2, n.左子樹表示當(dāng)aiaj時的比較序列.右子樹表示當(dāng)aiaj時的比較序列.排序 a1,

3、a2, a3= 9 , 4 , 6 :決策樹舉例 決策樹可以模擬任何的比較排序的執(zhí)行過程:每個輸入大小為n的序列都可以用這棵樹表示. 將算法視為每次兩個項相比后就分叉.樹包含了一切能夠比較的指令途徑.算法的運(yùn)轉(zhuǎn)時間 = 途徑的長度.最壞運(yùn)轉(zhuǎn)時間 = 樹的高度.決策樹模型定理.對n個項排序的任何決策樹的高度是(nlgn).證明. 樹一定包含n!個葉子, 由于有n!種能夠的陳列. 高度h 的二叉樹有2h個葉子. 因此,n! 2h.(lg 單調(diào)遞增)(Stirlings 公式)決策樹排序的下界 推論.在最差情況下，任何一種比較排序至少需求O(nlogn)比較操作。這是比較操作所獲的信息有限所導(dǎo)致的，

4、或者說是全序集的模糊代數(shù)構(gòu)造所導(dǎo)致的。從這個意義上講，堆排序和合并排序是漸進(jìn)最正確的比較排序算法 .比較排序的下界計數(shù)排序: 各項之間不進(jìn)展比較.輸入: A1 . . n, Aj1, 2, , k.輸出: B1 . . n, 有序.輔助存儲: C1 . . k.線性時間排序for i1 to k do Ci 0for j1 to n do CAj CAj + 1 Ci = |key = i|for i2 to k do Ci Ci + Ci1 Ci = |key i|for jn downto1 do BCAj Aj CAj CAj 1計數(shù)排序計數(shù)排序舉例for i1 to k do Ci 0

5、循環(huán)1for j1 to n do CAj CAj + 1 Ci = |key = i|循環(huán)2for j1 to n do CAj CAj + 1 Ci = |key = i|循環(huán)2for j1 to n do CAj CAj + 1 Ci = |key = i|循環(huán)2for j1 to n do CAj CAj + 1 Ci = |key = i|循環(huán)2for j1 to n do CAj CAj + 1 Ci = |key = i|循環(huán)2for i2 to k do Ci Ci + Ci1 Ci = |key i|循環(huán)3for i2 to k do Ci Ci + Ci1 Ci = |ke

6、y i|循環(huán)3for i2 to k do Ci Ci + Ci1 Ci = |key i|循環(huán)3for jn downto 1 do BCAj Aj CAj CAj 1循環(huán)4for jn downto 1 do BCAj Aj CAj CAj 1循環(huán)4for jn downto 1 do BCAj Aj CAj CAj 1循環(huán)4for jn downto 1 do BCAj Aj CAj CAj 1循環(huán)4for jn downto 1 do BCAj Aj CAj CAj 1循環(huán)4forforforfortototodowntododododo分析假設(shè) k = O(n), 那么計數(shù)排序用的時

7、間為 (n).但是, 排序的時間是(nlgn)!問題出在什么地方?答案:比較排序 的時間是 (nlgn) .計數(shù)排序不是 比較排序.實(shí)踐上, 各項之間根本沒有比較!運(yùn)轉(zhuǎn)時間計數(shù)排序是一種穩(wěn)定排序: 它會堅持相等的項的相對順序. 練習(xí):哪種其他的排序有這種特征?穩(wěn)定排序 發(fā)源 : Herman Hollerith 為 1890年美國人口普查設(shè)計的卡排序機(jī) (參考附錄)一位一位的排序. Hollerith 最初(不好)的想法:從最高位開場排序.好的想法:運(yùn)用輔助的穩(wěn)定排序方法從 最低位開場排序 .基數(shù)排序基數(shù)排序過程數(shù)位推導(dǎo) 假設(shè)數(shù)字曾經(jīng)按照其低階t 1位排序. 按照t位排序 基數(shù)排序的正確性數(shù)位

8、推導(dǎo)假設(shè)數(shù)字曾經(jīng)按照其低階t1位排序.按照t位排序 兩個在位t不同的數(shù)被正確排序.基數(shù)排序的正確性數(shù)位推導(dǎo)假設(shè)數(shù)字曾經(jīng)按照其低階t 1位排序.按照t位排序 兩個在位t不同的數(shù)被正確排序. 兩個t 位一樣的數(shù)堅持與輸入一樣的次序 正確的順序.基數(shù)排序的正確性假設(shè)運(yùn)用計數(shù)排序作為輔助的穩(wěn)定排序方法。 對n個b比特字進(jìn)展排序。每個字可以看成有b/r個以2r為基的數(shù).例子: 32-位字r =8b/r=4遍基于28位的計數(shù)排序; 或者r=16b/r=2遍基于216位的計數(shù)排序.我們要作多少遍?基數(shù)排序分析回想: 計數(shù)排序運(yùn)用 (n + k)的時間對n個范圍在0到k1的數(shù)進(jìn)展排序。假設(shè)每個b-位字分成r-

9、比特份,每遍計數(shù)排序破費(fèi) (n + 2r).由于有b/r遍,我們有選擇r使得T(n,b)最小:添加r意味著更少的遍數(shù),但是由于 rlgn,時間成指數(shù)增長?；鶖?shù)排序分析續(xù)經(jīng)過求導(dǎo)并將方程置0求得最小值T(n,b) 。.或者, 察看我們不要2rn ,在滿足這個限制的條件下選擇盡能夠大的r對對稱性沒有影響。選擇r =lgn意味著T(n,b)= (bn/lgn). 對于界于在0到nd1的數(shù),我們有b =dlgn 基數(shù)排序運(yùn)轉(zhuǎn)時間為 (dn).選擇r實(shí)踐上, 在大量輸入的情況下，基排序速度很快，算法也很容易編碼和維護(hù) .例子 (32-比特數(shù)): 對 2000個數(shù)排序適宜最多走3遍. 合并排序和快速排序至

10、少要 lg2000 =11遍. 缺陷: 與快速排序不同, 基排序根本上沒有援用部分性, 這樣在現(xiàn)代的處置器上一個調(diào)優(yōu)的快速排序，利用內(nèi)存的分層體系，可以在性能上超越基數(shù)排序。結(jié)論Herman Hollerith (1860-1929)穿孔卡Hollerith 的制表系統(tǒng)排序工人的操作基數(shù)排序來源“現(xiàn)代的IBM卡片關(guān)于穿孔卡技術(shù)的網(wǎng)絡(luò)資源 附錄: 穿孔技術(shù)在1880年美國人口普查破費(fèi)了近10年的時間處置.在 MIT擔(dān)任講師期間,Hollerith發(fā)明了穿孔卡技術(shù)的原型.他的機(jī)器,包括一個“卡排序員 ,使得1890的統(tǒng)計結(jié)果在6個周的時間內(nèi)就處置完了。他在1911年創(chuàng)建了制表機(jī)器公司，這個公司在1

11、924年和其他公司合并后組成了國際商用機(jī)器公司(IBM).Herman Hollerith(1860-1929)穿孔卡 = 數(shù)據(jù)記錄.洞 = 值. 算法 = 機(jī)器 +操作員.1900 美國人口普查運(yùn)用的穿孔卡的復(fù)制品. Howells 2000穿孔卡Holleriths 制表系統(tǒng)圖片請參考Howells 2000. 穿孔 手壓閱讀器 轉(zhuǎn)盤計數(shù)器 排序盒圖片請參考Howells 2000.圖片請參考Howells 2000. 操作員插入一個卡片。 按住穿過穿孔卡的孔的鍵，使得電流接觸卡下面的水銀杯. 每當(dāng)一個數(shù)位被穿孔后, 對應(yīng)排序盒的蓋子升起。 操作員將卡片放入盒子并且合上蓋子. 當(dāng)一切的卡片

12、處置終了后, 前端的面板翻開 ,卡片曾經(jīng)安裝順序排放, 完成了一遍穩(wěn)定排序。排序員的操作Hollerith在1889年的最初專利展現(xiàn)了最高位優(yōu)先的基數(shù)排序:“The most complicated combinations can readily be counted with comparatively few counters or relays by first assorting the cards according to the first items entering into the combinations, then reassorting each group according to the second item entering into the combination, and so on, and finally counting on a few counters the last item of the combination for each group of cards.最低位優(yōu)先的基數(shù)排序好似是由一位機(jī)器操作員發(fā)明的?；鶖?shù)排序的來源 每列一個字符.請看 WWW Virtual Punch