算法設(shè)計與分析線性時間排序.ppt

算法設(shè)計與分析,譚守標(biāo) 安徽大學(xué) 電子學(xué)院 2007.9,第七章 線性時間排序,排序算法的下界 計數(shù)排序（過程及分析） 基數(shù)排序 桶排序（過程及分析） 程序演示及說明,排序算法的下界,決策樹 最壞情況下界 定理9.1 推論9.2,決策樹,決策樹表示了某種排序算法作用于給定輸入上所做的所有比較,而控制結(jié)構(gòu),數(shù)據(jù)移動等則被忽略。,最壞情況下界,在決策樹中,由根到任一葉節(jié)點間最長路徑的長度表示了對應(yīng)的排序算法中最壞情況比較次數(shù)。這樣, 一個比較排序算法中的最壞情況比較次數(shù)就與其決策樹的高度對應(yīng), 同時關(guān)于其決策樹高度的下界也就是關(guān)于比較排序算法運行時間的下界。,定理9.1,定理:任意一棵對n個元素排序的決策樹有高度 (nlgn) 。 證明: 考慮對n個元素排序的, 高度為h的決策樹。因為n!種排列, 每種排列代表一種不同的最終排序, 故該樹必須至少有n!片葉子。又一顆高度為h的二叉樹的葉子數(shù)不多于2h, 則: n! 2h 兩邊取對數(shù), 有: h lg(n!),定理9.1,因為lg函數(shù)是單調(diào)遞增的, 又根據(jù)Stirling近似公式, 有: n! (n/e)n 所以, 有: h lg(n/e)n = nlgn nlge = (nlgn),推論9.2,推論: 堆排序和合并排序是漸進(jìn)最優(yōu)的比較算法。 證明:堆排序和合并排序的運行時間上界O(nlgn)與定理9.1給出的最壞情況下界 (nlgn)一致。,計數(shù)排序（過程及分析）,計數(shù)排序思路 計數(shù)排序算法 計數(shù)排序分析,計數(shù)排序思路,計數(shù)排序假設(shè)n個輸入中的每一個都是介于1到k之間的整數(shù), 此處k是整數(shù)。 計數(shù)排序的基本思想就是對每一個元素x,確定出小于x的元素數(shù)。有了這個信息就可把x直接放到它在最終輸出數(shù)組中的位置上。例如有17個元素小于x,則x就屬于第18個輸出位置。 如果有相等的元素怎么辦？,計數(shù)排序算法,COUNTING_SORT(A, B, k) 1 for i 1 to k 2 do Ci 0 3 for j 1 to lengthA 4 do CAj CAj+1 5 Ci現(xiàn)在包含等于i的元素個數(shù) 6 for i 2 to k 7 do Ci Ci+Ci-1 8 Ci現(xiàn)在包含小于等于i的元素個數(shù) 9 for j lengthA downto 1 10 do BCAj Aj 11 CAj CAj-1,計數(shù)排序算法,計數(shù)排序分析,計數(shù)排序的時間分析, 第1-2行的for循環(huán)花費的時間為O(k), 第3-4行中for循環(huán)所花費時間為O(n),第6-7行的for循環(huán)花費的時間為O(k)。這樣，總的時間就是O(k+n)。在實踐中，當(dāng)k= O(n)時，我們常常采用計數(shù)排序，這時其運行時間為O(n)。,基數(shù)排序（過程及分析）,基數(shù)排序思想 基數(shù)排序算法 基數(shù)排序分析,基數(shù)排序思想,每種數(shù)字?jǐn)?shù)據(jù)都是一種進(jìn)位計數(shù)制數(shù)據(jù)，如二進(jìn)制、十進(jìn)制等，每一位的取值范圍即基數(shù)。 基數(shù)排序的思想就是在某種進(jìn)制下對所有數(shù)據(jù)從低位到高位逐位進(jìn)行排序，最終就能得到整體排序的結(jié)果。,基數(shù)排序算法,基數(shù)排序算法,RADIX_SORT(A, d) 1 for i 1 to d 2 do 使用一種穩(wěn)定的排序方法來對 數(shù)組A按第i位數(shù)字進(jìn)行排序,基數(shù)排序分析,正確性：歸納證明 時間代價： 當(dāng)每位數(shù)字都介于1-k之間，且k不太大時，可以選擇計數(shù)排序。 每一位上的處理時間為： (n+k) 總時間為： (d(n+k)， 當(dāng)d為常量，k= (n)時， (d(n+k)= (n),基數(shù)排序例,以一個計算機(jī)字(16位)為基數(shù)，一個64位數(shù)則為4位數(shù)，即d=4， k=216，用基數(shù)排序只需4次。,桶排序（過程及分析）,桶排序思想 桶排序算法 桶排序分析,桶排序思想,桶排序的思想就是把區(qū)間0, 1)劃分成n個相同大小的子區(qū)間, 或稱桶, 然后將n個輸入數(shù)分布到各個桶中去。如果輸入數(shù)均勻分布在0, 1)上, 則一般不會有很多數(shù)落在一個桶中。為得到結(jié)果, 先對各個桶中的數(shù)進(jìn)行排序, 然后按次序把各個桶中的元素列出來即可。,桶排序算法,BUCKET_SORT(A) 1 n lengthA 2 for i 1 to n 3 do 將Ai插入到表B nAi 4 for i 0 to n-1 5 do 用插入排序?qū)Ρ鞡i進(jìn)行排序 6 將表B0, B1, ., Bn-1按順序合并,桶排序算法,桶排序分析,正確性：反證法 時間代價：,桶排序分析,排序算法穩(wěn)定性,若待排序的序列中，存在多個具有相同值的元素，經(jīng)過排序，這些元素的相對次序保持不變，則稱該算法是穩(wěn)定的；若經(jīng)排序后，元素的相對 次序發(fā)生了改變，則稱該算法是不穩(wěn)定的。,常見排序算法的穩(wěn)定性,堆排序算法 不穩(wěn)定 快速排序算法 不穩(wěn)定 歸并排序算法 穩(wěn)