分治法-分而治之課件

第四章分治法

——“分”而治之4.1一般方法對(duì)大規(guī)模問(wèn)題的求解利用分治法求解大規(guī)模問(wèn)題1.基本思想分而治之方法法與軟件設(shè)計(jì)的模塊化方法非常相似。為解決一個(gè)大問(wèn)題，可以（1）把它分解成兩個(gè)或多個(gè)更小的問(wèn)題；（2）分別解決每個(gè)小問(wèn)題；（3）把各小問(wèn)題的解答組合起來(lái)，即可得到原問(wèn)題的解。小問(wèn)題通常與原問(wèn)題相似或同質(zhì)，因而可以遞歸地使用分而治之策略解決。12/3/2023通常，子問(wèn)題與原始問(wèn)題“同質(zhì)”12/3/2023例[找偽幣]假設(shè)16枚金幣中有一枚是偽造的，真假金幣的區(qū)別僅是重量不同(偽幣輕一些），利用一個(gè)沒(méi)有砝碼的天平作工具，找出這枚偽造的金幣。

方法1：比較硬幣1和2的重量，有一個(gè)輕則找到；否則比較硬幣3和4，依次比較下去，直到找到。最多8次比較。方法2：利用分治法。16個(gè)硬幣分為兩組，每組8個(gè)，比較重量，偽幣在輕的一組。將輕的一組再分為兩組，每組4個(gè)……繼續(xù)劃分下去，依次每組2個(gè)，每組1個(gè)，此時(shí)找到。12/3/2023算法4.1分治策略的抽象化控制procedureDANDC(p,q)globaln,A(1:n);integerm,p,q;//1≤p≤q≤n//ifSMALL(p,q)thenreturn(G(p,q))elsem←DIVIDE(p,q)//p≤m＜q//return(COMBINE(DANDC(p,m),DANDC(m+1,q)))endifendDANDC注：k=2:二分是最常用的分解策略；SMALL(p,q)：布爾函數(shù)，判斷輸入規(guī)模q-p+1是否足夠小而無(wú)需再進(jìn)一步分就可求解；G(p,q)：對(duì)輸入規(guī)模為q-p+1的子問(wèn)題求解（SMALL(p,q)為真時(shí)）；DIVIDE(p.q)：對(duì)輸入規(guī)模為q-p+1的子問(wèn)題進(jìn)一步分解，返回值為[p,q]區(qū)間進(jìn)一步的分割點(diǎn)（SMALL(p,q)不為真時(shí)）；COMBINE(x,y)：子結(jié)果的合并函數(shù)，將區(qū)間[p,m]和[m+1,q]上的子問(wèn)題的解合并成上級(jí)區(qū)間[p,q]上的“較完整”的解。當(dāng)p=1,q=n時(shí)，就得到整個(gè)問(wèn)題的解。2.分治策略的抽象化控制12/3/2023DANDC的計(jì)算時(shí)間若所分成的兩個(gè)子問(wèn)題的輸入規(guī)模大致相等，則DANDC總的計(jì)算時(shí)間可用遞歸關(guān)系式表示，如下：g(n)n足夠小T(n)=2T(n/2)+f(n)否則

注：

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

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

f(n)：表示COMBINE對(duì)兩個(gè)子區(qū)間的子結(jié)果進(jìn)行合并的時(shí)間（該公式針對(duì)具體問(wèn)題有各種不同的變形）12/3/20234.2二分檢索（折半查找）1.問(wèn)題的描述已知一個(gè)按非降次序排列的元素表a1,a2,…,an,判定某給定的元素x是否在該表中出現(xiàn)。若是，則找出x在表中的位置并返回其所在下標(biāo)若非，則返回0值。12/3/2023分治求解策略分析：定義問(wèn)題的形式描述：I=(n,a1,a2,…,an,x)問(wèn)題分解：選取下標(biāo)k，由此將I分解為3個(gè)子問(wèn)題：I1=(k-1,a1,a2,…,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,ak+2,…,an,x)對(duì)于I2，若ak=x，則有解k，對(duì)I1、I3不用再求解；否則，若x<ak，則只在I1中求解，對(duì)I3不用求解；若x>ak，則只在I3中求解，對(duì)I1不用求解；I1、I3上的求解可再次采用分治方法劃分后求解（遞歸過(guò)程）12/3/20232.二分檢索算法算法4.3二分檢索procedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low←1;high←n;whilelow≤highdo

mid←case:x<A(mid):high←mid-1:x>A(mid):low←mid+1:else:j←mid;returnendcaserepeatj←0endBINSRCH注：給定一個(gè)按非降次序排列的元素?cái)?shù)組A(1:n)，n≥1,判斷x是否出現(xiàn)。若是，置j，使得x=A(j)若非，j=012/3/2023例2.1：設(shè)A(1:9)=(-15，-6，0，7，9，23，54，82，101)在A中檢索x=101，-14，82。執(zhí)行軌跡見(jiàn)下表1表1運(yùn)行軌跡示例x=101x=-14x=82lowhighmidlowhighmidlowhighmid19519519569714269789811189899921找不到找到

找到

成功的檢索不成功的檢索成功的檢索12/3/20233.算法的正確性證明定理4.1過(guò)程BINSRCH(A,n,x,j)能正確運(yùn)行證明：1）在具體指定A中的數(shù)據(jù)元素及x的數(shù)據(jù)類(lèi)型后，算法中的所有運(yùn)算都能按要求正確運(yùn)行——即首先滿(mǎn)足確定性和能行性2）終止性算法初始部分置low←1,high←n

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

②否則，進(jìn)入循環(huán)，計(jì)算mid,或x=A(mid)，j置為mid，算法終止；或x<A(mid)，置high←mid-1，搜索范圍實(shí)際縮小為[low,mid-1]，進(jìn)入下次循環(huán)，對(duì)[mid+1,high]區(qū)間不做進(jìn)一步搜索；或x>A(mid)，置low←mid+1，進(jìn)入下次循環(huán)；搜索范圍實(shí)際縮小為[mid+1,high]，對(duì)[low,mid-1]區(qū)間不做進(jìn)一步搜索；

因low,high,mid都是整型變量，故按照上述規(guī)則，在有限步內(nèi)，或找到某個(gè)mid，有A(mid)=x；或變得low>high，在A中沒(méi)有找到任何元素等于x，算法終止。12/3/20234.性能分析1）空間特性n+5個(gè)空間位置——О(n)2)時(shí)間特性區(qū)分以下情況，并進(jìn)行相應(yīng)的分析成功檢索：所檢索的x出現(xiàn)在A中。成功檢索情況共有n種：x恰好是A中的某個(gè)元素，A中共有n個(gè)元素，故有n種可能的情況不成功檢索：所檢索的x不出現(xiàn)在A中。不成功檢索情況共有n+1種：x<A(1),或A(i)<x<A(i+1),1≤i<n-1或x>A(n)

成功/不成功檢索的最好情況：執(zhí)行步數(shù)最少，計(jì)算時(shí)間最短成功/不成功檢索的最壞情況：執(zhí)行步數(shù)最多，計(jì)算時(shí)間最長(zhǎng)成功/不成功檢索的平均情況：一般情況下的計(jì)算時(shí)間12/3/2023實(shí)例分析（例4.1）頻率計(jì)數(shù)特征while循環(huán)體外語(yǔ)句的頻率計(jì)數(shù)為1集中考慮while循環(huán)中的x與A中元素的比較（其它運(yùn)算的頻率計(jì)數(shù)與之有相同的數(shù)量級(jí)）假定只需一次比較就可確定case語(yǔ)句控制是三種情況的哪一種。查找每個(gè)元素所需的元素比較次數(shù)統(tǒng)計(jì)如下：A⑴⑵⑶⑷⑸⑹⑺⑻⑼元素-15-6079235482101成功檢索比較次數(shù)323413234

不成功檢索比較次數(shù)333443334412/3/2023成功檢索最好：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次12/3/2023二元比較樹(shù)算法執(zhí)行過(guò)程的主體是x與一系列中間元素A(mid)比較?？捎靡豢枚獦?shù)描述這一過(guò)程，并稱(chēng)之為二元比較樹(shù)。構(gòu)造：比較樹(shù)由稱(chēng)為內(nèi)結(jié)點(diǎn)和外結(jié)點(diǎn)的兩種結(jié)點(diǎn)組成：內(nèi)結(jié)點(diǎn)：表示一次元素比較，用圓形結(jié)點(diǎn)表示，存放一個(gè)mid值；代表一次成功檢索；外結(jié)點(diǎn)：在二分檢索算法中表示一種不成功檢索的情況，用方形結(jié)點(diǎn)表示。路徑：表示一個(gè)元素的比較序列。例4.1的二元比較樹(shù)12/3/2023基于二元比較樹(shù)的分析若x在A中出現(xiàn)，則算法的執(zhí)行過(guò)程在一個(gè)圓形的內(nèi)結(jié)點(diǎn)處結(jié)束。若x不在A中出現(xiàn)，則算法的執(zhí)行過(guò)程在一個(gè)方形的外結(jié)點(diǎn)處結(jié)束——外結(jié)點(diǎn)不代表元素的比較，因?yàn)楸容^過(guò)程在該外結(jié)點(diǎn)的上一級(jí)的內(nèi)結(jié)點(diǎn)處結(jié)束。

例4.1的二元比較樹(shù)12/3/2023定理4.2若n在區(qū)域[2k-1,2k)中，則對(duì)于一次成功的檢索，BINSRCH至多做k次比較；對(duì)于一次不成功的檢索，或者做k-1次比較，或者做k次比較。證明：要點(diǎn)：成功檢索都在內(nèi)結(jié)點(diǎn)處結(jié)束，不成功檢索都在外結(jié)點(diǎn)處結(jié)束當(dāng)2k-1≤n<2k時(shí)，所有內(nèi)結(jié)點(diǎn)在1至k級(jí)，所有外結(jié)點(diǎn)在第k級(jí)或第k+1級(jí)，故：成功檢索在i級(jí)終止所需要的元素比較次數(shù)是i不成功檢索在i級(jí)外部結(jié)點(diǎn)終止的元素比較次數(shù)是i-112/3/2023BINSRCH計(jì)算復(fù)雜度的理論分析1）不成功檢索的最好、最壞和平均情況的計(jì)算時(shí)間均為——外結(jié)點(diǎn)處在最末的兩級(jí)上；2）最好情況下的成功檢索的計(jì)算時(shí)間為最壞情況下的成功檢索的計(jì)算時(shí)間為12/3/20233）平均情況下的成功檢索的計(jì)算時(shí)間分析利用外部結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)到根距離和之間的關(guān)系進(jìn)行推導(dǎo)：記，由根到所有內(nèi)結(jié)點(diǎn)的距離之和稱(chēng)為內(nèi)部路徑長(zhǎng)度，記為I；由根到所有外部結(jié)點(diǎn)的距離之和稱(chēng)為外部路徑長(zhǎng)度，記為E。則有，E=I+2n

記，

U(n)是平均情況下不成功檢索的計(jì)算時(shí)間，則U(n)=E/(n+1)

S(n)是平均情況下成功檢索的計(jì)算時(shí)間，則S(n)=I/n+1

利用上述公式，可有:S(n)=(1+1/n)U(n)-1當(dāng)n→∞,S(n)∝U(n)

，而U(n)=

所以S(n)=12/3/20234.以比較為基礎(chǔ)檢索的時(shí)間下界問(wèn)題：設(shè)n個(gè)元素的數(shù)組A(1:n)有A(1)<A(2)<…<A(n)。檢索一給定元素x是否在A中出現(xiàn)。定理4.2給出了二分檢索算法的時(shí)間下界，是否預(yù)計(jì)還存在有以元素比較為基礎(chǔ)的另外的檢索算法，它在最壞情況下比二分檢索算法在計(jì)算時(shí)間上有更低的數(shù)量級(jí)?以比較為基礎(chǔ)的算法：假定算法中只允許進(jìn)行元素間的比較，而不允許對(duì)它們實(shí)施其它運(yùn)算。12/3/2023注：每個(gè)內(nèi)結(jié)點(diǎn)表示一次元素的比較。每棵比較樹(shù)中恰好含有n個(gè)內(nèi)結(jié)點(diǎn)，分別與n個(gè)不同i值相對(duì)應(yīng)；每個(gè)外結(jié)點(diǎn)對(duì)應(yīng)一次不成功的檢索，并恰好又n+1個(gè)外結(jié)點(diǎn)對(duì)應(yīng)于n+1中不成功檢索的情況。任何以比較為基礎(chǔ)的檢索算法，其執(zhí)行過(guò)程都可以用二元比較樹(shù)來(lái)描述。12/3/2023以比較為基礎(chǔ)的有序檢索問(wèn)題最壞情況的時(shí)間下界定理4.3設(shè)A(1:n)含有n(n≥1)個(gè)不同的元素，排序?yàn)锳(1)<A(2)<…<A(n)。又設(shè)用以比較為基礎(chǔ)的算法去判斷是否，則這樣的任何算法在最壞情況下所需的最小比較次數(shù)FIND(n)有：證明：從模擬求解檢索問(wèn)題算法的比較樹(shù)可知，F(xiàn)IND(n)不大于樹(shù)中由根到一個(gè)葉子的最長(zhǎng)路徑的距離。而所有樹(shù)中必定有n個(gè)內(nèi)結(jié)點(diǎn)與x在A中的n中可能的出現(xiàn)相對(duì)應(yīng)。如果一棵二元樹(shù)的所有內(nèi)結(jié)點(diǎn)所在的級(jí)數(shù)小于或等于k，則最多有2k-1個(gè)內(nèi)結(jié)點(diǎn)。故n≤2k-1,即12/3/2023任何一種以比較為基礎(chǔ)的算法，在最壞情況下的計(jì)算時(shí)間都不低于Ο(logn)。因此，不可能存在最壞情況比二分檢索數(shù)量級(jí)還低的算法。二分檢索是解決檢索問(wèn)題的最優(yōu)的最壞情況算法。12/3/20234.3找最大和最小元素問(wèn)題描述：給定含有n個(gè)元素的集合，在其中找出最大和最小元素。12/3/20231.直接找最大和最小元素算法4.5直接找最大和最小元素procedureSTRAITMAXMIN(A,n,max,min)//將A中的最大值置于max，最小值置于min//Integeri,nmax←min←A(1)fori←2tondoifA(i)>maxthenmax←A(i)endififA(i)<minthenmin←A(i)endifrepeatendSTRAITMAXMIN

算法的性能：只考慮算法中的比較運(yùn)算，以此代表算法的執(zhí)行特征；該算法最好、最壞、平均情況下均需要做2(n-1)次元素比較12/3/2023STRAITMAXMIN算法的一種簡(jiǎn)單改進(jìn)形式:procedureSTRAITMAXMIN1(A,n,max,min)integeri,nmax←min←A(1)fori←2tondoifA(i)>maxthenmax←A(i)endifelseifA(i)<minthenmin←A(i)endifrepeatendSTRAITMAXMIN1這使得，最好情況：按遞增次序排列，元素比較次數(shù)為n-1次最壞情況：按遞減次序排列，元素比較次數(shù)為2(n-1)次平均情況：元素比較次數(shù)為3(n-1)/2次12/3/20232.分治求解策略記問(wèn)題的一個(gè)實(shí)例為：I=(n,A(1),…,A(n))采用二分法將I分成兩個(gè)子集合處理

I1=(,A(1),…，A())，和

I2=(n-,A(+1),…，A(n))則有，MAX(I)=max(MAX(I1),MAX(I2))MIN(I)=min(MIN(I1),MIN(I2))采用遞歸的設(shè)計(jì)策略，得到以下算法：12/3/20233.一種遞歸求解策略算法4.6遞歸求取最大和最小元素procedureMAXMIN(i,j,fmax,fmin)//A(1:n)是含有n個(gè)元素的數(shù)組，參數(shù)I,j是整數(shù)，1≤i,j≤n//

//該過(guò)程把A(i:j)中的最大和最小元素分別賦給fmax和fmin//integeri,j;globaln,A(1:n)case:i=j:fmax←fmin←A(i)//只有一個(gè)元素:i=j-1:ifA(i)<A(j)thenfmax←A(j);fmin←A(i)elsefmax←A(i);fmin←A(j)//兩個(gè)元素的情況endif:else:mid←//取中callMAXMIN(i,mid,gmax,gmin)callMAXMIN(mid+1,j,hmax,hmin)

fmax←max(gmax,hmax);fmin←min(gmin,hmin)endcaseendMAXMIN12/3/2023例：在A(1:9)=(22,13,-5,-8,15,60,17,31,47)上執(zhí)行算法4.6每個(gè)結(jié)點(diǎn)內(nèi)的值分別是：i,j,fmax,fmin遞歸調(diào)用遞歸調(diào)用分解過(guò)程遞歸調(diào)用的返回12/3/2023性能分析(T(n)表示元素比較數(shù)）0n=1T(n)=1n=2n>2當(dāng)n是2的冪時(shí)(n=2k),化簡(jiǎn)上式有，T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=…=2k-1T(2)+=2k-1+2k-2=3n/2-212/3/2023性能分析1）與STRAITMAXMIN算法相比，比較次數(shù)減少了25%（3n/2-2:2n-2)。已經(jīng)達(dá)到了以元素比較為基礎(chǔ)的找最大最小元素的算法計(jì)算時(shí)間的下界：2）存在的問(wèn)題：空間占用量大

?有

級(jí)的遞歸，入棧參數(shù)：

?i,j,fmax,fmin和返回地址五個(gè)值。時(shí)間可能不比預(yù)計(jì)的理想如果元素A(i)和A(j)的比較與i和j的比較相差不大時(shí)，算法MAXMIN不可取。12/3/2023假設(shè)元素的比較與i和j的比較時(shí)間相同（整型數(shù)）。又設(shè)case語(yǔ)句中僅需一次i和j的比較就能夠確定是哪種情況。記此時(shí)MAXMIN的頻率計(jì)數(shù)為C(n)，n=2k(k為正整數(shù)）。則有，2n=2C(n)=2C(n/2)+3n>2化簡(jiǎn)得，C(n)=2C(n/2)+3=…=5n/2-3按照同樣的假設(shè)，重新估算STRAITMAXMIN算法的比較次數(shù)為：3(n-1)?？紤]MAXMIN算法遞歸調(diào)用的開(kāi)銷(xiāo)，此時(shí)MAXMIN算法的效率可能還不如STRAITMAXMIＮ算法。12/3/2023結(jié)論：如果A中的元素間的比較代價(jià)遠(yuǎn)比整型數(shù)（下標(biāo)）的比較昂貴，則分治方法將產(chǎn)生一個(gè)效率較高的算法；反之，可能僅得到一個(gè)低效的算法。故，分治策略只能看成一個(gè)較好的但并不總是成功

的算法設(shè)計(jì)指導(dǎo)。12/3/2023思考題：最大子段和問(wèn)題求數(shù)列的最大子段和。給定n個(gè)元素的整數(shù)列(可能為負(fù)整數(shù))a1，a2，…，an，求形如ai，ai+1，aj，i，j=1，2，…，n，i<=j的子段，使其和為最大。例如，當(dāng)(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2) max_sum=20，best_i=2，best_j=412/3/2023若用一般的二分法解決該實(shí)例？分解為兩組(-2,11,-4)和(13,-5,-2)1113不獨(dú)立，子問(wèn)題中間有公共子問(wèn)題12/3/2023對(duì)重疊子問(wèn)題專(zhuān)門(mén)處理“三”分治情形1情形2情形3將a[1..n]分為長(zhǎng)度相等的2段a[1..(n/2)]和a[(n/2)+1..n],分別求這2段最大子段和,則a[1.n]最大子段和有3種情形:1)a[1..n]的最大子段和與a[1..(n/2)]的最大子段和相同；2)a[1..n]的最大子段和與a[(n/2)+1..n]的最大字段和相同;3)a[1..n]的最大字段和為a[i..j],且1≤i≤(n/2),(n/2)+1≤j≤n。情況1)和情況2)可分別遞歸求得。對(duì)于情況3）,a[(n/2)]與a[(n/2)+1]一定在最大子段中。因此,可以計(jì)算出a[i..(n/2)]最大值s1和a[(n/2)+1..j]最大值s2。則s1+s2即為情況3)時(shí)最優(yōu)值。12/3/2023“三”分治情形1情形2情形3對(duì)分解得到的左右子段，求左右子段內(nèi)部的最大子段和；左子段中滿(mǎn)足以下條件的最大的子段和s1：以任何位置i開(kāi)始，結(jié)尾處n/2結(jié)束；右子段中滿(mǎn)足以下條件的最大的子段和s2：以起始位置n/2+1開(kāi)始，任何位置j結(jié)束；原問(wèn)題最大子段和是左右子段內(nèi)最大和與兩個(gè)子段最大值求和s1+s2中的大者。12/3/20234.4歸并分類(lèi)1.分類(lèi)問(wèn)題——排序給定一n個(gè)元素的集合A，按照某種方法將A中的元素按非降或非增次序排列。分類(lèi)：內(nèi)排序，外排序常見(jiàn)內(nèi)排序方法：冒泡排序插入排序歸并排序快速排序堆排序…[例]輸入：（8，5，4，9）輸出：（4，5，8，9）或（9，8，5，4）12/3/20232.插入分類(lèi)

算法4.7插入分類(lèi)procedureINSERTIONSORT(A,n)//將A(1：n)中的元素按非降次序分類(lèi)，n≥1//A(0)←-∞//設(shè)置初始邊界值forj←2tondo//A(1:j-1)已分類(lèi)//item←A(j);i←j-1whileitem<A(i)do//0≤i<j//A(i+1)←A(i);i←i-1repeatA(i+1)←item;repeatendINSERTIONSORT

(8,5,4,9)(8,5,4,9)

(5,8,4,9)(5,8,

4,9)(4,5,8,9)(4,5,8,9)12/3/2023性能分析：最壞情況：輸入數(shù)據(jù)按非增次序排列,每次內(nèi)層while循環(huán)執(zhí)行j次（j=2,3,…,n)。則有，最好情況：輸入數(shù)據(jù)已按非降序排列，不進(jìn)入while循環(huán)，則最好情況下計(jì)算時(shí)間為Ω(n)12/3/20233.分治策略求解

基本設(shè)計(jì)思想：將原始數(shù)組A中的元素分成兩個(gè)子集合：A1(1:)和A2(+1:n)。分別對(duì)這兩個(gè)子集合單獨(dú)分類(lèi)，然后將已分類(lèi)的兩個(gè)子序列歸并成一個(gè)含有n個(gè)元素的分類(lèi)好的序列。這樣的一個(gè)分類(lèi)過(guò)程稱(chēng)為歸并分類(lèi)。

12/3/2023算法4.8歸并分類(lèi)

procedureMERGESORT(low,high)//A(low:high)是一個(gè)全程數(shù)組，它含有high-low+1≥0個(gè)待分類(lèi)的元素//integerlow,highiflow<highthen

mid←//計(jì)算中分點(diǎn)//callMERGESORT(low,mid)//在第一個(gè)子集合上分類(lèi)(遞歸)//callMERGESORT(mid+1,high)//在第二個(gè)子集合上分類(lèi)(遞歸)//callMERGE(low,mid,high)//歸并已分類(lèi)的兩子集合//endifendMERGESORT12/3/2023算法4.9使用輔助數(shù)組歸并兩個(gè)已分類(lèi)的集合procedureMERGE(low,mid,high)//A(low,high)是一個(gè)全程數(shù)組,它含有兩個(gè)放在A(low,mid)和A(mid+1,high)中的已分類(lèi)的子集合.目標(biāo)是將這兩個(gè)已分類(lèi)的集合歸并成一個(gè)集合，并存放到A(low,high)中//integerh,I,j,k,low,mid,high;//low≤mid＜high//globalA(low,high);localB(low,high)h←low;i←low;j←mid+1;whileh≤midandj≤highdo//當(dāng)兩個(gè)集合都沒(méi)有取盡時(shí),將較小的元素先存放到B中//ifA(h)≤A(j)thenB(i)←A(h);h←h+1//如果前一個(gè)數(shù)組中的元素較小//elseB(i)←A(j);j←j+1//如果后一個(gè)數(shù)組中的元素較小//endifrepeat

//處理尚有剩余元素的集合//ifh>midthenfork←jtohighdoB(i)←A(k);i←i+1;repeatelsefork←htomiddoB(i)←A(k);i←i+1;repeatendiffork←lowtohighdoA(k)←B(k)repeat//將已歸并的集合復(fù)制到A中//endMERGE12/3/2023性能分析1)過(guò)程MERGE的歸并時(shí)間與兩數(shù)組元素的總數(shù)成正比(可表示為:cn,n為元素?cái)?shù),c為某正常數(shù))2)過(guò)程MERGESORT的分類(lèi)時(shí)間用遞推關(guān)系式表示如下:an=1,a是常數(shù)T(n)=2T(n/2)+cnn>1,c是常數(shù)化簡(jiǎn):若n=2k,則有,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<n<2k+1,則有T(n)≤T(2k+1)。所以得：T(n)=Ο(nlogn)

12/3/2023歸并分類(lèi)示例設(shè)A=（310，285，179，652，351，423，861，254，450，520）1）劃分過(guò)程310，285，179，652，351，423，861，254，450，520310，285，179，652，351423，861，254，450，520310，285，179652，351310，285179310285652351423，861，254450，520423，86125442386145052012/3/20232）歸并過(guò)程首先進(jìn)入左分枝的劃分與歸并。首先形成的劃分狀態(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，652|423，861，254，450，520）第四次歸并：（179，285，310，351，652|423，861，254，450，520）進(jìn)入右分枝的劃分與歸并過(guò)程（略）12/3/20233）用樹(shù)結(jié)構(gòu)描述歸并分類(lèi)過(guò)程12/3/20234.歸并分類(lèi)算法的改進(jìn)1）算法4.8存在的問(wèn)題遞歸層次太深在MERGESORT的執(zhí)行過(guò)程中，當(dāng)集合僅含有兩個(gè)元素時(shí)，仍要進(jìn)一步做遞歸調(diào)用，直至每個(gè)集合僅含有一個(gè)元素時(shí)才退出遞歸調(diào)用。在集合含有僅相當(dāng)少的元素時(shí)，較深層次的遞歸調(diào)用使得時(shí)間過(guò)多地消耗在處理遞歸上。元素在數(shù)組A和輔助數(shù)組B之間的頻繁移動(dòng)每次歸并，都要首先將A中的元素移到B中，在由B復(fù)制到A的對(duì)應(yīng)位置上。12/3/20232）改進(jìn)措施針對(duì)遞歸層次問(wèn)題采用能在小規(guī)模集合上有效工作的其它算法，直接對(duì)小規(guī)模集合處理。如INSERTIONSORT算法針對(duì)元素頻繁移動(dòng)問(wèn)題采用一個(gè)稱(chēng)為鏈接信息數(shù)組LINK（1：n）的數(shù)據(jù)結(jié)構(gòu)，記錄歸并過(guò)程中A中的元素相對(duì)于其排序后在分類(lèi)表中位置坐標(biāo)的鏈接關(guān)系。LINK(i)取值于[1，n]，是指向A的元素的指針：在分類(lèi)表中它指向下一個(gè)元素在A中的位置坐標(biāo)。12/3/2023例：LINK(1)(2)(3)(4)(5)(6)(7)(8)

6

4

7

1

3

0

8

0該表中含有兩個(gè)子表，0表示表的結(jié)束。設(shè)置表頭指針Q和R分別指向兩個(gè)子表的起始處：Q=2，R=5；則有，表1：Q(2，4，1，6)，經(jīng)過(guò)分類(lèi)后有：A(2)≤A(4)≤A(1)≤A(6)表2：R(5，3，7，8)，同樣有：A(5)≤A(3)≤A(7)≤A(8)

鏈接信息表在歸并過(guò)程中的應(yīng)用：將歸并過(guò)程中元素在A和B之間移動(dòng)的過(guò)程變成更改LINK所指示的鏈接關(guān)系，從而避免移動(dòng)元素的本身。

分類(lèi)表可以通過(guò)LINK的表頭指針和讀取LINK中的鏈接關(guān)系取得。12/3/2023改進(jìn)后的歸并分類(lèi)模型算法4.10使用鏈接信息數(shù)組的歸并分類(lèi)模型procedureMERGESORT1(low,high,p)//利用鏈接信息數(shù)組LINK(1:n)將全程數(shù)組A(low:high)按非降次序分類(lèi)。LINK中值表示按分類(lèi)次序給出A下標(biāo)的表，并把p置于該表的開(kāi)始處//globalA(low:high),LINK(low,high)ifhigh-low+1<16//當(dāng)集合中的元素個(gè)數(shù)足夠少(<16)時(shí)，采用更有效的小規(guī)模集合上的分類(lèi)算法直接分類(lèi)//thencallINSERTSORT1(A,LINK,low,high,p)//算法2.7的改型//elsemid←callMERGESORT1(low,mid,q)//返回q表//callMERGESORT1(mid+1,high,r)//返回r表//callMERGE1(q,r,p)//將表q和表r歸并成表p//endifendMERGESORT112/3/2023算法4.11使用鏈接表歸并已分類(lèi)的集合

procedureMERGE1(q,r,p)//q和r是全程數(shù)組LINK(1:n)中兩個(gè)表的指針。歸并這兩個(gè)表，得到一個(gè)由p所指示的新表。此表將A中的元素按非降次序分類(lèi)。LINK(0)被定義//globaln,A(1:n),LINK(1:n)localintegeri,j,ki←q;j←r;k←0

//新表在LINK(0)處開(kāi)始//whilei≠0andj≠0do

//當(dāng)兩表均非空時(shí)//ifA(i)≤A(j)

//找較小的關(guān)鍵字//thenLINK(k)←i;k←i;i←LINK(i)

//加一個(gè)新關(guān)鍵字到表中//elseLINK(k)←j;k←j;j←LINK(j)

//加一個(gè)新關(guān)鍵字到表中//endifrepeatifi=0thenLINK(k)=jelseLINK(k)=iendifp=LINK(0)endMERGE112/3/2023MERGESORT1的調(diào)用在初次調(diào)用時(shí)，待分類(lèi)的n個(gè)元素放于A(1:n)中。LINK(1:n)初始化為0；初次調(diào)用：callMERGESORT1(1,n,p)p作為按分類(lèi)次序給出A中元素的指示表的指針。3）改進(jìn)歸并分類(lèi)算法示例設(shè)元素表：（50，10，25，30，15，70，35，55）采用MERGESORT1對(duì)上述元素表分類(lèi)（不做小規(guī)模集合的單獨(dú)處理）下表給出在每一次調(diào)用MERGESORT1結(jié)束后，LINK數(shù)組的變化情況。12/3/2023在上表的最后一行，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)12/3/20235.以比較為基礎(chǔ)分類(lèi)的時(shí)間下界任何以關(guān)鍵字比較為基礎(chǔ)的分類(lèi)算法，其最壞情況下的時(shí)間下界都為：Ω(nlogn)利用二元比較樹(shù)證明。假設(shè)參加分類(lèi)的n個(gè)關(guān)鍵字A(1),A(2),…,A(n)互異。任意兩個(gè)關(guān)鍵字的比較必導(dǎo)致A(i)<A(j)或A(i)>A(j)的結(jié)果。以二元比較樹(shù)描述元素間的比較過(guò)程：若A(i)<A(j)，進(jìn)入下一級(jí)的左分支若A(i)>A(j)，進(jìn)入下一級(jí)的右分支12/3/2023算法在外部結(jié)點(diǎn)終止。從根到某外結(jié)點(diǎn)的路徑代表某個(gè)特定輸入情況下一種唯一的分類(lèi)排序序列。路徑長(zhǎng)度表示生成該序列代表的分類(lèi)表所需要的比較次數(shù)。而最長(zhǎng)的路徑代表算法在最壞情況下的執(zhí)行情況，該路徑的長(zhǎng)度即是算法在最壞情況下所作的比較次數(shù)。故，以比較為基礎(chǔ)的分類(lèi)算法的最壞情況下界等于該算法對(duì)應(yīng)的比較樹(shù)的最小高度。12/3/2023①由于n個(gè)關(guān)鍵字有n!種可能的排列，所以二元比較樹(shù)中將有n!個(gè)外部結(jié)點(diǎn)：每種排列對(duì)應(yīng)于某種特定輸入情況下的分類(lèi)情況，每個(gè)外部結(jié)點(diǎn)表示一種可能的分類(lèi)序列。②設(shè)一棵二元比較樹(shù)的所有內(nèi)結(jié)點(diǎn)的級(jí)數(shù)均小于或等于k，則該樹(shù)中最多有2k個(gè)外結(jié)點(diǎn)。記算法在最壞情況下所作的比較次數(shù)為T(mén)(n)，則有T(n)=k：生成外結(jié)點(diǎn)所代表的分類(lèi)序列所需的比較次數(shù)等于該外結(jié)點(diǎn)所在的級(jí)數(shù)-1；根據(jù)①和②的分析，有：

n!≤2T(n)化簡(jiǎn)：當(dāng)n>1時(shí)，有n!≥n(n-1)(n-2)…()≥(n/2)n/2當(dāng)n≥4時(shí)，有T(n)≥(n/2)log(n/2)≥(n/4)logn故，任何以比較為基礎(chǔ)的分類(lèi)算法的最壞情況的時(shí)間下界為：

Ω(nlogn)

12/3/20234.5快速分類(lèi)任何一個(gè)基于比較來(lái)確定兩個(gè)元素相對(duì)位置的排序算法需要Ω(nlogn)計(jì)算時(shí)間。如果我們能設(shè)計(jì)一個(gè)需要O(n1ogn)時(shí)間的排序算法，則在漸近的意義上，這個(gè)排序算法就是最優(yōu)的。許多排序算法都是追求這個(gè)目標(biāo)。下面介紹快速排序算法，它在平均情況下需要O(nlogn)時(shí)間。這個(gè)算法是由C.A.R.Hoare發(fā)明的。1.問(wèn)題描述分類(lèi)問(wèn)題2.劃分快速分類(lèi)是一種基于劃分的分類(lèi)方法；

劃分：選取待分類(lèi)集合A中的某個(gè)元素t，按照與t的大小關(guān)系重新整理A中元素，使得整理后的序列中所有在t以前出現(xiàn)的元素均小于等于t，而所有出現(xiàn)在t以后的元素均大于等于t。這一元素的整理過(guò)程稱(chēng)為劃分（Partitioning）。元素t稱(chēng)為劃分元素。

快速分類(lèi)：通過(guò)反復(fù)地對(duì)待排序集合進(jìn)行劃分達(dá)到分類(lèi)目的的分類(lèi)算法。12/3/2023劃分過(guò)程（PARTITION）的算法描述算法4.12用A(m)劃分集合A(m:p-1)procedurePARTITION(m,p)integerm,p,i;globalA(m:p-1)v←A(m);i←m//A(m)是劃分元素//looploopi←i+1untilA(i)≥vrepeat//i由左向右移//loopp←p-1untilA(p)≤vrepeat//p由右向左移//ifi<pthencallINTERCHANGE(A(i),A(p))elseexitendifrepeatA(m)←A(p)；A(p)←v//劃分元素在位置p//endPARTITION12/3/2023注：算法對(duì)集合A(m:p-1)進(jìn)行劃分。并使用待劃分區(qū)間的第一個(gè)元素A(m)作為劃分元素A(p)不在劃分區(qū)間內(nèi)，但被定義，且A(p）≥A(m)，用于限界12/3/2023例2.5劃分實(shí)例(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)ipA:657075808560555045+∞29

|……|A:654575808560555070+∞38

|…………|A:654550808560557570+∞47

|………………|A:6545505585

60807570+∞56

|……|A:654550556085807570+∞65

|……|A:604550556585807570+∞劃分元素定位于此交換劃分元素12/3/2023經(jīng)過(guò)一次“劃分”后，實(shí)現(xiàn)了對(duì)集合元素的調(diào)整：其中一個(gè)子集合的所有元素均小于等于另外一個(gè)子集合的所有元素。按同樣的策略對(duì)兩個(gè)子集合進(jìn)行分類(lèi)處理。當(dāng)子集合分類(lèi)完畢后，整個(gè)集合的分類(lèi)也完成了。這一過(guò)程避免了子集合的歸并操作。這一分類(lèi)過(guò)程稱(chēng)為快速分類(lèi)。12/3/20233.快速分類(lèi)通過(guò)反復(fù)使用劃分過(guò)程PARTITION實(shí)現(xiàn)對(duì)集合元素分類(lèi)的算法。算法4.13快速分類(lèi)procedureQUICKSORT(p,q)//將數(shù)組A(1:n)中的元素A(p),…A(q)按遞增的方式分類(lèi)。A(n+1)有定義，且假定A(n+1)←+∞//integerp,q;globaln,A(1:n)ifp<qthen

j←q+1

//進(jìn)入時(shí)，A(j)定義了劃分區(qū)間[p,q]的上界，初次調(diào)用時(shí)j=n+1callPARTITION(p,j)//出口時(shí)，j帶出此次劃分后劃分元素所在的坐標(biāo)位置//callQUICKSORT(p,j-1)//前一子集合上遞歸調(diào)用callQUICKSORT(j+1,q)//后一子集合上遞歸調(diào)用endifendQUICKSORT12/3/20234.快速分類(lèi)分析統(tǒng)計(jì)的對(duì)象：元素的比較次數(shù)，記為：C(n)兩點(diǎn)假設(shè)

①參加分類(lèi)的n個(gè)元素各不相同

②PARTITION中的劃分元素v是隨機(jī)選取的（針對(duì)平均情況的分析）隨機(jī)選取劃分元素：在劃分區(qū)間[m,p]隨機(jī)生成某一坐標(biāo)：i←RANDOM(m,p-1)；調(diào)換A(m)與A(i):v←A(i);A(i)←A(m);i←m作用：將隨機(jī)指定的劃分元素的值依舊調(diào)換到A(m)位置。之后，算法主體不變，仍從A(m)開(kāi)始執(zhí)行劃分操作。12/3/2023遞歸層次QuickSort(1,n)QuickSort(1,j1-1)QuickSort(j1+1,n)QuickSort(1,j21-1)QuickSort(j21+1,j1-1)QuickSort(j1-1,j22-1)QuickSort(j22+1,n)n個(gè)元素參加劃分和分類(lèi)去掉1個(gè)第一級(jí)的劃分元素n-1個(gè)元素參加劃分和分類(lèi)去掉2個(gè)第二級(jí)的劃分元素n-3個(gè)元素參加劃分和分類(lèi)去掉4個(gè)第三級(jí)的劃分元素第一層第二層第三層設(shè)在任一級(jí)遞歸調(diào)用上，調(diào)用PARTITION處理的所有元素總數(shù)為r，則，初始時(shí)r=n，以后的每級(jí)遞歸上，由于刪去了上一級(jí)的劃分元素，故r比上一級(jí)至少少1：理想情況，第一級(jí)少1，第二級(jí)少2，第三級(jí)少4，…；最壞情況，每次僅減少1（如集合元素已經(jīng)按照遞增或遞減順序排列）12/3/2023最壞情況分析記最壞情況下的元素比較次數(shù)是Cw(n)；PARTITION一次調(diào)用中的元素比較數(shù)是p-m+1，故每級(jí)遞歸調(diào)用上，元素的比較次數(shù)等于該級(jí)所處理的待分類(lèi)元素?cái)?shù)。

最壞情況下，每級(jí)遞歸調(diào)用的元素總數(shù)僅比上一級(jí)少1，故Cw(n)是r由n到2的累加和。即：Cw(n)==Ο(n2)12/3/2023平均情況分析

平均情況是指集合中的元素以任一一種順序排列，且任選所有可能的元素作為劃分元素進(jìn)行劃分和分類(lèi)，在這些所有可能的情況下，算法執(zhí)行性能的平均值。設(shè)調(diào)用PARTITION(m,p)時(shí)，所選取劃分元素v恰好是A(m:p-1)中的第i小元素（1≤i≤p-m）的概率相等。則經(jīng)過(guò)一次劃分，所留下的待分類(lèi)的兩個(gè)子文件恰好是A(m:j-1)和A(j+1:p-1)的概率是：1/(p-m),m≤j<p。則有，

其中，n+1是PARTITION第一次調(diào)用時(shí)所需的元素比較次數(shù)。CA(0)=CA(1)=0

12/3/2023化簡(jiǎn)上式可得：CA(n)/(n+1)=CA(n-2)/(n-1)+2/n+2/(n+1)=CA(n-3)/(n-2)+2/(n-1)+2/n+2/(n+1)…=CA(1)/2+由于所以得，CA(n)<2(n+1)loge(n+1)=Ο(nlogn)12/3/20235.快速分類(lèi)算法的迭代模型消去遞歸（略）6.快速分類(lèi)與歸并分類(lèi)比較兩者平均情況時(shí)間都是Ο(nlogn），平均情況下哪種快一些？實(shí)驗(yàn)證明快速分類(lèi)要快一些12/3/20234.6選擇問(wèn)題1.問(wèn)題描述給出含有n個(gè)元素表A(1:n)，要求確定其中的第k小元素。2.設(shè)計(jì)思路利用PARTITION過(guò)程。如果劃分元素v測(cè)定在A(j)的位置上，則有j-1個(gè)元素小于或等于A(j)，且有n-j個(gè)元素大于或等于A(j)。此時(shí)，若k=j，則A(j)即是第k小元素；否則，若k<j，則第k小元素將出現(xiàn)在A(1:j-1)中；若k>j，則第k小元素將出現(xiàn)在A(j+1:n)中。12/3/2023舉例在四人中找第二高（即第三矮）吳宗憲，曾志偉，古天樂(lè)，周潤(rùn)發(fā)12/3/20233.利用PARTITION實(shí)現(xiàn)的選擇算法算法描述算法4.15找第k小元素procedureSELECT(A,n,k)//在數(shù)組A(1:n)中找第k小元素，并將之放在A(k)中。//integern,k,m,r,j; m←1;r←n+1;A(n+1)←+∞

//A(n+1)被定義，并置為一大值，用于限界//loop//在進(jìn)入循環(huán)時(shí)，1≤m≤k≤r≤n+1//j←r//將剩余元素的最大下標(biāo)加1后置給j//callPARTITION(m，j)//返回j,它使得A(j)是第j小的值//case:k=j:return:k<j:r←j//j是新的上界//:else:m←j+1//k>j,j+1是新的下界//endcaserepeatendSELECT12/3/2023算法分析兩點(diǎn)假設(shè)①A中的元素互異②隨機(jī)選取劃分元素，且選擇A中任一元素作為劃分元素的概率相同分析每次調(diào)用PARTITION（m,j),所需的元素比較次數(shù)是

Ο(j-m+1)。在執(zhí)行一次PARTITION后，或者找到第k小元素，或者將在縮小的子集(A(m,k-1)或A(k+1,j))中繼續(xù)查找?？s小的子集的元素?cái)?shù)將至少比上一次劃分的元素?cái)?shù)少1。12/3/20231)最壞情況SELECT的最壞情況時(shí)間是Ο(n2)

當(dāng)A中的元素已經(jīng)按照遞增的順序排列，且k=n。此時(shí)，需要n次調(diào)用PARTITION過(guò)程，且每次返回的元素位置是子集中的第一個(gè)元素，子集合的元素?cái)?shù)一次僅減少１，而j值不變。則,n次調(diào)用的時(shí)間總量是12/3/20232)平均情況

設(shè)是找A(1:n)中第k小元素的平均時(shí)間。是SELECT的平均計(jì)算時(shí)間，則有并定義則有：T(n)≤R(n)。12/3/2023定理4.4SELECT的平均計(jì)算時(shí)間TA(n)是Ο(n)（對(duì)比快速分類(lèi)平均計(jì)算時(shí)間Ο(nlogn)）證明：PARTITION和SELECT中，case語(yǔ)句的執(zhí)行時(shí)間是Ο(n)。在隨機(jī)等概率選擇劃分元素時(shí)，首次調(diào)用PARTITION中劃分元素v剛好是A中第i小元素的概率為1/n，1≤i≤n。則，存在正常數(shù)c，c>0,有，n≥2且有，n≥2

12/3/2023令c≥R(1)。利用數(shù)學(xué)歸納法證明，對(duì)所有n≥2，有R(n)≤4cn.①當(dāng)n=2時(shí)，由上式得：②假設(shè)對(duì)所有得n,2≤n<m，有R(n)≤4cn③當(dāng)n=m時(shí)，有，由于R(n)是n的非降函數(shù)，故在當(dāng)m為偶數(shù)而k=m/2，或當(dāng)m為奇數(shù)而k=(m+1)/2時(shí)，取得極大值。因此，

若m為偶數(shù)，則

若m為奇數(shù)，則由于TA(n)≤R(n)，所以TA(n)≤4cn。故，TA(n)=Ο(n)12/3/20234.最壞情況是Ο(n)的選擇算法1）采用兩次取中間值的規(guī)則精心選取劃分元素首先，將參加劃分的n個(gè)元素分成組，每組有r個(gè)元素(r≥1)。（多余的個(gè)元素忽略不計(jì)）然后，對(duì)這組每組的r個(gè)元素進(jìn)行分類(lèi)并找出其中間元素mi,1≤i≤，共得個(gè)中間值。之后，對(duì)這個(gè)中間值分類(lèi)，并找出其中間值mm。將mm作為劃分元素執(zhí)行劃分。2）算法描述12/3/2023算法4.16使用二次取中規(guī)則得選擇算法的說(shuō)明性描述procedureSELECT2(A,k,n)//在集合A中找第k小元素，使用兩次取中規(guī)則//①若n≤r，則采用插入法直接對(duì)A分類(lèi)并返回第k小元素②把A分成大小為r的個(gè)子集合，忽略多余的元素③設(shè)M={m1,m2,…m}是子集合的中間值集合④v←SELECT2(M,,)⑤j←PARTITION(A，v)

//v作為劃分元素，劃分后j等于劃分元素所在位置的下標(biāo)//⑥case:k=j:return(v):k<j:設(shè)S是A(1:j-1)中元素的集合return(SELECT2(S,k,j-1)):else:設(shè)R是A(j+1:n)中元素的集合return(SELECT2(R,k-j,n-j))endcaseendSELECT212/3/2023例：設(shè)n=35,r=7。分為n/r=5個(gè)元素組：B1，B2，B3，B4，B5；每組有7個(gè)元素。B1-B5按照各組的mi的非增次序排列。mm=mi的中間值，1≤i≤5由圖所示有：mm中間值小于等于mm的元素大于等于mm的元素非降次序B1B2B3B4B5按照mi的非降次序排列12/3/2023由于r個(gè)元素的中間值是第小元素。則，至少有個(gè)mi小于或等于mm；至少有個(gè)mi大于或等于mm。則，至少有個(gè)元素小于或等于（或大于或等于）mm。

當(dāng)r=5，則使用兩次取中間值規(guī)則來(lái)選擇v=mm，可推出，至少有個(gè)元素小于或等于選擇元素v。至多有個(gè)元素大于v。至多有0.7n+1.2個(gè)元素小于v。

故，這樣的v可近似平均地劃分A中的n個(gè)元素。12/3/20232)算法分析記T(n)是SELECT2所需的最壞情況時(shí)間對(duì)特定的r分析SELECT2:選取r=5。假定A中的元素各不相同，則有①若n≤r，則采用插入法直接對(duì)A分類(lèi)并返回第k小元素→Ο(1)②把A分成大小為r的個(gè)子集合，忽略多余的元素→Ο(n)③設(shè)M={m1,m2,…m}是子集合的中間值集合→Ο(n)④v←SELECT2(M,,)→T(n/5)⑤j←PARTITION(A，v)→Ο(n)⑥case→T(3n/4),n≥24:k=j:return(v):k<j:設(shè)S是A(1:j-1)中元素的集合;return(SELECT2(S,k,j-1)):else:設(shè)R是A(j+1:n)中元素的集合;return(SELECT2(R,k-j,n-j))endcaseendSELECT212/3/2023故有，cnn＜24,T(n)＝T(n/5)+T(3n/4)+cnn≥24用歸納法可證：T(n)≤20cn即，T(n)=Ο(n)12/3/2023當(dāng)A中的元素不盡相同步驟⑤經(jīng)PARTITION調(diào)用所產(chǎn)生的S和R兩個(gè)子集合中可能存在一些元素等于當(dāng)前的劃分元素v,可能導(dǎo)致|S|或|R|大于0.7n+1.2。此時(shí)上述處理作一下改進(jìn)：方法一：將A集合分成3個(gè)子集合U,S和R，其中U是有A中所有與v相同的元素組成，S是由A中所有比v小的元素組成，R則是A中所有比v大的元素組成。同時(shí)步驟⑥更改：case:|S|≥k:return(SELECT2(S,k,|S|):|S|+|U|≥k:return(v):else:return(SELECT2(R,k-|S|-|U|,|R|))endcase

從而保證|S|+|R|≤0.7n+1.2成立，故關(guān)于T(n)的分析仍然成立。

T(n)=Ο(n)12/3/2023方法二：選取其他的r值進(jìn)行計(jì)算特例：當(dāng)r=5,且A中的元素不盡相同。假設(shè)其中有0.7n+1.2個(gè)元素比v小而其余的元素都等于v的情況。則，經(jīng)過(guò)PARTITION，在這些等于v的元素中至多有一半可能在S中，故|S|≤0.7n+1.2+(0.3n-1.2)/2=0.85n+0.6同理，|R|≤0.85n+0.6可得，步驟④和⑥此時(shí)所處理的元素總數(shù)將是1.05n+0.6>n不再是線(xiàn)性關(guān)系。故有T(n)≠Ο(n)改進(jìn)：取r=9。經(jīng)計(jì)算可得，此時(shí)將有個(gè)元素小于或等于v，同時(shí)至少有同樣多的元素大于或等于v。則當(dāng)n≥90時(shí)，|S|和|R|都至多為基于上述分析，有新的遞推式：12/3/2023故有，c1nn＜90T(n)＝T(n/9)+T(63n/72)+c1nn≥90用歸納法可證：T(n)≤72c1n即，T(n)=Ο(n)12/3/2023SELECT2的實(shí)現(xiàn)算法中需要解決的兩個(gè)問(wèn)題如何確定子集合的中間值當(dāng)r較小時(shí)，采用INSERTIONSORT(A,i,j)直接對(duì)每組的r個(gè)元素分類(lèi)，在分類(lèi)好的序列中，中間元素即為當(dāng)前r個(gè)元素的中間值。如何保存

個(gè)子集合的中間值注：各組找到的中間元素值將存放數(shù)組A的前部

12/3/2023算法4.17SELECT2的SPARKS的描述procedureSEL(A,m,p,k)//返回一個(gè)i，使得i∈[m,p]，且A(i)是A(m:p)中第k小元素，r是一個(gè)全程變量，其取值為大于1的整數(shù)globalr;integern,i,jifp-m+1≤rthencallINSERTIONSORT(A,m,p);return(m+k-1);endifloopn←p-m+1//元素?cái)?shù)//fori←1todo//計(jì)算中間值//callINSERTIONSORT(A,m+(i-1)*r,m+i*r-1)//將中間值收集到A(m:p)的前部//callINTERCHANGE(A(m+i-1),A(m+(i-1)r+-1))repeatj←SEL(A,m,m+-1,)//mm//callINSERTIONSORT(A(m),A(j))//產(chǎn)生劃分元素//j←p+1callPARTITION(m,j)case:j-m+1=k:return(