計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第4章 不基於比較的排序算法

第4章

不基於比較的排序算法1序言

2比較排序的復(fù)雜度下界

3不基於比較的線性時(shí)間排序算法

19計(jì)數(shù)排序

19基數(shù)排序

27桶排序

3121.序言可以證明，任何比較排序在最壞情況時(shí)需要至少lg(n!)

nlgn

次比較。要想有更快的排序算法，必須考慮不基於比較的排序。不基於比較的排序往往有額外的條件限制。主要討論：

計(jì)數(shù)排序

基數(shù)排序

桶排序32.比較排序的復(fù)雜度下界

決策樹模型及最壞情況下界

很多問題的決策是對(duì)輸入數(shù)據(jù)作一系列某個(gè)操作決定的。每次操作會(huì)有若干個(gè)可能的結(jié)果，而下次操作如何進(jìn)行是根據(jù)這一次操作的結(jié)果而定，直到得到答案。這可用一個(gè)決策樹來描述。任何基於比較的排序都是通過一系列數(shù)字間的比較來決定輸入數(shù)據(jù)之間大小關(guān)系的，因此可以用一棵決策樹來描述。證明排序問題的下界，我們只需考慮輸入的n個(gè)數(shù)都不相等的情況。這是因?yàn)獒槍?duì)一個(gè)特殊情況的下界也一定是包含所有情況的下界。我們將證明，即使需要排序的n個(gè)數(shù)都不相等，任何基於比較的排序算法，在最壞情況時(shí)，都必須做至少

lg(n!)

nlgn次比較。

4例（圖4.1）：一個(gè)把a(bǔ)1,a2,a3

排序的決策樹有n個(gè)不同數(shù)的序列中，最小的數(shù)稱為第1順序數(shù)，第2小的數(shù)稱為第2順序數(shù)，…，第n個(gè)小的數(shù)(即最大的數(shù))稱為第n順序數(shù)。排序就是確定在原序列中，那個(gè)是第1順序數(shù)，那個(gè)是第2順序數(shù)，…，那個(gè)是第n順序數(shù)。所以，排序的本質(zhì)是給出n個(gè)順序數(shù)在原序列中的一個(gè)排列。(接下頁(yè))5決策樹模型及最壞情況下界(繼續(xù))每個(gè)葉結(jié)點(diǎn)代表了一個(gè)從輸入序列A[1]，A[2]，…，A[n]，到輸出序列

B[1]<B[2]

<…

<B[n]的映射。如果B[j]=A[i]，那么，A[i]就是第j順序數(shù)(1

i

n)。我們可以定義這個(gè)映射函數(shù)為：

(i)=j。比如，圖4-1中葉結(jié)點(diǎn)(1,3,2)表示A[1]<A[3]<A[2]。這個(gè)映射函數(shù)是：

(1)=1，

(2)=3，

(3)=2。因?yàn)檩斎氲膎個(gè)數(shù)都不相等，它們只能有一個(gè)排序結(jié)果，所以一個(gè)葉結(jié)點(diǎn)只能代表一個(gè)映射。因?yàn)橐粋€(gè)映射正好等于一個(gè)n個(gè)元素的全排列，所以有n!個(gè)不同的映射。因此，決策樹必須至少有n!個(gè)葉子來代表這些不同的映射。如n個(gè)數(shù)不等，可證明排序決策樹必須正好有n!個(gè)葉子（見書）。6定理4.1

任一個(gè)比較排序算法，在最壞情況時(shí)，需要至少

lg(n!)

次比較。證明：由上面討論，任何比較排序算法所對(duì)應(yīng)的決策樹必須有n!個(gè)葉子。設(shè)這個(gè)決策樹的高是h。因?yàn)楦叨葹閔的二叉樹最多有2h個(gè)葉子，所以必有關(guān)系：2h

≥n!，也就是h

lg(n!)。因?yàn)閔是整數(shù)，所以有

h

lg(n!)。這說明，有一個(gè)葉子的深度（depth）是h。那么，如果算法從樹根開始，經(jīng)過一系列比較操作后到達(dá)這個(gè)葉子時(shí)，算法必定作了h次比較。這是因?yàn)椋惴ㄒ鲆淮伪容^才可以沿路徑前進(jìn)一步。所以，一個(gè)比較排序算法，在最壞情況時(shí)，需要至少h=

lg(n!)

次比較。

注:因

lg(n!)

nlgn，通常也說，比較排序的下界是nlgn。7下界應(yīng)用舉例例4.1

假設(shè)我們需要判定數(shù)組A[1..n]中的n個(gè)數(shù)是否有相同的數(shù)字，那么，在最壞情況時(shí)，任何基于比較的算法需要至少lg(n!)次比較。證明：

假設(shè)算法A是這樣的一個(gè)算法。設(shè)輸入的A[1..n]含n個(gè)不同數(shù)。

這些數(shù)可以排序?yàn)椋篵1

<b2<…<bn。我們不需真的去排序，但這個(gè)遞增序列肯定存在。算法A必定會(huì)判定A[1..n]中沒有相同的數(shù)字。我們斷定:算法A一定比較了b1和b2。我們用反證法證明這點(diǎn)。假設(shè)算法A沒有比較b1和b2，卻判定A[1..n]沒有相同的數(shù)字，那么我們把

b2改動(dòng)一下，讓b2等于b1，b2=b1，其余數(shù)不變。然后，把這改動(dòng)后的數(shù)組A[1..n]再讓這個(gè)算法A去判定。(接下頁(yè))8下界應(yīng)用舉例(證明繼續(xù))顯然，這個(gè)改動(dòng)不會(huì)改變?nèi)魏蝺蓚€(gè)數(shù)，bi和bj(1

i<j

n)的比較結(jié)果，除非i=1，j=2。因?yàn)榍耙淮闻卸〞r(shí)，算法沒有比較b1和b2，所以算法這一次會(huì)重復(fù)所有前一次的比較，也不會(huì)比較b1和

b2。那么，算法A必定察覺不到我們的改動(dòng)，而仍然會(huì)判定數(shù)組中沒有相同的數(shù)字。顯然，這就錯(cuò)了。反證法成功。所以，算法A必定要比較b1和b2。同理，如果b3是第3小的數(shù)，那么這個(gè)算法必定要比較b2和b3。以此類推，這個(gè)算法必須比較序列中每?jī)蓚€(gè)相鄰的數(shù)字。這就意味著，根據(jù)這個(gè)算法的比較結(jié)果，我們可以把這n個(gè)不同數(shù)字排序。因?yàn)榛诒容^的排序至少需要lg(n!)次比較，所以這個(gè)算法A也需要至少lg(n!)次比較。

9

10*二叉樹的外路徑總長(zhǎng)與平均情況下界我們先討論有Min-EPL的二叉樹的特征。引理4.3 一棵有最小外路徑總長(zhǎng)的二叉樹T必定是個(gè)完全二叉樹(fullbinarytree)，即每個(gè)內(nèi)結(jié)點(diǎn)正好有二個(gè)子結(jié)點(diǎn)。證明：反證法。如下圖(4-2)，設(shè)樹T的內(nèi)結(jié)點(diǎn)x只有一個(gè)兒子y，我們把x的兒子和x的父親相連后，刪除x。得到的新二叉樹T’有相同的葉結(jié)點(diǎn)集合而外路經(jīng)總長(zhǎng)減小，矛盾。引理得證。

11引理4.4 一棵有最小外路徑總長(zhǎng)(Min-EPL)的二叉樹T中，所有葉結(jié)點(diǎn)必定只出現(xiàn)在最底兩層。證明：反證法。由引理4.3，T是完全二叉樹，設(shè)高為h。如下圖，假設(shè)有葉子x在第k(k

h-2)層。把h-1層的點(diǎn)y的兒子a和b切下后接到x上。得到樹T’與T有相等的葉子個(gè)數(shù)。下面計(jì)算證明T’有較小EPL(T’)。EPL(T’)=EPL(T)

|原(r,x)|

|原(r,a)|

|原(r,b)|+|新(r,y)|+|新(r,a)|+|新(r,b)|=EPL(T)–k–h–h+(h-1)+(k+1)+(k+1)=EPL(T)–h+k+1

EPL(T)–h+(h-2)+1=EPL(T)–1。這與T有Min-EPL矛盾，引理得證。

12引理4.5 假設(shè)一個(gè)有最小外路徑總長(zhǎng)的二叉樹T有l(wèi)個(gè)葉結(jié)點(diǎn)，那么EPL(T)>l(

lgl

1)。證明：設(shè)樹高為h。由引理4.3和4.4，T是個(gè)完全二叉樹并且所有葉子都在最底兩層。設(shè)第(h-1)層的內(nèi)結(jié)點(diǎn)個(gè)數(shù)為

x，那么必有1

x≤2h-1。

如圖，第(h-1)層正好有2h-1–x個(gè)葉子，第h層正好有2x個(gè)葉子，總共有

l

=(2h-1–x)+2x

=2h-1

+x個(gè)葉子。因?yàn)?h-1

=l-x<

l≤2h，故有(h-1)<lgl≤h，即h=

lgl

。因?yàn)槿~子的深度至少是(h-1)，所以EPL(T)>l(h-1)=

l(

lgl

1)。引理得證。

13定理4.6

任一比較排序平均需要至少

lg(n!)

-1次比較。證明：假設(shè)T是決策樹。算法平均需要的比較次數(shù)，A(n)，等于它外路經(jīng)總和除以葉結(jié)點(diǎn)個(gè)數(shù)。從引理4.5，A(n)=EPL(T)/l>(

lgl

1)。因?yàn)閘

n!，所以A(n)>

lg(n!)

-1。

*二叉樹的全路徑總長(zhǎng)與堆排序最好情況下界引理4.7 設(shè)

T是有n個(gè)結(jié)點(diǎn)的，有最小全路徑總長(zhǎng)的，二叉樹，其高度是h。那么，除了第h-1層外，所有內(nèi)結(jié)點(diǎn)必定有兩個(gè)子結(jié)點(diǎn)。證明：反證法證。設(shè)第k(k≤h-2)層的一個(gè)內(nèi)結(jié)點(diǎn)x只有一個(gè)兒子，如下圖(4-5)。

(接下頁(yè))14注意：有最小全路徑總長(zhǎng)的二叉樹不一定是完全二叉樹。(b)

變換后的樹T’與T有相同的結(jié)點(diǎn)總數(shù)(a)

樹T中點(diǎn)x在第k層且只有一個(gè)兒子x

第k層,

k

h-2第h層(最底層)y

ba

rx

第k層第h層(最底層)y

ba

r證明（繼續(xù)）：如下圖，我們可切去底層一個(gè)葉結(jié)點(diǎn)a并把它連到x上。因?yàn)辄c(diǎn)a以外各點(diǎn)的深度不變而點(diǎn)a的深度減少，所以，變換后的樹T’有較小的全路徑總長(zhǎng)，矛盾，引理4.7得證。

15引理4.8

有n個(gè)結(jié)點(diǎn)的堆所對(duì)應(yīng)的二叉樹有最小全路徑總長(zhǎng)(Min-TPL)。證明：設(shè)T是有n個(gè)結(jié)點(diǎn)的，有Min-TPL的二叉樹，其高為h。

首先，T的所有葉子必須在最底二層。否則，如果葉子x在第k(k

h-2)層，我們可在底層切去一個(gè)葉子a，并把它連到x上。因?yàn)槌c(diǎn)a以外各點(diǎn)的深度不變而點(diǎn)a的深度減少，變換后的樹T’有較小的全路徑總長(zhǎng)，矛盾。其次，由引理4.7，除第h-1層外，所有其他內(nèi)結(jié)點(diǎn)必須有兩個(gè)子結(jié)點(diǎn)。所以，樹T

與有n個(gè)結(jié)點(diǎn)的堆H，除底層外，完全一樣。因此，樹T和堆H有相同的高度

h=lgn,并且底層的葉結(jié)點(diǎn)數(shù)也必須相等。所以，有n個(gè)結(jié)點(diǎn)的堆H也是一個(gè)有Min-TPL的二叉樹。

16定理4.9任一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹T的全路徑總長(zhǎng)大于n(

lgn

-2)。證明：假設(shè)堆的高度是h，底層(第h層)有u個(gè)葉結(jié)點(diǎn)，1≤u≤2h。如下圖(4-6)所示，從根到h-1層的頂點(diǎn)個(gè)數(shù)順序?yàn)?，2，22，…，2h-1。

17定理4.10

如果A[1..n]中數(shù)字都不同，那么任何情況下堆排序Heapsort(A[1..n])需要的比較次數(shù)是

(nlgn)。證明：假定n是偶教，n=2k，這不影響復(fù)雜度。在建好堆之后，前k個(gè)數(shù)，A[1..k]是內(nèi)結(jié)點(diǎn)，而后k個(gè)數(shù)A[k+1..n]是葉結(jié)點(diǎn)。

設(shè)中位數(shù)是x，則正好有k個(gè)數(shù)大於x?？勺C明：在排序開始前的堆中，至少有

k/3

個(gè)葉子(中數(shù)字)是小於等于x的。反證：如果不是，則最多有

k/3

-1個(gè)葉子是小於等于x的。那么，至少

2k/3

+1個(gè)葉子是大于x的。因?yàn)樗鼈冎辽儆?/p>

(2k/3+1)/2

≥

k/3

個(gè)父親，而父親們也是大于x的，那么，一共至少有

2k/3

+1+

k/3

>k

個(gè)結(jié)點(diǎn)中數(shù)大于x，矛盾。因?yàn)橛?/p>

k/3

葉子是小於等于x的，故至少有

k/3

個(gè)內(nèi)結(jié)點(diǎn)在開始時(shí)是大于x的。用S表示這些點(diǎn)的集合，|S|≥

k/3

=

n/6

。(接下頁(yè))18

193.不基於比較的線性時(shí)間排序算法

計(jì)數(shù)排序輸入要求:數(shù)字是整數(shù)，并且有范圍0≤a1,a2,…,an≤k，k=O(n)。如果不滿足，設(shè)法把問題變換為一個(gè)滿足該條件的問題。算法: 設(shè)輸入是A[1..n]第1步，統(tǒng)計(jì)有多少數(shù)等于0，有多少數(shù)等于1，…，有多少數(shù)等于k。for

i

0to

k

C[i]

0 //

C[i]

記錄整數(shù)i的個(gè)數(shù)，初始化為零。endfor for

i

0to

n

C[A[i]]

C[A[i]]+1 //如A[i]=j，整數(shù)j的個(gè)數(shù)加1。endfor第2步，

(見下頁(yè))。20計(jì)數(shù)排序(繼續(xù)1)第2步，對(duì)數(shù)組C做累計(jì)統(tǒng)計(jì)，有多少數(shù)是0，有多少數(shù)是小于等于1的，有多少數(shù)是小于等于2的，等等，直到有多少數(shù)是小于等于k的。結(jié)果仍放在C中，C[0]不變。fori

1to

k

C[i]

C[i]+C[i-1] endfor例4.2

假設(shè)數(shù)組A[1..8]有如下8個(gè)整數(shù)：4,5,3,0,2,3,4,2。 笫1步后數(shù)組C為：

笫2步后數(shù)組C為：C[0]C[1]C[2]C[3]C[4]C[5]102221C[0]C[1]C[2]C[3]C[4]C[5]11357821計(jì)數(shù)排序(繼續(xù)2)第3步，從A[n]到A[1]，逐個(gè)把A中數(shù)輸出到B[1..n]使B[1..n]是排好序的。做法： forj

n

downto1

u

A[j] //A[j]=整數(shù)u

d

C[u] //當(dāng)前數(shù)組B中還有d個(gè)小于等于u的數(shù)要安排

B[d]

A[j] //把A[j](=

u)放入B[d]中 C[u]

d-1 //修改C[u]為d-1endfor

理由：(a)

如果A[j]是從A[n]到A[1]中，第一個(gè)u。那么A[1..n]一共有d個(gè)小于等于u的數(shù)，而A[j]是最右邊的一個(gè)。所以，B[1..d]必定是排好序的這d個(gè)數(shù)。B[d+1]以及之后的數(shù)必大于u。因?yàn)锳[j]是最右邊的一個(gè)u，所以應(yīng)該把A[j]放入B[d]中，然后修改C[u]為d–1。22計(jì)數(shù)排序(繼續(xù)3)如果A[j]不是從A[n]到A[1]中，第一個(gè)u。那么C[u]=d表明，除去那些之前已經(jīng)安排好的等于u的數(shù)字外，包括A[j]在內(nèi)，A[1..n]有d個(gè)小于等于u的數(shù)。它們必須被安放在B[1]至B[d]中。因?yàn)锳[j]是這d個(gè)數(shù)中最右邊的一個(gè)，所以應(yīng)該把A[j]放入B[d]中。注意到，我們之前可能還看到過小于u的數(shù)，它們已被安排在B[1]至B[d-1]中某些地方，但它們不影響A[j]在序列中的位置是B[d]。同理，我們之前可能還看到過大于u的數(shù)，它們已被安排在B[d+1]之后的地方，也不影響A[j]在序列中的位置是B[d]。A[j]放入B[d]后，修改C[u]為d–1，指明下一個(gè)等于u的數(shù)在B中的位置。(如果還有等于u的數(shù)，否則不起作用。)下面看一個(gè)例子。23例將A[8]到A[1]中數(shù)字放入B[1..8]中，一共操作8次。第1步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[8]2C[0]C[1]C[2]C[3]C[4]C[5]113578C[0]C[1]C[2]C[3]C[4]C[5]更新后112578第2步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[7]24C[0]C[1]C[2]C[3]C[4]C[5]更新后112568A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]4530234224第3步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[6]234A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]453023C[0]C[1]C[2]C[3]C[4]C[5]更新后112468第4步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[5]2234C[0]C[1]C[2]C[3]C[4]C[5]更新后111468第5步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[4]02234C[0]C[1]C[2]C[3]C[4]C[5]更新后01146825A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]453第6步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[3]022334C[0]C[1]C[2]C[3]C[4]C[5]更新后011368第7步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[2]0223345C[0]C[1]C[2]C[3]C[4]C[5]更新后011367第8步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[1]02233445C[0]C[1]C[2]C[3]C[4]C[5]更新后01135726計(jì)數(shù)排序偽碼Counting-Sort(A[1..n],B[1..n],k)for

i

0to

k

C[i]

0 //初始化數(shù)組C為全零endforfor

i

0to

n

C[A[i]]

C[A[i]]+1 //C[j]記錄整數(shù)

j

的個(gè)數(shù)endforfori

1to

k

C[i]

C[i]+C[i-1] //C[i]記錄小于等于i的個(gè)數(shù)endforforj

n

downto1

u

A[j]，

d

C[u]

B[d]

A[j]，

C[u]

d-1endforEnd

顯然，計(jì)數(shù)排序復(fù)雜度是O(n)。27基數(shù)排序(Radixsort)要求：數(shù)字是由d位數(shù)組成的整數(shù)，每位取0，1，…,k中一個(gè)整數(shù)。k通常是一個(gè)常數(shù)，比如十進(jìn)制數(shù)中每位可以取0到9中任一數(shù)。做法：從右向左，即從最低位到最高位，逐位排序。這n個(gè)數(shù)字被排序d次，每次取一位作為關(guān)鍵字來對(duì)前一次排序的結(jié)果重做一次排序。因?yàn)槊恳晃坏娜≈捣秶荹0..k]，可以用計(jì)數(shù)排序來完成。偽碼見下頁(yè)28基數(shù)排序的偽碼Radix-Sort(A[1..n],d,k)for

i

1to

d

forj

1to

n

D[j]

ithdigitofA[j]//抽取A[j]中右起第i位數(shù) endfor

Counting-Sort(D[1..n],B[1..n],k)//以D[1..n]為關(guān)鍵字排序

A[1..n]

B[1..n]endforEnd基數(shù)排序復(fù)雜度是O(d(n+k))。通常d和k都是常數(shù)，其復(fù)雜度是O(n)。29例4.3

基數(shù)排序例子24963170424945867363139567370493745893739524963163193745867370445867370439524939593730基數(shù)排序正確性證明：設(shè)a

和b是序列中任意兩個(gè)數(shù)。假設(shè)a的d位數(shù)字，從高位到低位，是ad,ad-1,…,a2,a1，而b的d位數(shù)字是bd,bd-1,…,b2,b1。如果a

=b，因?yàn)橛?jì)數(shù)排序是穩(wěn)定排序，a和b的相對(duì)次序始終保持不變，所以基數(shù)排序是穩(wěn)定排序。如果a<b，那么，一定會(huì)在某h位上使ah<bh。假定h是從左到右，第一個(gè)出現(xiàn)個(gè)不等式的位，即ad

=bd,a