算法：求解問題的一組規(guī)則

檢索問題\/分治策略

排序問題發(fā)現(xiàn)?貪心策略

路徑問題規(guī)則的設計＜一設也略動態(tài)規(guī)劃

最優(yōu)化問題〃指導

n1|檢索與周游

遍歷問題,、回溯與分支限界

形成算法產(chǎn)生算法設計的指

導思想和基本規(guī)律

第二章分治法(DivideandConquer)

——“分”而治之

2.1一般方法

■如何求解規(guī)模較大問題？

分析問題的特征，尋找合適的解決問題的方法

何謂規(guī)模較大？相對而言

■利用分治法求解大規(guī)模問題

一種“大事化小”，“從小事做起”的解決問題的策略

最常用的算法設計策略之一

.分治策略基本思想逐步細化的過程

1，子問題二廠子問題求幀、

當問題的規(guī)模較大而無aqlal

法直接求解時，將整個問題

分成若干個小問題，然后分問題子結果

Qaq2?a2?A

而治之。分解合并

并在獲得較小子問題的

解之后，再將子問題的解合

?qk?ak

并成原始問題的解。

yy

__J

?子問題的劃分是一個遞歸過程。

?通常情況下，要求劃分出的子問題與原始問題具有相

同的“類型，，，“同質”

2.分治策略的抽象化控制過程——二分策略

算法2.1分治策略的抽象化控制注：

procedureDANDC(p,q)ak=2:二分是最常用的分解策略；

globaln.A(1:n);aSMALL(p.q)：布爾函數(shù)，判斷輸

入規(guī)模q-p+1是否足夠小而無需再

integerm,p,q;//1WpWqWn〃進一步分就可求解；

ifSMALL(p,q)

>G(p,q)：當SMALL(p,q)為真時，

thenreturn(G(p,q))對輸入規(guī)模為q-p+1的子問題求解;

else>DIVIDE(p.q)：當規(guī)模q-p+1還較

m—DIVIDER,q)//p<m<q//大時，對規(guī)模為q-p+1的子問題進

retum(COMBINE(DANDC(p,m),一步分解，返回值為［p,q］區(qū)間進

一步的分割點；

DANDC(m+1,q)))

：子結果的合并函

endif>COMBINE(x,y)

數(shù),將區(qū)間［p,m］和［m+1,q］上的子

endDANDC問題的解合并成區(qū)間［p,q］上的

“較完整”的解。當p=1,q=n時,

最初的調用：DANDC(1,n)就得到整個問題的解。

■DANDC的計算時間

若所分成的兩個子問題的規(guī)模大致相等，則DANDC總的

計算時間可用遞歸關系式表示如下：

rg(n)n足夠小

T(n)=<

I2T(n/2)+f(n)否則

>T(n)：表示輸入規(guī)模為n時的DANDC計算時間

>g(n)：表示對足夠小的輸入規(guī)模直接求解的計算時間

>f(n)：表示COMBINE對兩個子區(qū)間的子結果進行合并

的時間

(該公式針對具體問題有各種不同的變形)

2.2二分檢索——折半查找

1.問題的描述

有序表上的檢索問題：已知一個按非降次序排列的元素

表a］，a2,…,小，判定某給定的元素x是否在該表中出現(xiàn)。

>若是，則找出x在表中的位置并返回其所在位置的下標

>若非，貝1J返回。值。

問題的形式描述:

l=(n,a1,a2,...,an,x)

■問題分解：選取下標k,由此將I分解為3個子問題：

11一a2，.…,,x)?——規(guī)模較大

12=(1,ak,x)-------規(guī)模足夠小

b—(n-k,8+1，E，…,a^x)<規(guī)模較大

>對于叨若a1x,則有解k,對「不用再求解;否則，

>若xv%,則只在中求解，對卜不用求解；

>若X〉為,則只在I3中求解，對「不用求解；

>對l1、I3的求解可再次采用分治方法求解-----遞歸過程

2.二分檢索

二分檢索：每次選取中間元素的下標

算法2.3二分檢索

procedureBINSRCH(A,n,x,j)

integerlow,high,mid,j,n;注：

low—1;high—n;給定一個按非降次序排列

whilelow<highdo的元素數(shù)組A(1:n),n》l,

mid<—|_(low+high)/2J判斷x是否出現(xiàn)。

case

:x〈A(mid):high—mid-1?若是,置j,使得x=A(j)

:x>A(mid):low<—mid+1?若非，j=0

:else:j<—mid;return

endcase

repeat

jJ。

endBINSRCH

789

例2.1：設A(1:9)=(-15,-6,0,7,9,23,54,82,101)

在A中檢索x=101,-14，82o執(zhí)行軌跡見下表1

表i運行軌跡示例

x=101x=-14x=82

lowhighmidlowhighmidlowhighmid

195195195

697142697

898111898

99921找不到找至IJ

找至U

成功的檢索不成功的檢索成功的檢索

定理2.1過程BINSRCH(A,n,xJ)能正確運行

證明：

1)在具體指定A中的數(shù)據(jù)元素及x的數(shù)據(jù)類型后，算法中的所有運算都

能按要求正確運行——即首先滿足確定性和能行性

2)終止性

算法初始部分置low-1,high—n

①若n=0,不進入循環(huán)，j置0,算法終止

②否則，進入循環(huán)，計算mid,

>或x=A(mid),j置為mid,算法終止；

>或xvA(mid),置high—mid",搜索范圍實際縮小為［low,mid-1］,

進入下次循環(huán)，對［mid+1,high］區(qū)間不做進一步搜索；

>或x>A(mid),置low—mid+1,進入下次循環(huán)；搜索范圍實際縮小

為［mid+1,high］,對［low,mid-1］區(qū)間不做進一步搜索;

因low,high,mid都是整型變量，故按照上述規(guī)則，在有限步內，或

找到某個mid,有A(mid)=x；或變得low>high,在A市沒有找到任何兀

素等于x,算法終止。

3.性能分析

1)空間特性

n+5個空間位置(A,x,j,mid,low,high)-----O(n)

2)時間特性

區(qū)分以下情況進行分析

?成功和不成功檢索情況：

>成功檢索：指所檢索的X恰好在A中出現(xiàn)。

由于A中共有n個元素，故成功檢索恰好有n種可能的情況

>不成功檢索：指x不出現(xiàn)在A中。

根據(jù)取值，不成功檢索共有n+1種可能的情況(取值區(qū)間)：

x<A(1)或A(i)<x<A(i+1),l^i<n-l或x>A(n)

?最好、最壞、平均檢索情況——與數(shù)據(jù)配置有關

A成功/不成功檢索的最好情況：最少幾次能達到目的

執(zhí)行步數(shù)最少，計算時間最短

▲成功檢索的最好情況：若x恰好是A中的某個元素，最少

幾次確定x在A中的出現(xiàn)位置：1次

▲不成功檢索的最好情況：若x不是A中的任何元素，最少

幾次能判斷出這一結論

A成功/不成功檢索的最壞情況：最多幾次能達到目的

執(zhí)行步數(shù)最多，計算時間最長

＞成功/不成功檢索的平均情況：典型數(shù)據(jù)配置下的執(zhí)行

情況，為一般情況下計算時間的平均值

實例分析（例2.1）

運算的頻率計數(shù)procedureBINSRCH(A,n,x,j)

1.while循環(huán)體外語句的頻integerlow,high,mid,j,n;

率計數(shù)為1匚>low<—1;high<—n;

whilelow<highdo

2.集中考慮while循環(huán)中x與Amid<—(low+high)/2j

中元素的比較運算"\case

——其它運算的頻率計數(shù):x<A(mid):high<—mid-1

與比較運算有相同的數(shù)量7:x>A(mid):low-mid+1

:else:j<-mid;return

級。4endcase

3.case語句的分析：假定只repeat

需一次比較就可確定casej-。

語句控制是三種情況的哪endBINSRCH

一種。

實例分析(例2.1)

每種查找情況所需的元素比較次數(shù)統(tǒng)計如下:

A(1)(2)(3)(4)(5)(6)(7)(8)(9)

元素-15-6079235482101

成功檢索比較次數(shù)323@0323?

不成功檢索比較次數(shù)3334433344

成功檢索

最好：1次

最壞：4次

平均：(3+2+3+4+1+3+2+3+4)/9"2.77次

■不成功檢索

最好：3次

最壞：4次

平均：(3+3+3+4+4+3+3+3+4+4)/10=3.4次

二元比較樹

算法執(zhí)行過程的主體是X與一系列

中間元素A(mid)比較。可用一棵二元樹

描述這一過程，稱為二元比較樹

■結點：分為內結點和外結點兩種

?內結點：?代表一次元素比較

?用圓形結點表示

?存放一個mid值(下標)

?代表成功檢索情況

?外結點：?用方形結點表示，

,表示不成功檢索情況

■路徑：代表檢索中元素的比較序列

■分支：“小于”進入左分支，“大于”

例2.1的二元比較樹

進

入右分支。

二元比較樹的查找過程

□若x在A中出現(xiàn)，則算法的執(zhí)行過

程在一個圓形的內結點處結束

□若x不在A中出現(xiàn)，則算法的執(zhí)行

過程在一個方形的外結點處結束

注：外結點不代表元素的比較，因

為比較過程在該外結點的上一

級的內結點處結束。

例2.1的二元比較樹

定理2.2若n在區(qū)域［2-2）中，則對于一次成功的檢索，

BINSRCH至多做k次比較；對于一次不成功的檢索，

或者做k-1次比較，或者做k次比較。

證明要點：

>二分檢索中，每次mid取中值，故其二元比較樹是一種“結點平衡”的樹

★當2k-〔Wn<2k時，結點分布情況為：

內結點：1至k級

外結點：k級或k+1級，

★外部結點在相鄰的兩級上——最深一層或倒數(shù)第2層

?比較過程：

院成功檢索在內結點處結束，不成功檢索在外結點處結束

a成功檢索在i級的某個內結點終止時，所需要的元素比較次數(shù)是i,

等于根到該內結點的路徑長度+1。

a不成功檢索在i級的外部結點終止所需的元素比較次數(shù)是i-1,

等于根到該外結點的路徑長度。

BINSRCH的計算復雜度

n引2R2k)

k-logn

1)外結點在最末的兩級上，故不成功檢索的最好、

最壞和平均情況的計算時間均為0(logn)

2)成功檢索的最好情況下計算時間為0(1)

成功檢索的最壞情況下計算時間為?(logn)

3)平均情況下的成功檢索的計算時間

利用外部結點和內部結點到根距離和之間的關系進行推導。

記，

>由根到所有內結點的距離之和稱為內部路徑長度，記為I；

>由根到所有外部結點的距離之和稱為外部路徑長度，記為E。

則有，E=l+2n....................................................................①

記，

>U(n)是平均情況下不成功檢索的計算時間，則

U(n)=日(n+1)...............................................②

>S(n)是平均情況下成功檢索的計算時間，則

S(n)=l/n+1.................................................③

n個內部結點在成功檢索時所需的比較次

數(shù)均為根到該結點的路徑長度+1

y

由①②③得：

S(n)=(1+1/n)U(n)-1

當rif8,s(n)8u(n),而U(n)=0(logn)

所以S(n)二0(logn)

成功檢索不成功檢索

最好平均最壞最好平均最壞

0(1)0(logn)0(logn)0(logn)0(logn)0(logn)

4.以比較為基礎檢索的時間下界

問題：設n個元素的有序表A(1:n),A(1)<A(2)<..<A(n)o檢索一

給定元素x是否在A中出現(xiàn)。

問：是否預計還存在有以元素比較為基礎的另外的檢索算法，它

在最壞情況下比二分檢索算法在計算時間上有更低的數(shù)量級?

以比較為基礎的算法：假定算法中只允許進行元素間的比較，而不

允許對它們實施其它運算。

分析：任何以比較為基礎的檢索算法，其執(zhí)行過程都可以用

二元比較樹來描述。

圖2.2兩個檢索算法的比較樹

(a)模擬線性檢索(b)模擬二分檢索

內結點：表示一次元素的比較，并代表成功檢索情況。每棵比較樹中恰

好含有n個內結點，分別與n個不同i值相對應；

外結點：代表不成功檢索情況。每棵比較樹中恰好有n+1個外結點分別

與n+1中不成功檢索情況相對應。

以比較為基礎的有序檢索問題最壞情況的時間下界有以下結論：

定理2.3設A(1:n)含有n(n>l)個不同的元素，且有

A(1)<A(2)<..<A(n)

又設，用以比較為基礎的算法去判斷給定的x是否有xeA(l:n)

貝最壞情況下，任何這樣的算法所需的最小比較次數(shù)FIND(n)

有：FIND(n)2「log(n+l)]

證明：

①從模擬求解檢索問題算法的比較樹可知，F(xiàn)IND(n)不大于樹中由根到

一個葉子(外部結點)的最長路經(jīng)的距離。

②在所有的二元比較樹中必定有n個內結點分別與x在A中的n中可能的

出現(xiàn)相對應。

③如果一棵二元樹的所有內結點所在的級數(shù)小于或等于k,則該樹中最

多有2匕1個內結點。

故，nW2T即

FIND(n)=k>log(n+1)~|

■結論

1)任何一種以比較為基礎的有序檢索算法，在最壞情況下

的計算時間都不低于O(logn)。因此，不可能存在最壞

情況比二分檢索數(shù)量級還低的算法。

2)二分檢索是解決檢索問題的最優(yōu)的最壞情況算法

2.3找最大和最小元素

查找問題：

1）在元素表中確定某給定的元素的位置或判定

其不出現(xiàn)：二分檢索，順序查找

2）在元素表單獨或同時找出其中的最大和

（或）最小

3）在元素表找出其中第一?。ù螅┖偷诙?/p>

（大）元素

4）找元素表中的第k小元素：排序或選擇

等等

本節(jié)問題：在元素表同時找出最大元素和最小元素

問題描述：給定含有n個元素的集合（以數(shù)組A表

示），找出其中的最大和最小元素。

二種算法的比較:

迭代算法

遞歸算法

1.直接找最大和最小元素

算法2.5直接找最大和最小元素

procedureSTRAITMAXMIN(A,n,max,min)

〃將A中的最大值置于max,最小值置于min//

Integeri,n

max—min-A⑴

fori<—2tondo算法的性能：

ifA(i)>maxthen

max—A(i)?只考慮算法中的比較

endif運算，以此代表算法

ifA(i)<minthen的執(zhí)行特征；

min—A(i)

endif?該算法最好、最壞、

repeat平均情況下均需要做

endSTRAITMAXMIN2(n-1)次元素比較

STRAITMAXMIN算法的一種簡單改進形式：

procedureSTRAITMAXMIN1(A,n,max,min)

integeri,n

max—min—A⑴

fcri—2tondo

ifA(i)>maxthenmax<—A(i)endif

elseifA(i)<minthenmin—A(i)endif

repeat

endSTRAITMAXMIN1

這使得，

>最好情況：按遞增次序排列，元素比較次數(shù)為n-1次

>最壞情況：按遞減次序排列，元素比較次數(shù)為2(n")次

>平均情況：元素比較次數(shù)為3(n")/2次

2.分治求解策略

記問題的一個實例為：

l=(n,A(1),...,A(n))

采用二(等)分法將I分成兩個子集合處理

b=(|_n/2_,A(1),…，A([n/2_|))，和

l2=(n-[n/2」,A([n/2」+1),…，A(n))

則有,

MAX(I)=max(MAX(l1),MAX(l2))

MIN(I)=min(MIN(l1),MIN(l2))

MAX(I)和MIN(I)分別代表I中元素的最大者和最小者

采用遞歸的設計策略，得到以下算法：

3.找最大最小元素的遞歸求解算法

算法2.6遞歸求取最大和最小元素

procedureMAXMIN(i,j,fmax,fmin)

〃A(1:n)是含有n個元素的全局數(shù)組，參數(shù)i,j是整數(shù)，1Wi,jWn,代表當前的查找區(qū)間//

〃該過程把A(i:j)中的最大和最小元素分別賦給fmax和fmin//

integeri,j;globaln,A(l:n)

case

:i=j:fmax-fmin-A(i)〃只有一個元素

:i=j-l:ifA(i)<A(j)thenfmax-A(j);fmin-A(i)

elsefmax-A(i);fmin-A(j)〃兩個元素的情況

endif

:else:mid-1(i+j)/2」〃取中，并在兩個子區(qū)間上作遞歸調用

callMAXMIN(i,mid,gmax,gmin)

callMAXMIN(mid+1,j,hmax,hmin)

fmax-max(gmax,hmax);fmin-min(gmin,hmin)

endcase

endMAXMIN

MAXMIN過程的初始調用:

MAXMIN(1,n,fmax,fmin)

數(shù)組A是全局數(shù)組

fmax,fmin帶出A(1:n)中的最大和最小元素

例：在A(1:9)=(22,13,-5,-8,15,60,17,31,47)上執(zhí)行算法2.6

遞

歸

調

遞

用

歸

的

調

返

用

回

分

解

過

程

圖2.3表示MAXMIN遞歸調用的樹

區(qū)間劃分將一直進行到只含有1個或2個元素時為止，然后求子解，并返回

MAXMIN過程的性能分析一僅考慮算法中的比較運算

r0n=1

T(n)=<1n=2

、T([n/2j+T(「n/2])+2n>2

當n是2的哥時(n=2k),化簡上式有，

T(n)=2T(n/2)+2

=2(2T(n/4)+2)+2

二25(2)+匯21

l<i<k-l

=2k-1+2k-2

=3n/2-2

性能比較

1)與STRAITMAXMIN算法相比，比較次數(shù)減少了25%

(3n/2-2:2n-2)o

已經(jīng)達到了以元素比較為基礎的找最大最小元素的算法

計算時間的下界：「3〃/2]-2

2)存在的問題——遞歸調用造成：

>空間占用量大

有[log〃」+l級的遞歸，入棧參數(shù)：

i,j,fmax,fmin和返回地址五個值。

>時間可能不比預計的理想

如果元素A⑴和A(j)的比較與和j的比較在時間上相差不

大時，算法MAXMIN不可取。

假設元素的比較與i利的比較時間相同(整型數(shù))。又設對case語句調

整，使得僅需一次i和j的比較就能夠確定是哪種情況。

case

:i>=j-l:ifA(i)<A(j)thenfmax-A(j);fniin-A(i)

elsefmax-A(i)A(j)〃兩個元素的情況

endif

:else:,

記此時MAXMIN的頻率計數(shù)為C(n),n=2k(k為正整數(shù))。則有，

r2nv=2(一次是i和卜1的比較，一次是A(i)和A(j)的比較)

C(n)=.

2C(n/2)+3n>2

化簡得，

C(n)=2C(n/2)+3

=5n/2-3

按照同樣的假設，重新估算STRAITMAXMIN算法的比較次數(shù)

為：3(n-1)o

>STRAITMAXMIN與MAXMIN在計算時間上的差異越來越小

1/4(25%)=>1/6(16.7%)

?考慮MAXMIN算法遞歸調用的開銷，此時MAXMIN算法

的效率可能還不如STRAITMAXMIN算法。

結論：如果A中的元素間的比較代價遠比整型數(shù)

（下標）的比較昂貴，則分治方法將產(chǎn)生

一個效率較高的算法；

反之，可能僅得到一個低效的算法。

故，分治策略只能看成一個較好的但并不總是成功

的算法設計指導。

2.4歸并分類

1.分類問題——排序

給定一n個元素的集合A,按照某種方法將A中的元素按非

降或非增次序排列。

分類：內排序，外排序

常見內排序方法：冒泡排序

插入排序

歸并排序

快速排序

堆排序

冒泡排序

■voidBubbleSort(inta[],intn)

{〃對表a做冒泡排序。

intij,t;

for(i=0；i<n；i++){

for(j=0;j++){

if(a[j]>a0+1]){

temp=a[j];

a[j]=aO+1]；

a[j+1]=temp;

}

}

}

}

2.插入分類

算法2.7插入分類

procedureINSERTIONSORT(A,n)

〃將A(1：n)中的元素按非降次序分類，n>1//

A(0)--8〃設置初始邊界值

forj—2tondo〃A(1:j-1)已分類//i指示的是j之前的

item—A(j);i—j-1-------一位，即當前已

排序子表的最末

whileitem<A(i)do//0<i<j//一個元素的下標

A(i+1)—A(i);i-i-1

repeat

A(i+1)<—item;

repeat

endINSERTIONSORT

性能分析：

最壞情況：輸入數(shù)據(jù)按非增次序排列，每次內層

while循環(huán)執(zhí)行j次n)o則有，

Zj=(n(n+1))/2-1

2<j<n

=0(n2)

最好情況：輸入數(shù)據(jù)已按非降序排列，不進入

while循環(huán)，則最好情況下計算時間為Q(n)

3.分治策略求解

基本設計思想：將原始數(shù)組A中的元素分成兩個

子集合：&（1:]n/2」）和A41n/2」+1:n）。分別對這

兩個子集合單獨分類，然后將已分類的兩個子序列

歸并成一個含有n個元素的分類好的序列。

這樣的一個分類過程稱為歸并分類。

算法2.8歸并分類

procedureMERGESORT(low,high)

〃A(low:high)是一個全程數(shù)組，low和high分別指示當前待分類區(qū)間的最

小下標和最大下標，含有high?low+120個待分類的元素〃

integerlow,high

iflow<highthen〃當含有2個及2個以上的元素時，作劃分與遞歸處理〃

mid—1(low+high)/2j〃計算中分點〃

callMERGESORT(low,mid)〃在第一個子集合上分類(遞歸)〃

callMERGESORT(mid+1,high)〃在第二個子集合上分類(遞歸)〃

callMERGE(low,mid,high)〃歸并已分類的兩子集合〃

endif

endMERGESORT

算法2.8歸并分類(C語言版本)

voidMERGESORT(intlowjnthigh)

〃A(low:high)是一個全程數(shù)組，low和high分別指示當前待分類區(qū)間的最

小下標和最大下標，含有high?low+120個待分類的元素〃

(

intmid;

if(low<high){〃當含有2個及2個以上的元素時，

作劃分與遞歸處理〃

mid=(low+high)/2;〃計算中分點，利用c語言的整數(shù)除法〃

MERGESORT(low,mid)〃在第一個子集合上分類(遞歸)〃

MERGESORT(mid+1,high)〃在第二個子集合上分類(遞歸)〃

MERGE(low,mid,high)〃歸并已分類的兩子集合〃

}

}//endMERGESORT

算法2.9使用輔助數(shù)組歸并兩個已分類的集合

procedureMERGE(low,mid,high)

//A(low,high)是一個全程數(shù)組，它含有兩個放在A(low,mid)和A(mid+1,high)中的已分

類的子集合.目標是將這兩個已分類的集合歸并成一個集合，并存放到A(low,high)中〃

integerh,IJ,k,low,mid.highy/low^micKhigh//

globalA(low,high);localB(low,high)

h—low;i—low;j—mid+1;

whileh<midandj<highdo〃當兩個集合都沒有取盡時，將較小的元素先存放到B中〃

ifA(h)<AQ)thenB(i)<-A(h);h<-h+1〃如果前一個數(shù)組中的元素較小〃

elseB(i)—A(j);j-j+1//如果后一個數(shù)組中的元素較小//

endif

i-i+1

repeat

〃處理尚有剩余元素的集合〃

ifh>midthenfork—jtohighdoB(i)—A(k);i—i+1;repeat

elsefork<—htomiddoB(i)-A(k);i-i+1;repeat

endif

fork—lowtohighdoA(k)<—B(k)repeat〃將已歸并的集合復制到A中〃

endMERGE

算法2.9使用輔助數(shù)組歸并兩個已分類的集合

(C語言)

voidMERGE(intlow,intmidjnthigh)

〃A(low,high)是一個全程數(shù)組，它含有兩個放在A(low,mid)和A(mid+1,high)中的已分

類的子集合.目標是將這兩個已分類的集合歸并成一個集合，并存放到A(low,high)中〃

{integerhjj.k;

intB[N]；//設A數(shù)組的大小為N

h=low;i=low;j=mid+1;

while(h<=mid&&j<=high){〃當兩個集合都沒有取盡時，將較小的元素先存放到B中〃

if(A[h]<=A0]){B[i]=A[h];h=h+1;}〃如果前一個數(shù)組中的元素較小〃

else{B[i]=A[j];j=j+1;}〃如果后一個數(shù)組中的元素較小〃

i-i+1

}

〃處理尚有剩余元素的集合〃

if(h>mid)for(k=j;k<=high;k++){B[i]=A[k];i=i+1;}

elsefor(k=h;k<=mid;k++){B[i]=A[k];i=i+1;}

endif

for(k=low;k<=high;k++)A[k]=B[k]〃將已歸并的集合復制到A中〃

}//endMERGE

性能分析

1)過程MERGE的歸并時間與兩數(shù)組元素的總數(shù)成正比

故可表示為：cn,n為元素數(shù),c為某正常數(shù)

2)過程MERGESORT的分類時間用遞推關系式表示如下：

1an=1,a是常數(shù)

遞歸調用一直進行

T(n)=到子區(qū)間僅含一個

2T(n/2)+cnn>1,c是常數(shù)元素時為止

化簡：若廿2匕則有，工-----------------------)

T(n)=2(2T(n/4)+cn/2)+cn

=4T(n/4)+2cn=4T(2T(n/8)+cn/4)+2cn

=2kT(1)+kcn

=an+cnlogn//k=logn//

若2k〈nv2k+i,則有T(n)<T(2k+i)。

所以得：T(n)=O(nlogn)

歸并分類示例

■設A二(310,285,179,652,351,423,861,254,450,520)

-1)劃分過程

2）歸并過程

首先進入左分枝的劃分與歸并。

第一次歸并前的劃分狀態(tài)是:

(310|285|179|652,351|423,861,254,450,520)

第一次歸并(285,310|179|652,351|423,861,254,450,520)

第二次歸并(179,285,310|652,351|423,861,254,450,520)

第三次歸并(179,285,310|351,6521423,861,254,450,520)

第四次歸并(179,285,310,351,6521423,861,254,450,520)

進入右分枝的劃分與歸并過程

（略）

3）用樹結構描述歸并分類過程

圖2.4用樹表示MERGESORT。,10）的調用圖2.5用樹表示對MERGE的調用

4.歸并分類算法的改進

1）算法2.8存在的問題

?遞歸層次太深

在MERGESORT的執(zhí)行過程中，當集合僅含有兩個元素

時，仍要進一步做遞歸調用，直至每個集合僅含有一個元素

時才退出遞歸調用。

在集合僅含有相當少的元素時，較深層次的遞歸調用使

得時間過多地消耗在處理遞歸上。

?元素在數(shù)組A和輔助數(shù)組B之間的頻繁移動

每次歸并，都要首先將A中的元素移到B中，再由B復制

到A的對應位置上。

■2）改進措施

?針對遞歸層次問題

采用能在小規(guī)模集合上有效工作的其它算法，直接對小

規(guī)模集合處理。

如INSERTIONSORT算法

?針對元素頻繁移動問題

采用一個稱為鏈接信息數(shù)組LINK（1：n）的數(shù)據(jù)結構，

記錄歸并過程中A中的元素相對于其排序后在分類表中位置

坐標的鏈接關系。

LINK（i）取值于[1,n],是指向A的元素的指針：在分類

表中它指向下一個元素在A中的位置坐標。

例：

LINK(1)(2)(3)(4)(5)(6)(7)(8)

64713080

?該表中含有兩個子表，0表示表的結束。

A設置表頭指針Q和R分別指向兩個子表的起始處：

Q=2,R=5；

則有，

表1：Q(2,4,1,6),經(jīng)過分類后有：A(2)<A(4)<A(1)<A(6)

表2：R(5,3,7,8),同樣有：A(5)<A(3)<A(7)<A(8)

■鏈接信息表在歸并過程中的應用：

將歸并過程中元素在A和B之間移動的過程變成更改LINK

所指示的鏈接關系，從而避免移動元素的本身。

分類表可以通過LINK的表頭指針和讀取LINK中的鏈接關

系取得。

改進后的歸并分類模型

算法2.10使用鏈接信息數(shù)組的歸并分類模型

procedureMERGESORT1(low,high,p)

//利用鏈接信息數(shù)組LINK(1:n)將全程數(shù)組A(low:high)按非降次序分類。LINK中值表示按分類次序給出

A下標的表，并把p置于該表的開始處〃

globalA(low:high),LINK(low,high)

ifhigh-low+1<16〃當集合中的元素個數(shù)足夠少(<化)時，采用更有效的小規(guī)模集合上的分類

算法直接分類〃

thencallINSERTSORT1(A,LINK,low,high,p)〃算法2.7的改進型〃

elsemid—[_(low+high)/2j

callMERGESORT1(low,mid,q)//返回q表〃

callMERGESORT1(mid+1,high,r)〃返回r表〃

callMERGE1(q,r,p)〃將表q和表i?歸并成表p〃

endif

endMERGESORT1

算法2.11使用鏈接表歸并已分類的集合

procedureMERGE1(q,r,p)

〃q和r是全程數(shù)組LINK(1:n)中兩個表的指針。歸并這兩個表，得到一個由p所指示的新表。此表將

A中的元素按非降次序分類。LINK(O)被定義〃

globaln,A(1:n),LINK(1:n)

localintegeri,j,k

i<—q;j<—r;k<—0〃新表在LINK(O)處開始〃

whilei#0andj#0do//當兩表均非空時〃

ifA(i)<AQ)//找較小的關鍵字〃

thenLINK(k)——LINK。)//加一個新關鍵字到表中〃

elseLINK(k)-j;k—j;j-LINK。)//加一個新關鍵字到表中〃

endif

repeat

ifi=9thenLINK(k)=j

elseLINK(k)=i

endif

endMERGE1

MERGES0RT1的調用

>在初次調用時，待分類的n個元素放于A(1:n)中。

>LINK(1:n)初始化為0；

>初次調用：callMERGESORT1(1,n,p)

>p作為按分類次序給出A中元素的指示表的指針。

3)改進歸并分類算法示例

設元素表：(50,10,25,30,15,70,35,55)

采用MERGESORT1對上述元素表分類(不做小規(guī)模集合

的單獨處理)

下表給出在每一次調用MERGESORT1結束后，LINK數(shù)

組的變化情況。

表2.2例2.4中LINK數(shù)組的變化過程

(0)(1)(2)(3)⑷(5)(6)(7)(8)

A—50102530-15703555

LINK000000000

qrP

122201000000(10,50)

343301400000(10,50),(25,30)

232203410000(10,25,30,50)

565503416000(10,25,30,50),(15,70)

787703416Q80(10,25,30,50),(15,70),(35,55)

575503417-086(10,25,30,50)(15,35,55,70)

252285473016(10,15,25,30,35,50,55,70)

在上表的最后一行，p=2返回，得到鏈表(2,5,3,4,7,1,8,6)

即：A(2)^A(5)<A(3)<A(4)<A(7)<A(1)<A(8)<A(6)

5.以比較為基礎分類的時間下界

1.分類的“實質”

給定n個記錄RiR，《淇相應的關鍵字是…,七。

分類就是確定12…,n的一種排列P「P如..Pn，使得記錄的

關鍵字滿足以下非遞減（或非遞增）排列關系

kp〔Wkp2W???Wkpn

從而使n個記錄成為一個按關鍵字有序的序列:

{Rpi,Rp2,…，Rpn}

2.以關鍵字比較為基礎的分類算法的時間下界

最壞情況下的時間下界為：Q(nlogn)

利用二元比較樹證明。

假設參加分類的n個關鍵字A(1),A(2),…,A(n)互異。任意

兩個關鍵字的比較必導致A(i)〈A(j)或A(i)>A(j)的結果。

以二元比較樹描述元素間的比較過程：

>若A(i)<A(j),進入下一級的左分支

>若A(i)>A(j),進入下一級的右分支

算法在外部結點終止。

從根到某外結點的路徑代表某個特定輸入情況下一種唯一的分類排序序列。路

徑長度表示生成該序列代表的分類表所需要的比較次數(shù)。而最長的路徑代表算法在

最壞情況下的執(zhí)行情況，該路徑的長度即是算法在最壞情況下所作的比較次數(shù)。

故，以比較為基礎的分類算法的最壞情況下界等于該算法對應的比較樹的最小

司度。

①由于n個關鍵字有n!種可能的排列，所以分類二元比較樹中將有

n!個外部結點：每個外部結點代表一種特定的排列，該排列對應于某種

特定輸入情況下的分類序列。

②設一棵二元比較樹的所有內結點的級數(shù)均小于或等于k,則該樹

中最多有2k個外結點。

記算法在最壞情況下所作的比較次數(shù)為T(n),則有T(n)二k：生成外

結點所代表的分類序列所需的比較次數(shù)等于該外結點所在的級數(shù)T;

根據(jù)①和②的分析，有：

n!W2T(n)

化簡：

當n〉l時，有n!Nn(nT)(n-2)…(|"n/2"|)2(n/2)石

當n三4時，有T(n)2(n/2)log(n/2)N(n/4)logn

故，任何以比較為基礎的分類算法的最壞情況的時間下界為：

Q(nlogn)

2.5快速分類

1.劃分與快速分類

＞快速分類是一種基于劃分的分類方法；

＞劃分：選取待分類集合A中的某個元素t,按照與t的大小關系重

新整理A中元素，使得整理后t被置于序列的某位置上，

而序列中所有在t以前出現(xiàn)的元素均小于等于t,而所有出

現(xiàn)在t以后的元素均大于等于t。這一元素的整理過程稱為

劃分(Partitioning)。

元素t稱為劃分元素。

＞快速分類：對待排序集合通過反復劃分達到分類目的的分

類算法。

劃分過程(PARTITION)的算法描述

算法2.2用A(m)劃分集合A(m:pA(p)被定義，但為一限界值，

不包含在實際的分類區(qū)間內。

procedurePARTITION(m,p)

V.?

integerglobalA(m:p-1)/

v—A(m);i—m〃A(m)是劃分元素〃

loop

loopi<—i+1untilA(i)>vrepeat〃i由左向右移〃

loopp<—p-1untilA(p)<vrepeat〃p由右向左移〃

ifi<pthen

callINTERCHANGE(A(i),A(P))

elseexit

endif

repeat

A(m)—A(p)；A(p)—v〃劃分元素在位置p〃

endPARTITION

注：

>算法對集合A(m:p-1)進行劃分。并使用待劃分區(qū)間的第一

個元素A(m)作為劃分元素

>A(p)不在劃分區(qū)間內，但被定義，且A(p)三A(m),用于

限界

例2.5劃分實例

⑴(2)⑶⑷⑸(6)⑺(8)(9)(10)iP

A:6570758085605550454-oo29

1..■,11

A:6545758085605550704-oo38

A:654550808560557570+oo47

II

■?I

A:654550558560807570+oo56

I….I

交■-I

換A:654550556085807570+oo65

劃?II

分I

一A:604550556585807570+oo

t

劃分元素定位于此

經(jīng)過一次“劃分”后，實現(xiàn)了對集合元素的調整：

以劃分元素為界，左邊子集合的所有元素均小于等于右

邊子集合的所有元素。

按同樣的策略對兩個子集合進行分類處理。當子集合分類

完畢后，整個集合的分類也完成了。這一過程避免了子集合

的歸并操作。這一分類方法稱為快速分類。

2.快速分類算法

——一種通過反復使用劃分過程PARTITION實現(xiàn)對集合

元素分類的算法。

算法2.13快速分類

procedureQUICKSORT(p,q)

〃將數(shù)組A(1:n)中的元素A(p),…A(q)按遞增的方式分類。

A(n+1)有定義，且假定A(n+1)—+8〃

integerp,q;globaln,A(1:n)

ifp<qthen

j-q+1〃進入時，A(j)定義了劃分區(qū)間［p,q］的上界，首次調用時j=n+1

callPARTITION(pJ)〃出口時，j帶出此次劃分后劃分元素所在的卜標位置〃

callQUICKSORT(p,j-1)〃對前一子集合遞歸調用

callQUICKSORT］+1,q)〃對后一子集合遞歸調用

endif

endQUICKSORT

3.快速分類分析

■統(tǒng)計的對象：元素的比較次數(shù)——Partition過程，記為：C(n)

■兩點假設

①參加分類的n個元素各不相同

②PARTITION中的劃分元素v是隨機選取的(針對平均情況的分

析)

>隨機選取劃分元素：

在劃分區(qū)間隨機生成某一坐標：i-RANDOM(m.p-l)；

調換A(m)與A⑴：v<—A(i);A(i)<—A(m);i<—m

作用：將隨機指定的劃分元素的值調換到A(m)位置。算法主體

不變。之后，仍從A(m)開始執(zhí)行劃分操作。

遞歸層次n個元素參加劃分和分類

設在任一級遞歸調用上，調用PARTITION處理的所有元素總數(shù)為r,則，初始

時r二n,以后的每級遞歸上，由于刪去了上一級的劃分元素，故r比上一級至少1：

理想情況，第一級少1,第二級少2,第三級少4,...；

最壞情況，每次僅減少1（每次選取的劃分元素剛好是當前集合中最小或最大者）

■最壞情況分析

>記最壞情況下的元素比較次數(shù)是Cw(n)；

>PARTITION一次調用中的元素比較數(shù)是p-m+1,若一級

遞歸調用上處理的元素總數(shù)為r,則PARTITION的比較總數(shù)

為0(r)。

最壞情況下(第i次調用Partition所得的劃分元素恰好是

第i小元素)，每級遞歸調用的元素總數(shù)僅比上一級少1,故

Cw(n)是r由n到2的累加和。

2

即：Cw(n)==0(n)

■平均情況分析

平均情況是指集合中的元素以任意順序排列，且任選元素

作為劃分元素進行劃分和分類，在這些所有可能的情況下，算

法執(zhí)行性能的平均值。

設調用PARTITION(m,p)時，所選取劃分元素v恰好是

A(m:p-1)中的第i小元素的概率相等。則經(jīng)過一

次劃分，所留下的待分類的兩個子文件恰好是A(m:j-1)和

A(j+1:p-1)的概率是：1/(p-m),記平均情猊卞的元素

比較次數(shù)是CA(FI)；則有，

q⑺=〃+1+!z(g(i)+g(1))

X<k<n

其中，

n+1是PARTITION第一次調用時所需的元素比較次數(shù)。

>CA(0)=CA(1)=0

化簡上式可得：

CA(n)/(n+1)=CA(n-l)/n+2/(n+1)

=CA(n-2)/(n-l)+2/n+2/(n+1)

=CA(n-3)/(n-2)+2/(nT)+2/n+2/(n+1)

=CA(1)/2+2

?)<k<n+\

由于

3<k<n-\-\

所以得，CA(n)<2(n+l)loge(n+1)=0(nlogn)

■空間分析

最壞情況下，遞歸的最大深度為n-1.

需要棧空間：0(n)

使用一個迭代模型可以將棧空間總量減至O(logn)

4,快速分類算法的迭代模型

處理策略：每次在Partition將文件A(p:q)分成兩個文件

A(p:j-1)和A(j+1,q)后，先對其中較小的子文件

進行分類。當小的子文件分類完成后，再對較

大的子文件進行分類。

棧：需要一個?？臻g保存目前暫不分類的較大子文件。并

在較小子文件分類完成后，從棧中退出最新的較大子

文件進行下一步分類。

棧空間需要量：O(logn)

算法的終止：當?？諘r，整個分類過程結束。

cr

d

O

算法2.14QuickSort2(p,q)

integerSTACK(1:max),top//max=2[)ogn]

globalA(1:n);localintegerj

top—0

loop

whilep<qdo

j-q+1

callPARTITION(pJ);

ifj-p<q-j〃先對較小的子文件分類，并將規(guī)模較大的子文件入棧

thenSTACK(top+1)<-j+1；STACK(top+2)fq-j?1

elseSTACK(top+1Kp;STACK(top+2)<-j-1；P—j+1

endif

top-top+2//調整棧頂指針

repeat

iftop=0thenreturnendif〃如果棧為空，算法結束

q<-STACK(top);p<-STACK(top-1);top-top-2〃從棧中退出先前保存的

較大的子文件

repeat

endQUICKS0RT2

?快速分類算法迭代模型的空間分析

算法2.14的最大空間是O(logn)

推導：

設算法所需的最大?？臻g是S(n),則有

2+S(L(n-l)/2j)n>l

S(〃)=

0n<l

2.6選擇問題

1.問題描述

在n個元素的表A(