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

第3

章

基于比較的排序算法1什么是基于比較的排序

2插入排序 3合并排序

7堆排序

15快排序

282什么是基于比較的排序排序是把輸入的n個(gè)數(shù)，A[1],A[2],…,A[n]，重排為一個(gè)遞增序列或遞減序列。因?yàn)閷?duì)稱性，只考慮排序?yàn)檫f增序列，A[1]

A[2]

…

A[n]?；诒容^是指，用比較輸入數(shù)字之間大小的方法來(lái)決定它們的大小順序。不允許用數(shù)字的其它結(jié)構(gòu)性特征來(lái)幫助排序，例如數(shù)字A[i](1

i

n)有幾位，每一位的數(shù)值是多少，等等。32. 插入排序

這是一個(gè)簡(jiǎn)單的用貪心法的算法。思路是：初始： 把一個(gè)數(shù)，A[1]，排好序，(不需操作)第1步： 把兩個(gè)數(shù)，

A[1]，

A[2]，排好序，第2步： 把三個(gè)數(shù)，A[1]，A[2]，A[3]，排好序，……例如: (方框是下一步要插入的數(shù))初始： 5 3 4 2 1第1步后:

3 5 4 1 2第2步后:

3 4 5 1 2第3步后: 1 3 4 5 2第4步后:

1 2 3 4 54插入排序偽碼Insertion-sort(A[1..n])ifn=1 thenexitendiffor

k←2to

n

x←A[k] j←k–1 while

j>0and

A[j]>x A[j+1]←A[j] //A[j]比x

大，向后挪一位 j←j-1 endwhile //如果j=0，則有x<A[1] A[j+1]←x //把x插入到A[j+1]。如j=0，也正確

endfor End5

6插入排序的優(yōu)缺點(diǎn)缺點(diǎn)：復(fù)雜度較高，后面會(huì)介紹

(nlgn)的算法。優(yōu)點(diǎn)：算法簡(jiǎn)單，實(shí)現(xiàn)容易。是穩(wěn)定(stable)排序，即序列中任意兩個(gè)相等的數(shù)在排序后不改變它們的相對(duì)位置。是就地操作的算法，即只需要使用常數(shù)個(gè)除輸入數(shù)據(jù)所占空間以外的存儲(chǔ)單元。除數(shù)組A[1..n]以外，插入排序只需要指針k、指針j和臨時(shí)工作單元x。7用分治法把序列一分為二遞歸地將兩子序列排序用合并算法把排好序的兩個(gè)子序列合并為一個(gè)單一序列先討論合并算法，再討論排序算法。假設(shè)A[1..n1]和B[1..n2]分別為兩個(gè)遞增序列,即 A[1]

A[2]

A[3]

…

A[n1] B[1]

B[2]

B[3]

…

B[n2]合并算法把它們合并為一個(gè)排好序的單一序列。

合并后的序列存入數(shù)組C[1..n1+n2]，并有： C[1]

C[2]

C[3]

…

C[n1+n2](偽碼見下頁(yè))3. 合并排序8Merge(A[1..n1],B[1..n2],C[1..n1+n2])i

←

j

←k←1while

i

n1

and

j

n25

ifA[i]

B[j]6

then

C[k]←A[i]，i

←i+18 else

C[k]←B[j]，j

←j+110

endif11

k

←k+112 endwhileifi>n1 //說(shuō)明序列A里的數(shù)已全部放入序列C中

then

C[k..n1+n2]←B[j..n2] //B中剰余數(shù)放入C中15

elseC[k..n1+n2]←A[i..n1]

//否則，A中剰余數(shù)放入C中16 endifEnd合并算法復(fù)雜度(最壞情況)：

T(n)=n–1=n1+

n2

–1次比較。9合并排序：Mergesort(A[p..r]) //如果p=r，則是底的情況，不需任何操作1 if

p<r2

then

mid

←

(p+r)/2

3

Mergesort(A[p..mid])4

Mergesort(A[mid

+1..r])5

Merge(A[p..mid],A[mid+1..r],C[p..r])6

A[p..r]←C[p..r])7 endifEnd//調(diào)用

Mergesort(A[1..n])后可排序A[1..n]顯然，前面的合并算法Merge(A[1..n1],B[1..n2],C[1..n1+n2])需要稍加修改。主要是各數(shù)組兩端的序號(hào)必須是變量，不能總是從1開始。但這種修改極為容易，不在此贅述了。當(dāng)我們需要將數(shù)組A[1..n]排序時(shí)，只需調(diào)用Mergesort(A[1..n])即可。10二叉樹表示合并排序合并排序的遞歸過(guò)程可以用一棵二叉樹來(lái)表示。其劃分的順序是從根開始，自上而下，與樹的前向遍歷一致，而合并的順序是從葉子(底)開始，自下而上，與樹的后序遍歷順序一致。例子：A[1..8]A[1..4]A[5..8]A[1..2]A[3..4]A[5..6]A[7..8]9624153811合并排序復(fù)雜度最壞情況下，復(fù)雜度T(n)有遞推關(guān)系： T(1)=0 T(n)=T(

n/2

)+T(

n/2

)+(n-1)

（3.1）定理3.1設(shè)T(n)為，最壞情況下，合并排序數(shù)組A[1..n](n>0)需要的數(shù)字之間的比較次數(shù)，那么，T(n)滿足不等式

T(n)

n

lgn

–(n-1)。證明：我們用歸納法證明。歸納基礎(chǔ)：由(3.1)式，直接驗(yàn)證n=1,2,3,4。T(1)=0

1

lg1

–(1-1)，T(2)=T(1)+T(1)+(2-1)=1

2

lg2

–(2-1)，T(3)=T(2)+T(1)+(3-1)=3

3

lg3

–(3-1)，T(4)=T(2)+T(2)+(4-1)=5

4

lg4

–(4-1)。

定理正確。歸納步驟:(接下頁(yè))12定理3.1(證明繼續(xù)1)歸納步驟：假設(shè)當(dāng)

n

=1,2,3,…,k-1(k

5)時(shí)，有T(n)

n

lgn

–(n-1)。下面證明，當(dāng)n=k

時(shí)，仍然有T(n)

n

lgn

–(n-1)。我們注意到；

當(dāng)k是偶數(shù)時(shí)，

lg

k/2

=

lg(k/2)

=

lgk-1

=

lgk

-1。當(dāng)k是奇數(shù)時(shí)，

lg

k/2

=

lg((k+1)/2)

=

lg(k+1)-1

=

lg(k+1)

-1=

lgk

-1。 (因?yàn)閗是奇數(shù))所以，由歸納假設(shè)，我們有：T(

k/2

)

k/2

lg

k/2

–(

k/2

-1)

k/2

(

lgk

-1)–

k/2

+1 (3.2)T(

k/2

)

k/2

lg

k/2

–(

k/2

-1)

k/2

(

lgk

-1)–

k/2

+1 (3.3)(接下頁(yè))13定理3.1(證明繼續(xù)2)把(3.2)式和(3.3)式代入到(3.1)式，我們得到：T(n)=T(k)=T(

k/2

)+T(

k/2

)+(k-1)

(

k/2

(

lgk

-1)–

k/2

+1)+(

k/2

(

lgk

-1)–

k/2

+1)+(k-1)=k(

lgk

-1)–k+2+(k-1)=k

lgk

–k+1=k

lgk

–(k-1)。

歸納成功。

由定理3.1知，T(n)=O(nlgn)。因?yàn)楹喜⒉糠值淖詈们闆r需要至少min(n1,n2)=

n/2

次比較，所以有

T(n)

T(

n/2

)+T(

n/2

)+

n/2

。由主方法知，

T(n)

2T(

n/2

)+

n/2

=

(nlgn)。因此，合并排序的最好情況，最壞情況，以及平均情況的復(fù)雜度都是T(n)=

(nlgn)。14合并排序的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：復(fù)雜度是最好的。在第4章中，我們會(huì)證明這一點(diǎn)。合并排序是個(gè)穩(wěn)定排序。缺點(diǎn)：不是就地操作的算法，它需要使用

(n)個(gè)除數(shù)組A[1..n]外的存儲(chǔ)單元。當(dāng)n很大時(shí)，這是一個(gè)很大的開銷。把數(shù)組C中元素再?gòu)?fù)制回?cái)?shù)組A要消耗時(shí)間，相當(dāng)于把基本操作的次數(shù)加倍。當(dāng)n很大時(shí)，遞歸所需要用的堆棧也會(huì)增加開銷。15堆(heap)的數(shù)據(jù)結(jié)構(gòu)n個(gè)數(shù)字的最大堆是有n個(gè)結(jié)點(diǎn)(包括葉子)的二叉樹并滿足：每一個(gè)結(jié)點(diǎn)，包括葉結(jié)點(diǎn)，存有一個(gè)數(shù)。所有葉結(jié)點(diǎn)只出現(xiàn)在最底下二層，可證堆的高為h=lgn

。倒數(shù)第二層的所有內(nèi)結(jié)點(diǎn)出現(xiàn)在所有葉結(jié)奌的左邊。除最后一個(gè)內(nèi)結(jié)點(diǎn)可有一個(gè)左兒子外，每個(gè)內(nèi)結(jié)點(diǎn)必須有2個(gè)兒子。滿足最大堆順序：任一內(nèi)結(jié)點(diǎn)v中的數(shù)大于等于其兒子結(jié)點(diǎn)中的數(shù)，從而也大于等于v為根的子樹中所有結(jié)點(diǎn)的數(shù)。顯然，可以類似定義最小堆，因?qū)ΨQ性，我們只討論最大堆。在最大堆中，根結(jié)點(diǎn)中的數(shù)最大。4. 堆排序堆的例子16堆可以用一數(shù)組實(shí)現(xiàn)，例如上面的堆可存放如下：如何找出A[i]的兒子和父親？A[i]的左兒子

=

A[2i] (如果2i

>

n,

A[i]沒有左兒子。)A[i]的右兒子

=A[2i+1] (如果2i+1>n,A[i]沒有右兒子。)A[i]的父親 =

A[

i/2

] (i>1,否則A[i]=A[1]是根。)17堆排序簡(jiǎn)介設(shè)A[1..n]是一個(gè)堆，A[1]是最大數(shù)。把A[1]和A[n]中的數(shù)交換后，最大數(shù)就放在了A[n]，這正是排序后放最大數(shù)的地方。然后，我們把A[n]從堆中切除，即把n減1。這樣，剩下的n-1個(gè)數(shù)就在A[1..n-1]中了。A[1..n-1]不再是堆，但我們可以把它修復(fù)成一個(gè)堆。修復(fù)后，A[1]是下一個(gè)最大的數(shù)，把它與A[n-1]交換可把第二大數(shù)安排好。重復(fù)這樣的過(guò)程直至所有數(shù)都安排好。堆修復(fù)算法我們假設(shè)，在需要修復(fù)的堆中，有一處，也僅有一處違反了堆順序。也就是說(shuō)，在某一個(gè)內(nèi)結(jié)點(diǎn)A[i]中的數(shù)小于其某個(gè)兒子結(jié)點(diǎn)中的數(shù)值，而其余的所有內(nèi)結(jié)點(diǎn)A[j](j

i)都保持著最大堆順序，即A[j]中的數(shù)大于等于以A[j]為根的子樹中所有結(jié)點(diǎn)含有的數(shù)字。18堆修復(fù)算法偽碼：Max-Heapify(A[1..heap-size],i)l

←2i，r←2i+1

//左兒子的序號(hào)l，和右兒子的序號(hào)rif

l

heap-size

and

A[l]>A[i]

then

largest←l

elselargest←i //與左兒子比較誰(shuí)大endififr

heap-size

and

A[r]>A[largest]

thenlargest←r //與右兒子比較誰(shuí)大endififlargest

i

//如果A[i]比A[largest]小

thenA[i]

A[largest] //A[i]與該兒子交換

Max-Heapify([1..heap-size],largest) //遞歸修復(fù)該兒子這一點(diǎn)endifEnd堆修復(fù)算法例子19堆修復(fù)算法復(fù)雜度是2h=O(lgn)，因?yàn)樽疃噙f歸h

次，每次做2次比較。20為輸入數(shù)據(jù)建堆方法是先把數(shù)字任意放到數(shù)組

A[1..n]中，然后調(diào)整為一個(gè)堆。把A[i]為根的子樹調(diào)整為一個(gè)堆的遞歸算法如下。Build-Max-Heap(A[1..n],i)1 l

2i

//l是左兒子的序號(hào)2 r

2i+1

//r是右兒子的序號(hào)3 if

l≤n

4

thenBuild-Max-Heap(A[1..n],

l) //遞歸為左子樹建堆5 endif6 if

r≤n

7

then

Build-Max-Heap

(A[1..n],

r)

//遞歸為右子樹建堆8 endifMax-Heapify(A[1..n],i) End調(diào)用Build-Max-Heap(A[1..n],

1)后，即可將A[1..n]變?yōu)橐粋€(gè)堆。21輸入數(shù)據(jù)建堆的復(fù)雜度置n=2h+1-1。這樣A[1..n]所對(duì)應(yīng)的二叉樹是一棵高度為h的滿二叉樹(completebinarytree)，這里h=lg(n+1)–1。滿二叉樹的所有葉結(jié)點(diǎn)都在底層。例如：

22堆排序算法

將A[1..n]建堆后，堆排序算法如下：Heapsort(A[1..n])Build-Max-Heap(A[1..n],

1)2 Heap-size

n3 while

heap-size>14

A[1]

A[heap-size]5

heap-size

heap-size-16

Max-Heapify(A[1..heap-size]，1)7 endwhile8 End堆排序復(fù)雜度O(n)時(shí)間建堆。然后，循環(huán)(n-1)次，因?yàn)槎研迯?fù)的時(shí)間是O(lgn),所以最壞情況復(fù)雜度是

T(n)=O(n)+(n-1)O(lgn)=O(nlgn)堆排序舉例2324堆排序的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：堆排序是個(gè)就地操作的算法。它的復(fù)雜度T(n)=

(nlgn)是漸近最優(yōu)。缺點(diǎn)：堆排序的最大缺點(diǎn)是不穩(wěn)定。讀者可以很容易地找到不穩(wěn)定的例子。最壞情況下，可證明，它需要至少2n-lg(n+1)次比較先構(gòu)建一個(gè)堆。而且，它的排序部分還需要約2nlgn次比較。所以，最壞情況時(shí)，比合并排序的

n

lgn

-(n-1)比較次數(shù)(定理3.1)要多將近一倍以上。25堆用作優(yōu)先隊(duì)列堆還可用來(lái)動(dòng)態(tài)地管理和修改數(shù)據(jù)，比如插入一個(gè)數(shù)，刪除一個(gè)數(shù)，減少(或增加)一個(gè)數(shù)，找到最大(或最小)的數(shù)等。提供這些操作的數(shù)據(jù)結(jié)構(gòu)都稱為優(yōu)先隊(duì)列(Priorityqueue)。1. 增加堆中A[i]的值為新值keyHeap-Increase-Key(A[1..n]，i，key)1 ifkey<A[i]2

thenerror //要增加的值比原來(lái)值還小，不合理3 endif4 A[i]

key，father(i)

i/2

while

i>1and

A[father(i)]<A[i]

A[i]

A[father(i)]，i

father(i) father(i)

i/2

8 endwhile9 End

這個(gè)算法復(fù)雜度為O(lgn)。262. 插入一個(gè)數(shù)keyMax-Heap-Insert(A[1..heap-size],key)1 heap-size

heap-size

+12 n

heap-size3 A[n]

-

4 Heap-Increase-Key(A[1..n],n,key)End

//這個(gè)算法復(fù)雜度為O(lgn)。3. 取走最大數(shù)并放入變量max當(dāng)中

Heap-Extract-Max(A[1..heap-size]，max)1 n

heap-size2 if

n<13

thenreturn“error,heapunderflow”4 endif(接下頁(yè))273. 最大數(shù)放入變量max當(dāng)中

(繼續(xù))max

A[1]A[1]

A[n]heap-size[A]

n–18 Max-Heapify(A[1..heap-size]，1)9 return

max10 End //這個(gè)算法復(fù)雜度為O(lgn)將最大數(shù)復(fù)制到變量max當(dāng)中(不刪除最大數(shù))Heap-Maximum(A[1..heap-size],max)1 if

heap-size<12 thenreturnerror“heapunderflow” //堆是個(gè)空集3 endif4 max

A[1]5 returnmax6 End //這個(gè)算法復(fù)雜度為O(1)5.

快排序28快排序用分治法序列含1個(gè)數(shù)或沒有數(shù)時(shí)是底，此時(shí)不需任何操作。取序列A[p..r]中一個(gè)數(shù)，例如A[r]，作為中心點(diǎn)。文獻(xiàn)中有各種取法，都差不多，本書取A[r]作為中心點(diǎn)。

把序列中數(shù)，從A[p]到A[r-1]，逐個(gè)與中心點(diǎn)比較，小于等于A[r]的數(shù)放左邊，大于A[r]的數(shù)放右邊。最后，A[r]放中間。 左邊任何數(shù)≤A[r]<右邊任何數(shù)。遞歸地快排序左、右兩部分。劃分A[p..r]為二的算法指針j指向下一個(gè)要檢查的數(shù)，初始值為p，即指向A[p]。指針i指向當(dāng)前左邊部分中最后一個(gè)數(shù)，初始值為p-1。29劃分算法每步的具體操作：每次我們比較A[j]和A[r]時(shí)，有兩種結(jié)果，分述如下：

如果A[j]>A[r]，A[j]中數(shù)字屬于第二部分，只需指針j加1。如果

A[j]≤A[r]，A[j]中數(shù)字屬于第一部分。把A[j]和A[i+1]中數(shù)字交換后可把A[j]中的數(shù)字并入第一部分。這時(shí)需把指針i和j分別加1。當(dāng)A[1..r-1]中每個(gè)數(shù)都和A[r]比較后，交換A[i+1]和A[r]中數(shù)字。這樣就把A[r]中數(shù)放在了中心點(diǎn)位置上。顯然，中心點(diǎn)位置是q

=i+1。30劃分算法偽碼：Partition(A[p..r],q)1 x

A[r]2 i

p-13 for

j

ptor-1 //每次操作后，for循環(huán)會(huì)把j加14 ifA[j]

x//如A[j]>x，不需任何操作，i不變5 then

i

i+16

A[i]

A[j]7

endif

8 endfor9 A[i

+1]

A[r] 10 q

i+1 //中心點(diǎn)在A[i+1]11 returnq12 End

劃分算法需要n-1次比較，是就地操作。這里，n=r-p+1。31I=p-1J=pr初始狀態(tài)28713564ij一次比較后28713564ij2次比較后28713564ij3次比較后28713564ij4次比較后21783564ij5次比較后21387564ij6次比較后21387564ij7次比較后21387564把A[r]放到中21347568心點(diǎn)后q劃分算法舉例32快排序算法偽碼Quicksort(A[p..r]) 1 ifp<r //如果p

r，則見底2

then Partition(A[p..r],q)3

Quicksort(A[p..q-1])4

Quicksort(A[q+1..r])5 endif6 End

如果要把A[1..n]排序的話，只需調(diào)用Quicksort(A[1..n])。快排序最壞情況復(fù)雜度定理3.2

給定序列A[p..r]，快排序Quicksort(A[p..r])需要最多n(n-1)/2次比較，這里n為數(shù)組中元素的個(gè)數(shù)，即n=p-r+1。(證明見下頁(yè))33

34

35

36*快排序算法最好情況復(fù)雜度定理3.4

給定序列A[p..r]，快排序Quicksort(A[p..r])需要最少

(n+1)lg(n+1)

–2n次比較，這里n=p-r+1

為數(shù)組中元素的個(gè)數(shù)。證明：

對(duì)n進(jìn)行歸納證明。歸納基礎(chǔ)：n

=0時(shí)，T(0)=0,

(0+1)lg(0+1)

–2

0=0，定理正確。n

=1時(shí)，T(1)=0,

(1+1)lg(1+1)

–2

1=