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

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