線性時間排序

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

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

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

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

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

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

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

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

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

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

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

12、個元素滿足0 Ai1。另外還需要一個輔助數(shù)組B0.n-1來存放鏈表實現(xiàn)的桶，并假設(shè)可以用某種機制來維護這些表。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 桶排序過程下圖演示了桶排序作用于有10個數(shù)的輸入數(shù)組上的操作過程。(a)輸入數(shù)組A1.10。(b)在該算法的第5行后的有序表(桶)數(shù)組B0.9。

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

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