線性時(shí)間排序培訓(xùn)課件

1、第8章章：線性時(shí)間排序2本章內(nèi)容介紹了幾種O(nlgn)的排序算法：合并排序和堆排序達(dá)到此上界；快速排序平均情況下達(dá)到此上界；比較排序算法的下界線性時(shí)間排序：計(jì)數(shù)排序（Counting Sort）基數(shù)排序（Radix Sort）桶排序（Bucket Sort）38.1 排序算法的下界比較排序算法的作用比較排序算法僅用來確定輸入序列的元素間次序，即給定兩個(gè)元素ai和aj, 測(cè)試ai aj 中哪一個(gè)成立。48.1 排序算法的下界決策樹模型比較排序可以被抽象的視為決策樹。一棵決策樹是一棵滿二叉樹，表示某排序算法作用于給定輸入所做的所有比較。(6,8,5)5決策樹在決策樹中，對(duì)每個(gè)內(nèi)結(jié)點(diǎn)都注明i：j，

2、其中1i，jn，n是輸入序列中的元素個(gè)數(shù)。對(duì)每個(gè)葉結(jié)點(diǎn)都注明排列(1),(2),(n)。排序算法的執(zhí)行對(duì)應(yīng)于遍歷一條從樹的根到葉結(jié)點(diǎn)的路徑。在每個(gè)內(nèi)節(jié)結(jié)點(diǎn)處要做比較要使排序算法能正確的工作，其必要條件是，n個(gè)元素的n!種排列中的每一種都要作為決策樹的一個(gè)葉子而出現(xiàn)。ai a j6最壞情況下界在決策樹中，從根到任意一個(gè)可達(dá)葉節(jié)點(diǎn)之間最長(zhǎng)路徑的長(zhǎng)度，表示對(duì)應(yīng)的排序算法中最壞情況下的比較次數(shù)。這樣，一個(gè)比較排序算法中的最壞情況比較次數(shù)就與其決策樹的高度相等。定理8.1 任意一個(gè)比較排序算法在最壞情況下，都需要(nlgn)次的比較。于2 ，則有n!l 2定理8.1的證明證明：對(duì)于一棵每個(gè)排列都作為一個(gè)

3、可達(dá)葉結(jié)點(diǎn)出現(xiàn)的決策樹，根據(jù)前面的討論即可確定其高度?？紤]一棵高度為h的、具有l(wèi)個(gè)可達(dá)葉結(jié)點(diǎn)的決策樹，它對(duì)應(yīng)于對(duì)n個(gè)元素所做的比較排序。因?yàn)閚個(gè)輸入元素共有n!種排列，每一種都作為一個(gè)葉子出現(xiàn)在樹中，故有n!l。又由于在一棵高為h的二叉樹中，葉子的數(shù)目不多對(duì)該式取對(duì)數(shù)，得到hlg(n!)=(nlgn)推論8.2堆排序和歸并排序是漸進(jìn)最優(yōu)的比較算法證明：堆排序和歸并排序的運(yùn)行時(shí)間上界O(nlgn)與定理8.1給出的最壞情況下界 (nlgn)一致7hh88.2 計(jì)數(shù)排序計(jì)數(shù)排序假設(shè)n個(gè)輸入元素中的每一個(gè)都是介于0到k之間的整數(shù)，此處k為某個(gè)整數(shù)，當(dāng)k=O(n)時(shí)，技術(shù)排序的運(yùn)行時(shí)間是O(n)。計(jì)數(shù)

4、排序的基本思想就是對(duì)每一個(gè)輸入元素x，確定出小于x的元素個(gè)數(shù)。有了這一信息，就可以 把x直接放到它在最終輸出數(shù)組中的位置上。在計(jì)數(shù)排序算法中，我們假設(shè)輸入時(shí)隔數(shù)組A1.n，length(A)=n。另外還需要兩個(gè)數(shù)組：存放排序結(jié)果的B1.n，以及提供臨時(shí)存數(shù)區(qū)的C1.k9計(jì)數(shù)排序程序COUNT-SORT(A,B,k)1 for i0 to k2 do Ci03 for j1 to lengthA4 do CAj CAj + 15 Ci 現(xiàn)在包含等于i的元素個(gè)數(shù)6for i 1 to k7 do Ci Ci + Ci - 18 Ci現(xiàn)在包含小于或等于i的元素個(gè)數(shù)7 for j lengthA do

5、wnto 18 do BCAj Aj9 CAj CAj - 110計(jì)數(shù)排序過程1211計(jì)數(shù)排序過程3412計(jì)數(shù)排序過程56算法說明在第9-11行中的for循環(huán)部分，把每個(gè)元素Aj放在輸出數(shù)組B中與其相應(yīng)的最終位置上。如果所有n個(gè)元素都不相同，則當(dāng)?shù)谝淮螆?zhí)行到第9行時(shí)，對(duì)每個(gè)Aj，值CAj即為Aj在輸出數(shù)組中的最終正確位置，因?yàn)楣灿蠧Aj個(gè)元素小于等于Aj。由于各個(gè)元素可能不一定是不同的，因此，每當(dāng)將一個(gè)值A(chǔ)j放入數(shù)組B中時(shí)，都要減少CAj的值。這會(huì)使得下一個(gè)其值等于Aj的輸入元素（如果存在的話）直接進(jìn)入數(shù)組B中Aj的前一個(gè)位置上14計(jì)數(shù)排序時(shí)間代價(jià)計(jì)數(shù)排序時(shí)間代價(jià)算法第12行的for循環(huán)所花時(shí)

6、間為(k)。第34行中for循環(huán)所花時(shí)間為(n)，第67行for循環(huán)所花時(shí)間為(k)，第911行的for循環(huán)所花時(shí)間為(n)。這樣，總的時(shí)間就是(k+n)。實(shí)踐中，當(dāng)k=O(n)時(shí)，運(yùn)行時(shí)間為O(n)。計(jì)數(shù)排序的特點(diǎn)計(jì)數(shù)排序算法沒有用到元素間的比較，它利用元素的實(shí)際值來確定它們?cè)谳敵鰯?shù)組中的位置，不是一個(gè)基于比較的排序算法，從而它的計(jì)算時(shí)間下界不再是(nlogn)由于算法第4行使用了downto語句，經(jīng)計(jì)數(shù)排序，輸出序列中值相同的元素之間的相對(duì)次序與他們?cè)谳斎胄蛄兄械南鄬?duì)次序相同，因此計(jì)數(shù)排序算法是一個(gè)穩(wěn)定的排序算法。在衛(wèi)星數(shù)據(jù)排序和基數(shù)排序中間應(yīng)用。158.3 基數(shù)排序基數(shù)排序(radix

7、sort)是一種用在老式穿卡機(jī)上的算法。一張卡片有80列，每列可在12個(gè)位置中的任一處穿孔。排序器可被機(jī)械地“程序化”以檢查每一迭卡片中的某一列，再根據(jù)穿孔的位置將它們分放12個(gè)盒子里。這樣，操作員就可逐個(gè)地把它們收集起來。其中第一個(gè)位置穿孔的放在最上面，第二個(gè)位置穿孔的其次，等等。 對(duì)十進(jìn)制數(shù)字來說，每列中只用到10個(gè)位置(另兩個(gè)位置用于編碼非數(shù)值字符)。一個(gè)d位數(shù)占用d個(gè)列。因?yàn)榭ㄆ判蚱饕淮沃荒懿榭匆粋€(gè)列，要對(duì)n張片上的d位數(shù)進(jìn)行排序就要有個(gè)排序算法。直覺上，大家可能覺得應(yīng)該按最重要的一位排序，然后對(duì)每個(gè)盒子中的數(shù)遞歸地排序，最后把結(jié)果合并起來。與人們的直覺相反，基數(shù)排序是首先按最低有效

8、位數(shù)字進(jìn)行排序，以解決卡片排序問題。RADIX-SORT(A,d)1 for i 1 to ddo use a stable sort to sort array A on digit i168.3 基數(shù)排序例子17基數(shù)排序定理引理8.3 給定n個(gè)d位數(shù)，每一個(gè)數(shù)可以取k中可能的值。如果所用的穩(wěn)定排序需要(n+k)的時(shí)間，基數(shù)排序算法能以(d(n+k)的時(shí)間正確的對(duì)這些數(shù)進(jìn)行排序證明：基數(shù)排序的正確性可以通過對(duì)正在被排序的列進(jìn)行歸納而加以證明。對(duì)本算法時(shí)間代價(jià)的分析要取決于選擇哪一種穩(wěn)定的中間排序算法。當(dāng)每位數(shù)字都界于0到k-1之間，且k不太大時(shí)，可以選擇計(jì)數(shù)排序。對(duì)n個(gè)d位數(shù)的每一遍處理的時(shí)

9、間為(n+k)，共有d遍，故基數(shù)排序的總時(shí)間為(d(n+k)時(shí)間內(nèi)正確的對(duì)這 2/b r n RADIX-SORT能在 2n 序的每一遍需要時(shí)間為(n+k)= ，共有18基數(shù)排序定理引理8.4 給定n個(gè)b位數(shù)和任何正整數(shù)rb，些數(shù)進(jìn)行排序。例如：可以將一個(gè)32位的字視為有4個(gè)8位的數(shù)字，于是有b=32, r=8, k=2r-1=r8-1=255,d=b/r=4.r證明：對(duì)于以一個(gè)值rb，將每個(gè)關(guān)鍵字看做是有 d b / r 個(gè)數(shù)字，每個(gè)數(shù)字都包含r位。每一個(gè)數(shù)字都是介于0到 2r 1之間的一個(gè)整數(shù)，這樣就可以采用基數(shù)排序，此處k= 2 r 1。計(jì)數(shù)排rd遍，總的運(yùn)行時(shí)間為 b / r n 2r

10、 定理說明對(duì)于給定的n值和b值，我們希望所選擇的r值（rb）能夠最小化表達(dá)式(b/r)(n+2r)(n)。于是，選擇r=b得到的運(yùn)行時(shí)間為(b/b)(n+rb)=(n),從漸進(jìn)意義上來看，這一時(shí)間是最優(yōu)的。子內(nèi)的最佳時(shí)間，如此選擇得到的運(yùn)行時(shí)間為lg nlg n 20基數(shù)排序時(shí)間基數(shù)排序是否要比基于比較的排序算法更好？如果根據(jù)常見的情況有b=O(lgn)并選擇rlgn，則基數(shù)排序的運(yùn)行時(shí)間為O(n)，這看上去要比快速排序的平均情況時(shí)間O(nlgn)更好些。在這兩個(gè)時(shí)間中隱含在O記號(hào)中的常數(shù)因子是不同的。對(duì)于要處理的n個(gè)關(guān)鍵字，盡管基數(shù)排序執(zhí)行的遍數(shù)可能要比快速排序要少，但每一遍所需的時(shí)間都要長(zhǎng)

11、得多。此外，利用計(jì)數(shù)排序作為中間穩(wěn)定排序的基數(shù)排序不是原地排序，而很多O(nlgn)時(shí)間的比較排序算法則可以做到原地排序。因此當(dāng)內(nèi)存容量比較寶貴時(shí)，像快速排序這樣的原地排序算法可能是更為可取的。8.4 桶排序平均情況下桶排序以線性時(shí)間運(yùn)行假設(shè)輸入由一個(gè)隨機(jī)過程產(chǎn)生，該過程將元素一致地分布在區(qū)間0，1)上。桶排序的思想就是把區(qū)間0，1)劃分成n個(gè)相同大小的子區(qū)間，或稱桶。然后，將n個(gè)輸入數(shù)分布到各個(gè)桶中去。因?yàn)檩斎霐?shù)均勻且獨(dú)立均勻分布在0，1)上，所以，一般不會(huì)有很多數(shù)落在一個(gè)桶中的情況。為得到結(jié)果，先對(duì)各個(gè)桶中的數(shù)進(jìn)行排序，然后按次序把各個(gè)桶中的元素列出來即可。228.4 桶排序在桶排序算法的

12、代碼中，假設(shè)輸入是個(gè)含n個(gè)元素的數(shù)組A，且每個(gè)元素滿足0 Ai1。另外還需要一個(gè)輔助數(shù)組B0.n-1來存放鏈表實(shí)現(xiàn)的桶，并假設(shè)可以用某種機(jī)制來維護(hù)這些表。BUCKET-SORT(A)1 nlengthA2 for i 1 to n4 for i 0 to n-15 do sort list Bi with insertion sort6 concatenate the lists B0，B1，Bn-1together in order3 do insert Ai into list B nAi 23桶排序過程下圖演示了桶排序作用于有10個(gè)數(shù)的輸入數(shù)組上的操作過程。(a)輸入數(shù)組A1.10。(b

13、)在該算法的第5行后的有序表(桶)數(shù)組B0.9。桶i中存放了區(qū)間i/10，(i+1)/10上的值。排序輸出由表BO、B1、.、B9的按序并置構(gòu)成。24桶排序算法的正確性給任意兩個(gè)元素Ai和Aj，不失一般性，假設(shè)AiAj。由于floor(nAi)floor(nAj)。，元素Ai或者被放入Aj所在桶中，或者被放入一個(gè)下表更小的桶中。如果Ai和Aj落入同一個(gè)桶中，則第4-5行中的for循環(huán)會(huì)將它們按適當(dāng)?shù)捻樞蚺帕小Ｈ绻鸄i和Aj落入了不同的桶中，則第6行將它們按適當(dāng)?shù)捻樞蚺帕?，因此，桶排序是能正確工作的。 (n) E O(ni2 ) (n) O E (ni2 )25n 1i 0n 1i 0桶排序算法

14、的運(yùn)行時(shí)間除第5行外，所有各行在最壞情況的時(shí)間都是O(n)。唯一需要分析的部分就在于第5行中插入排序所花的時(shí)間。為分析調(diào)用插入排序的時(shí)間代價(jià)，設(shè)n_i為表示桶Bi中元素個(gè)數(shù)的隨機(jī)變量。因?yàn)椴迦肱判蛞远螘r(shí)間運(yùn)行，因而桶排序的運(yùn)行時(shí)間： n 1T (n) (n) O(ni2 )i 0對(duì)上式兩邊取期望，并利用期望的線性性質(zhì)，n 1 i 0 桶排序算法的運(yùn)行時(shí)間下式iEn 2 2 1 / n對(duì)i=0，1，n-1是成立的。每一個(gè)桶i有相同的值 Eni2 是不足為奇的，因?yàn)檩斎霐?shù)組A中的每一個(gè)值都是等可能地落在任何桶內(nèi)的。為了證明上式，我們定義指示器隨機(jī)變量X ij I A j落在桶i中其中，i=0,1,n-1, j=1,2,n。于是，nj 1項(xiàng)進(jìn)行重新組合：26 EX E X ij2 E X ij2 1* 0* 1 1 1E n j 1 1 j n 1 k