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

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

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

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

5、wnto 18 do BCAj Aj9 CAj CAj - 110計數排序過程1211計數排序過程3412計數排序過程56算法說明在第9-11行中的for循環部分，把每個元素Aj放在輸出數組B中與其相應的最終位置上。如果所有n個元素都不相同，則當第一次執行到第9行時，對每個Aj，值CAj即為Aj在輸出數組中的最終正確位置，因為共有CAj個元素小于等于Aj。由于各個元素可能不一定是不同的，因此，每當將一個值Aj放入數組B中時，都要減少CAj的值。這會使得下一個其值等于Aj的輸入元素（如果存在的話）直接進入數組B中Aj的前一個位置上14計數排序時間代價計數排序時間代價算法第12行的for循環所花時

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

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

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

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

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

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

12、代碼中，假設輸入是個含n個元素的數組A，且每個元素滿足0 Ai1。另外還需要一個輔助數組B0.n-1來存放鏈表實現的桶，并假設可以用某種機制來維護這些表。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個數的輸入數組上的操作過程。(a)輸入數組A1.10。(b

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

14、的運行時間除第5行外，所有各行在最壞情況的時間都是O(n)。唯一需要分析的部分就在于第5行中插入排序所花的時間。為分析調用插入排序的時間代價，設n_i為表示桶Bi中元素個數的隨機變量。因為插入排序以二次時間運行，因而桶排序的運行時間： n 1T (n) (n) O(ni2 )i 0對上式兩邊取期望，并利用期望的線性性質，n 1 i 0 桶排序算法的運行時間下式iEn 2 2 1 / n對i=0，1，n-1是成立的。每一個桶i有相同的值 Eni2 是不足為奇的，因為輸入數組A中的每一個值都是等可能地落在任何桶內的。為了證明上式，我們定義指示器隨機變量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 k