算法設(shè)計(jì)與分析：第5章 分治法

第5章分治法

學(xué)習(xí)要點(diǎn)：掌握設(shè)計(jì)有效算法的分治策略。理解遞歸的概念，分析遞歸算法的時(shí)間復(fù)雜度。通過(guò)下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧 （1）求最大最小元； （2）二分搜索技術(shù)； （3）合并排序和快速排序； （4）Strassen矩陣乘法；章節(jié)內(nèi)容：5.1一般方法5.2求最大最小元5.3二分搜索5.4排序問(wèn)題5.6斯特拉森矩陣乘法5.1分治法的一般方法分治法——將一個(gè)復(fù)雜的問(wèn)題分解成若干個(gè)規(guī)模較小、相互獨(dú)立，但類(lèi)型相同的子問(wèn)題求解；然后再將各子問(wèn)題的解組合成原始問(wèn)題的一個(gè)完整答案，這樣的問(wèn)題求解策略就叫分治法。將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。分治算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)分治法的設(shè)計(jì)思想是:將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。分治法的適用條件

分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。分治法的適用條件

分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題；這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用。分治法的適用條件

分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題；利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；能否利用分治法完全取決于問(wèn)題是否具有這條特征。如果具備了前兩條特征，而不具備這一特征，則可以考慮貪心法或動(dòng)態(tài)規(guī)劃法。分治法的適用條件

分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題；利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。這條特征涉及到分治法的效率。如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。分治法求解很自然的導(dǎo)致一個(gè)遞歸算法！

遞歸的概念直接或間接地調(diào)用自身的算法稱(chēng)為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱(chēng)為遞歸函數(shù)。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類(lèi)型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。下面來(lái)看幾個(gè)實(shí)例例1階乘函數(shù)

階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。int

factLoop(intn){

int

k,f; k=1; f=1;

while(kn) {

int

f=f*k;

intk=k+1; } returnf;}int

factRec(intn){if(n==0) return1;else returnn*factRec(n-1);}例2Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱(chēng)為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地得到：intfib(intn){

if(n<=1)

return1;else

return

fib(n-1)+fib(n-2);}intfib(intn){ intf,f1,f2; if(n<=1) f=n; else { f1=fib(n-1);

f2=fib(n-2); f=f1+f2; } returnf;}fibn:3f1:1f2:1f:2fibn:0f1:f2:f:0fibn:1f1:f2:f:1fibn:2f1:1f2:0f:1fibn:1f1:f2:f:1creationis

inpreorder例3Hanoi塔問(wèn)題設(shè)a,b,c是3個(gè)塔座。開(kāi)始時(shí)，在塔座a上有一疊共n個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤(pán)移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤(pán)；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤(pán)移至a,b,c中任一塔座上。在問(wèn)題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來(lái)解決這個(gè)問(wèn)題:voidhanoi(intn,inta,intb,intc){

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}T(1)=1T(n)=2T(n-1)+1T(n)=2T(n-1)+12T(n-1)=4T(n-2)+24T(n-2)=8T(n-3)+4…….2n-2T(2)=2n-1T(1)+2n-2T(n)=2n-1遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3、通過(guò)變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。遞歸小結(jié)分治法的算法框架程序5-1：分治法算法框架SolutionTypeDandC(ProblemTypeP){ProblemTypeP1,P2,...,Pk;if(Small(P))returnS(P);//解決小規(guī)模的問(wèn)題

else{ Divide(P,P1,P2,...,Pk);//將問(wèn)題分解成子問(wèn)題P1,P2,...,Pk ReturnCombine(DandC(P1),DandC(P2),...,DandC(Pk));

//遞歸的解各子問(wèn)題,并將各子問(wèn)題的解合并為原問(wèn)題的解

}}人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。即:將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題的處理方法是行之有效的。這種使子問(wèn)題規(guī)模大致相等的做法是出自一種平衡(balancing)子問(wèn)題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。一分為二的分治法算法框架程序5-2：一分為二的分治法算法框架SolutionTypeDandC(intleft,intright){ if(Small(left,right))returnS(left,right); //解決小規(guī)模的問(wèn)題

else{ intm=Divide(left,right);

//以m為界，將問(wèn)題分解成兩個(gè)子問(wèn)題

ReturnCombine(DandC(left,m),DandC(m+1,right));

//分別遞歸求解子問(wèn)題,并將子問(wèn)題的解合并為原問(wèn)題的解

}}分治法的復(fù)雜性分析一個(gè)分治法將規(guī)模為n的問(wèn)題分成a個(gè)規(guī)模為n／b的子問(wèn)題去解。設(shè)：S求解規(guī)模為1的問(wèn)題，需要耗費(fèi)常數(shù)單位時(shí)間c。再設(shè)：進(jìn)行問(wèn)題分解及將a個(gè)子問(wèn)題的解合并得到原始問(wèn)題的解需用f(n)個(gè)單位時(shí)間的工作量。則當(dāng)f(n)=cnk時(shí)，用T(n)表示該分治法解規(guī)模為|P|=n的問(wèn)題所需的計(jì)算時(shí)間有：令n=bm（即m=logbn），通過(guò)迭代法可求得方程的解：（5-1)

設(shè)a,b,c和k為常數(shù)，T(n)=aT(n/b)+cnk，T(1)=c，則令r=bk/a，分（r<1,r=1,r>1）三種情況討論，得到（定理5-1）：（5-2）注意：遞歸方程及其解只給出n等于b的方冪時(shí)T(n)的值，但是如果認(rèn)為T(mén)(n)足夠平滑，那么由n等于b的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)bi≤n<bi+1時(shí)，T(bi)≤T(n)<T(bi+1)。如果一個(gè)算法的時(shí)間可以表示為式（5-1）那樣的遞推式，便可以應(yīng)用定理5-1得到算法的漸近時(shí)間復(fù)雜度。本章算法的數(shù)據(jù)結(jié)構(gòu)除最后一小節(jié)外，本章算法都在可排序表（sortablelist）上實(shí)現(xiàn)?？膳判虮怼涗洠ㄔ兀┑年P(guān)鍵字可以比較大小的線性表。本章采用順序存儲(chǔ)（而不是鏈接存儲(chǔ)）的可排序表類(lèi)作為算法處理的數(shù)據(jù)結(jié)構(gòu)。可排序表中元素類(lèi)型為結(jié)構(gòu)類(lèi)型，元素值之間的比較指元素關(guān)鍵字值間的比較。

在互不相同的n個(gè)數(shù){x1,x2,…,xn}中，找出最大和最小的數(shù)。方法一：分別求最大值和最小值 分別需要n-1次和n-2次元素間的比較，共2n-3次。方法二：同時(shí)求最大元和最小元（程序5-4）

if(n==0)return; max=min=l[0]; for(inti=1;i<n;i++){ if(l[i]>max)max=l[i]; if(l[i]<min)min=l[i]; }此算法最好、最壞、平均情況下都需要2n-2次元素比較。5.2求最大最小元方法二（改進(jìn)）：只有當(dāng)l[i]>max為假時(shí)才比較l[i]<min if(n==0)return; max=min=l[0]; for(inti=1;i<n;i++){ if(l[i]>max)max=l[i];

else if(l[i]<min)min=l[i]; }

算法執(zhí)行的最好情況發(fā)生在表遞增有序時(shí)，需比較n-1次；

最壞情況發(fā)生在表遞減有序時(shí)，需比較2(n-1)次。方法三：用分治法來(lái)解決，將原問(wèn)題分解為大小基本相等的兩個(gè)子問(wèn)題，直到子問(wèn)題中只有一個(gè)或兩個(gè)元素可以直接求得最大、最小元；如果已經(jīng)求得子表中的最大、最小元，則原表的最大元是兩子表的最大元中較大的一個(gè)，原表的最小元是兩子表的最小元中較小的一個(gè)。遞歸過(guò)程為：（程序5-5）voidSortableList::MaxMin(inti,intj,T&max,T&min)const{Tmax1,min1;if(i==j)max=min=l[i]; //表中只有一個(gè)元素

else if(i==j-1) //表中只有兩個(gè)元素

if(l[i]<l[j]){max=l[j];min=l[i];} else {max=l[i];min=l[j];} else{ //表中有多個(gè)元素

intm=(i+j)/2; //對(duì)半分割

MaxMin(i,m,max,min); MaxMin(m+1,j,max1,min1); if(max<max1)max=max1; //兩子表最大元合并

if(min>min1)min=min1; //兩子表最小元合并

}}正確性容易用歸納法證明（P77）。分析用分治法求最大最小元的時(shí)間復(fù)雜度：設(shè)T（n）表示元素個(gè)數(shù)為n時(shí)的總比較次數(shù)，則

T（1）=0 //算法不需要進(jìn)行元素間的比較

T（2）=1 //算法只需進(jìn)行一次元素比較（n>2）

//算法兩次遞歸調(diào)用自身，分別在長(zhǎng)度為和的子表中求最大元和最小元算法兩次遞歸調(diào)用自身，所需時(shí)間分別為T(mén)()和T()，另外合并時(shí)還需要進(jìn)行2次額外比較。不難得到下列遞推式：當(dāng)n=2k時(shí)，由迭代計(jì)算得到：T(n)=3n/2-2迭代計(jì)算過(guò)程請(qǐng)大家完成！分治法求最大最小元的算法最好、最壞、平均情況下都需要3n/2-2次比較。由于是遞歸算法，雖然比較次數(shù)減少了，但未必省時(shí)。方法四：其實(shí)，此問(wèn)題也不一定要用遞歸算法來(lái)解決:可將數(shù)據(jù)分成兩個(gè)一組的n/2組，第一組比較一次，令大的為xmax，小的為xmin;以后各組比較三次，先兩個(gè)數(shù)據(jù)比較，其中大者再與xmax比，小者再與xmin比;總比較次數(shù)也恰為。采用分治法求解，在已按關(guān)鍵字值非減排序的有序表中，搜索給定元素的問(wèn)題。分析：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問(wèn)題滿足分治法的第一個(gè)適用條件。5.3二分搜索該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。分析：比較x和a的中間元素a[mid]。若x=a[mid]，則x在L中的位置就是mid；如果x<a[mid]，由于a是遞增排序的，因此假如x在a中的話，x必然排在a[mid]的前面，所以我們只要在a[mid]的前面查找x即可；如果x>a[mid]，同理我們只要在a[mid]的后面查找x即可。無(wú)論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過(guò)是查找的規(guī)?？s小了。5.3二分搜索采用分治法求解，在已按關(guān)鍵字值非減排序的有序表中，搜索給定元素的問(wèn)題。分析：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。分析：很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在a[mid]的前面或后面查找x是獨(dú)立的子問(wèn)題，因此滿足分治法的第四個(gè)適用條件。5.3二分搜索采用分治法求解，在已按關(guān)鍵字值非減排序的有序表中，搜索給定元素的問(wèn)題。分析：要在按關(guān)鍵字值非減排序的長(zhǎng)度為n的有序表（a0,a1,…,an-1)

中找出與特定元素x有相同關(guān)鍵字值的元素。搜索結(jié)果可以返回整個(gè)數(shù)據(jù)元素，也可以指示該元素在表中的位置。若表中元素的個(gè)數(shù)n=0，顯然搜索失敗；若n>0，則可將有序表分解為若干個(gè)子表（最簡(jiǎn)單的分解為兩個(gè)子表，即為有序表的二分搜索。）假設(shè)元素am為分割點(diǎn)。am與x比較的結(jié)果有三種可能：1）x<am，關(guān)鍵字值與x相同的元素必在子表(a0,a1,...,am-1)中；2）x=am，搜索成功；3）x>am，關(guān)鍵字值與x相同的元素必在子表(am+1,am+2,...,an-1)中。程序5-6分治法搜索有序表的二分搜索算法框架：template<classT>intSortableList<T>:BSearch(constT&x,intleft,intright)const{if(left<=right){ intm=Divide(left,right);//Devide函數(shù)按某種規(guī)則求分割點(diǎn)m if(x<l[m])returnBSearch(x,left,m-1); //搜索左邊子表

elseif(x>l[m])returnBSearch(x,m+1,right); //搜索右邊子表

elsereturnm; //搜索成功

}return-1; //搜索失敗}使用不同的規(guī)則求分割點(diǎn)m，則可得到不同的二分搜索方法，如：對(duì)半搜索、菲波那契搜索等。程序5-7對(duì)半搜索遞歸算法：template<classT>intSortableList<T>:BSearch(constT&x,intleft,intright)const{if(left<=right){ intm=(left+right)/2; //對(duì)半分割：m=(left+right)/2 if(x<l[m])returnBSearch(x,left,m-1); //搜索左半子表

elseif(x>l[m])returnBSearch(x,m+1,right); //搜索右半子表

elsereturnm; }return-1; }對(duì)半搜索算法將表劃分成幾乎相等大小的兩個(gè)子表。（容易用數(shù)學(xué)歸納法證明其正確性）程序的遞歸調(diào)用語(yǔ)句是最后一句可執(zhí)行語(yǔ)句，與上下文無(wú)關(guān)，此為尾遞歸。因此可以轉(zhuǎn)化為迭代函數(shù)。程序5-8對(duì)半搜索迭代算法：template<classT>intSortableList<T>:BSearch(constT&x)const{intm,left=0,right=n-1;while(left<=right){

m=(left+right)/2; //對(duì)半分割

if(x<l[m])right=m-1; //搜索左半子表

elseif(x>l[m])left=m+1; //搜索右半子表

elsereturnm; //搜索成功

}return-1; //搜索失敗}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn)次。每次循環(huán)，循環(huán)體內(nèi)運(yùn)算需要常數(shù)時(shí)間O(1)。因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn)。遞歸函數(shù)往往效率較低，因此將程序5-7轉(zhuǎn)換為迭代算法實(shí)現(xiàn)。二叉判定樹(shù)

二分搜索算法的執(zhí)行過(guò)程可以用一棵二叉判定樹(shù)來(lái)描述：指定元素x與表中元素l[m]之間的一次比較操作，表現(xiàn)為二叉判定樹(shù)中的一個(gè)圓形結(jié)點(diǎn)（內(nèi)結(jié)點(diǎn)），用m標(biāo)識(shí)。 如果x=l[m],則算法在該結(jié)點(diǎn)處成功終止.二叉判定樹(shù)的根結(jié)點(diǎn)，代表算法中首次與x比較的元素l[m]，用m標(biāo)識(shí)。當(dāng)x<l[m]時(shí)，x隨后與結(jié)點(diǎn)m的左孩子比較；當(dāng)x>l[m]時(shí)，x隨后與結(jié)點(diǎn)m的右孩子比較。若x<l[m]且算法終止，那么結(jié)點(diǎn)m的左孩子以標(biāo)號(hào)m-1的方形結(jié)點(diǎn)表示；若x>l[m]且算法終止，那么結(jié)點(diǎn)m的右孩子以標(biāo)號(hào)為m的方形結(jié)點(diǎn)（外結(jié)點(diǎn)）表示。從根結(jié)點(diǎn)到每個(gè)內(nèi)結(jié)點(diǎn)的一條路徑代表成功搜索的一條比較路徑。如果搜索成功，則算法在內(nèi)結(jié)點(diǎn)處終止；否則算法在外結(jié)點(diǎn)處終止。4170258369-10123456789舉例：對(duì)長(zhǎng)度為10的有序表執(zhí)行對(duì)半搜索的二叉判定樹(shù)：若算法在方形結(jié)點(diǎn)m處終止，則：當(dāng)0≤m<n-1時(shí)，l[m]<x<l[m+1]；當(dāng)m=-1時(shí)，x<l[0]；當(dāng)m=n-1時(shí)，x>l[n-1]。都意味著搜索失敗。二叉判定樹(shù)的性質(zhì)——由性質(zhì)5-4和性質(zhì)5-2可引出定理5-4和定理5-5。性質(zhì)5-4：若n=2h-1，則對(duì)半搜索二叉判定樹(shù)的外結(jié)點(diǎn)均在h+1層上；否則，在第h或h+1層上。（h=） 性質(zhì)5-3：若n=2h-1，則對(duì)半搜索二叉判定樹(shù)是滿二叉樹(shù)。 性質(zhì)5-2：具有n(n>0)個(gè)內(nèi)結(jié)點(diǎn)的二叉判定樹(shù)的高度為（不計(jì)外結(jié)點(diǎn)）。（有序表）對(duì)半搜索二叉判定樹(shù)的性質(zhì)：性質(zhì)5-1：具有n(n>0)個(gè)內(nèi)結(jié)點(diǎn)的對(duì)半搜索二叉判定樹(shù)的左子樹(shù)上有個(gè)內(nèi)結(jié)點(diǎn)，右子樹(shù)上有個(gè)內(nèi)結(jié)點(diǎn)。定理5-5：對(duì)半搜索算法在搜索成功時(shí)的平均時(shí)間復(fù)雜度為Θ(logn)。定理5-4：對(duì)半搜索算法在成功搜索的情況下，關(guān)鍵字值之間的比較次數(shù)不超過(guò)。對(duì)于不成功的搜索，算法需要進(jìn)行或次比較。從對(duì)半搜索二叉判定樹(shù)上可以看到，對(duì)半搜索所需的關(guān)鍵字值的比較次數(shù)不會(huì)超過(guò)判定樹(shù)的高度。（不計(jì)失敗節(jié)點(diǎn)）定理5-6：在一個(gè)有n個(gè)元素的集合中，通過(guò)關(guān)鍵字值之間的比較，搜索指定關(guān)鍵字值的元素，任意這樣的算法在最壞情況下至少需要進(jìn)行次比較。一個(gè)基于關(guān)鍵字比較的搜索算法可以用一個(gè)二叉判定樹(shù)來(lái)描述,樹(shù)上至少有n個(gè)結(jié)點(diǎn)，該二叉判定樹(shù)的樹(shù)高至少是（不計(jì)外結(jié)點(diǎn)）。（由二叉樹(shù)性質(zhì)可知，高度為h的二叉樹(shù)上至多有2h-1個(gè)結(jié)點(diǎn)，有n≤2h-1，h≥）則：次關(guān)鍵字值間的比較，是這類(lèi)搜索算法在最壞情況下的時(shí)間下界。因此：對(duì)半搜索是最優(yōu)算法。練習(xí)：折半插入排序(BinaryInsertsort)基本思想：

設(shè)在順序表中有一個(gè)對(duì)象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已經(jīng)排好序的對(duì)象。在插入V[i]時(shí),利用對(duì)半搜索尋找V[i]的插入位置。 請(qǐng)實(shí)現(xiàn)該算法voidBInsSort(TV[],intn)

，并分析其時(shí)間復(fù)雜度和穩(wěn)定性。typedefintT;voidBInsSort(TV[],intn){Ttemp;intLeft,Right;

for(inti=1;i<n;i++){ Left=0;Right=i-1;temp=V[i];

while(Left<=Right){ //對(duì)半搜索

intmid=(Left+Right)/2; if(temp<V[mid]) Right=mid-1; else Left=mid+1; } for(intk=i-1;k>=Left;k--)V[k+1]=V[k];//記錄后移

V[Left]=temp;//插入

}}折半插入排序所需的比較次數(shù)與待排序?qū)ο蟮某跏寂帕袩o(wú)關(guān),僅依賴(lài)于待排序?qū)ο蟮膫€(gè)數(shù)。（在插入第i個(gè)對(duì)象時(shí),需要經(jīng)過(guò)

log2i

+1次比較,才能確定它應(yīng)插入的位置。）因此,折半插入排序的比較次數(shù)為：證明過(guò)程參見(jiàn)“堆排序”比較操作：由于折半搜索在平均情況和最壞情況下比順序搜索查找快，因此折半插入排序的平均性能和最壞情況比直接插入排序要快；但比其最好情況要差。（在對(duì)象的初始排列已經(jīng)按排序碼排好序或接近有序時(shí),直接插入排序比折半插入排序執(zhí)行的排序碼比較次數(shù)要少。）折半插入排序是一個(gè)穩(wěn)定的排序方法。移動(dòng)操作：折半插入排序的對(duì)象移動(dòng)次數(shù)與直接插入排序相同,依賴(lài)于對(duì)象的初始排列。最壞情況和平均情況下均為O(n2)。5.4排序問(wèn)題分治法求解排序問(wèn)題思想：按某種方式將序列分成兩個(gè)或多個(gè)子序列，分別進(jìn)行排序，再將已排序的子序列合并成一個(gè)有序序列。合并排序和快速排序是兩種典型的符合分治策略的排序算法。合并排序合并排序：把兩個(gè)或多個(gè)有序序列合并成一個(gè)有序序列。最基本的合并排序算法——兩路合并排序。兩路合并排序：把兩個(gè)有序序列合并成一個(gè)有序序列。兩路合并排序

使用分治法的兩路合并排序算法：將待排序的元素序列一分為二，得到長(zhǎng)度基本相等的兩個(gè)子序列，分別排序。如果子序列較長(zhǎng)，還可繼續(xù)細(xì)分，直到子序列的長(zhǎng)度不超過(guò)1為止。 當(dāng)分解所得的子序列已排列有序時(shí)，將兩個(gè)有序子序列合并成一個(gè)有序子序列，得到原問(wèn)題的解。

合并方法： 比較兩序列中的最小值，輸出其中較小者，然后重復(fù)此過(guò)程，直到其中一個(gè)隊(duì)列為空時(shí)，如果另一個(gè)隊(duì)列還有元素沒(méi)有輸出，則將剩余元素依次輸出。 （見(jiàn)P83圖5-2）程序5-10兩路合并排序算法（MergeSort函數(shù)）voidMergeSort(intleft,intright){ if(left<right){ //序列長(zhǎng)度大于1時(shí)，進(jìn)一步劃分

intmid=(left+right)/2; //一分為二

MergeSort(left,mid); //對(duì)左子序列元素排序

MergeSort(mid+1,right); //對(duì)右子序列元素排序

Merge(left,mid,right);

//將已排好序的左、右子序列合并成一個(gè)有序序列}voidMergeSort(){ MergeSort(0,n-1); }兩路合并排序算法MergeSort將一個(gè)序列分解成兩個(gè)長(zhǎng)度幾乎相等的子序列，對(duì)它們分別排序，然后調(diào)用Merge函數(shù)將兩個(gè)有序子序列合并成一個(gè)有序序列，完成合并排序。程序5-9兩路合并排序算法（Merge函數(shù)）voidMerge(intleft,intmid,intright){T*temp=newT[right-left+1];

intk=0; //k為數(shù)組temp中當(dāng)前位置

inti=left, j=mid+1;//i為左子序列當(dāng)前位置；j為右子序列當(dāng)前位置

while((i<=mid)&&(j<=right)) if(l[i]<=l[j]) temp[k++]=l[i++]; else temp[k++]=l[j++];while(i<=mid)temp[k++]=l[i++];while(j<=right)temp[k++]=l[j++];for(i=0,k=left;k<=right;)l[k++]=temp[i++];

//從temp中重新寫(xiě)回序列l(wèi)中}若某子序列中還有元素沒(méi)有輸出，則依次輸出剩余元素Merge函數(shù)負(fù)責(zé)將兩個(gè)有序子序列(l[left],...l[mid])和(l[mid+1],...,l[right])合并成一個(gè)有序序列。合并過(guò)程中需要用到一個(gè)臨時(shí)數(shù)組temp[]，用來(lái)暫存合并結(jié)果。合并結(jié)束后再將合并得到的有序序列重新復(fù)制到(l[left],...,l[right])中。兩路合并排序遞歸算法（例） 0 1 2 3 4 5 6 [35 40 72 49 39 80 49] [35 40 72 49] [39 80 49] [35 40] [72 49] [39 80] [49] [35] [40] [72] [49] [39] [80]兩路合并排序遞歸算法（例） 0 1 2 3 4 5 6 [35 40 72 49 39 80 49] [35 40 72 49] [39 80 49] [35 40] [72 49] [39 80] [49] [35] [40] [72] [49] [39] [80]兩路合并排序遞歸算法（例） 0 1 2 3 4 5 6 [35 40 72 49 39 80 49] [35 40 72 49] [39 80 49] [35 40] [49 72] [39 80] [49] [35] [40] [72] [49] [39] [80]兩路合并排序遞歸算法（例） 0 1 2 3 4 5 6 [35 40 72 49 39 80 49] [35 40 49 72] [39 80 49] [35 40] [49 72] [39 80] [49] [35] [40] [72] [49] [39] [80]兩路合并排序遞歸算法（例） 0 1 2 3 4 5 6 [35 40 72 49 39 80 49] [35 40 49 72] [39 80 49] [35 40] [49 72] [39 80] [49] [35] [40] [72] [49] [39] [80]兩路合并排序遞歸算法（例） 0 1 2 3 4 5 6 [35 40 72 49 39 80 49] [35 40 49 72] [39 80 49] [35 40] [49 72] [39 80] [49] [35] [40] [72] [49] [39] [80]兩路合并排序遞歸算法（例） 0 1 2 3 4 5 6 [35 40 72 49 39 80 49] [35 40 49 72] [39 49 80] [35 40] [49 72] [39 80] [49] [35] [40] [72] [49] [39] [80]兩路合并排序遞歸算法（例） 0 1 2 3 4 5 6 [35 39 40 49 49 72 80] [35 40 49 72] [39 49 80] [35 40] [49 72] [39 80] [49] [35] [40] [72] [49] [39] [80]算法mergeSort的遞歸過(guò)程可以消去。初始序列[35][40][72][49][39][80][49][3540][4972][3980][49]第一步第二步[35404972][394980]第三步[35394049497280]

兩路合并排序（MergeSort）實(shí)際就是先將n個(gè)數(shù)據(jù)看成n個(gè)長(zhǎng)度為l的表，將相鄰的表成對(duì)合并，得到長(zhǎng)度為2的n/2個(gè)有序表；進(jìn)一步再將相鄰表成對(duì)合并，得到長(zhǎng)度為4的n/4個(gè)有序表；……；如此重復(fù)做下去，直至所有數(shù)據(jù)均合并到一個(gè)長(zhǎng)度為n的有序表為止，即完成排序。上述每一次的合并過(guò)程稱(chēng)為一趟〔Pass），整個(gè)排序過(guò)程就是兩路合并排序。Merge函數(shù)將長(zhǎng)度之和為n的兩個(gè)有序子序列合并成一個(gè)有序序列，執(zhí)行過(guò)程中最多需進(jìn)行n-1次關(guān)鍵字值間的比較，其時(shí)間復(fù)雜度為O(n)。兩路合并算法時(shí)間復(fù)雜度分析請(qǐng)寫(xiě)出合并排序遞歸算法MergeSort的時(shí)間復(fù)雜度遞歸函數(shù)？Merge函數(shù)將長(zhǎng)度之和為n的兩個(gè)有序子序列合并成一個(gè)有序序列，執(zhí)行過(guò)程中最多需進(jìn)行n-1次關(guān)鍵字值間的比較，其時(shí)間復(fù)雜度為O(n)。由此可得到合并排序遞歸算法MergeSort的時(shí)間復(fù)雜度遞歸函數(shù)：由定理5-1，或通過(guò)迭代計(jì)算，均可得到兩路合并排序的時(shí)間復(fù)雜度為T(mén)(n)=O(nlogn)

。兩路合并算法時(shí)間復(fù)雜度分析兩路合并算法空間復(fù)雜度分析兩路合并排序一般需要一個(gè)與原序列相同長(zhǎng)度的輔助數(shù)組temp，因此它所需的額外空間為O(n)。兩路合并排序最好時(shí)間復(fù)雜度：O(nlogn)最壞時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)快速排序快速排序（又稱(chēng)分劃交換排序）：在待排序的序列（k0,k1,...,kn-1）中選擇一個(gè)元素作為分劃元素，也稱(chēng)為主元。以主元為軸心，對(duì)原序列重新排列，分成左右兩個(gè)子序列，使主元左側(cè)子序列中所有元素都不大于主元，主元右側(cè)子序列中所有元素都不小于主元，這樣的分解過(guò)程稱(chēng)為一趟分劃。原序列被分成三部分：主元和左、右兩個(gè)子序列(Kp(0),Kp(1),...Kp(j-1))Kp(j)(Kp(j+1),Kp(j+2),Kp(n-1))通過(guò)分劃操作，原序列的排序問(wèn)題被分解成了兩個(gè)性質(zhì)相同、相互獨(dú)立的子問(wèn)題，分別對(duì)兩個(gè)子序列進(jìn)行排序。當(dāng)子序列為空序列或只有一個(gè)元素的序列時(shí)，無(wú)須進(jìn)行任何處理，它們自然是有序的。程序5-12快速排序算法（排序函數(shù)—QuickSort

）voidQuickSort(intleft,intright){ if(left<right){ //當(dāng)序列長(zhǎng)度>1時(shí)，用Partition函數(shù)分割

intj=Partition(left,right); //對(duì)序列進(jìn)行分劃操作

QuickSort(left,j-1); //對(duì)左子序列進(jìn)行快速排序

QuickSort(j+1,right); //對(duì)右子序列進(jìn)行快速排序

}}分劃操作Partition是快速排序的核心。分劃操作中最簡(jiǎn)單的選擇主元的方法：選擇序列的第一個(gè)元素。程序5-11快速排序算法（分劃函數(shù)—Partition）intPartition(intleft,intright){ //調(diào)用本函數(shù)的前置條件：left<right；主元為第一個(gè)元素l[left]

。

inti=left,j=right+1; do{ doi++;while(l[i]<l[left]); //從l[left+1]開(kāi)始比較

//i右移，直到遇到一個(gè)不小于主元的元素停止

doj--;while(l[j]>l[left]); //從l[right]開(kāi)始比較

//j左移，直到遇到一個(gè)不大于主元的元素停止

if(i<j)Swap(i,j); //交換l[i]和l[j]兩個(gè)元素

}while(i<j); //只要i仍小于j Swap(left,j);

//最后將主元l[left]與l[j]交換，結(jié)束一趟分劃操作

returnj; //返回當(dāng)前主元的位置}初始序列{72,26,57,88,42,80,72,48,60,∞}{72,26,57,88,42,80,72,48,60,∞}i++;j--;{72,26,57,60,42,48,72,80,88,∞}Swap(left,j)完成{72,26,57,60,42,48}72{80,88,∞}{72,26,57,88,42,80,72,48,60,∞}Swap(i,j){72,26,57,60,42,80,72,48,88,∞}i++;j--;{72,26,57,60,42,80,72,48,88,∞}Swap(i,j){72,26,57,60,42,48,72,80,88,∞}i++;j--;{72,26,57,60,42,48,72,80,88,∞}不滿足i<j時(shí)退出循環(huán)例：一趟分劃過(guò)程算法在待排序序列的尾部設(shè)置一個(gè)大值∞作為哨兵，是為了防止指針i在右移的過(guò)程中移出序列之外而無(wú)法終止。（如：初始序列為遞減次序排列時(shí)）思考：為什么排序序列左側(cè)不用設(shè)置哨兵？若當(dāng)前進(jìn)行分劃操作的初始序列中元素個(gè)數(shù)為n，則：每趟分劃操作中，主元和表中元素的比較不超過(guò)n+1次。完整的快速排序過(guò)程示例：

見(jiàn)P88表5-1快速排序算法時(shí)間復(fù)雜度分析顯然，當(dāng)序列中沒(méi)有元素或只有1個(gè)元素的時(shí)候，所需的排序時(shí)間為常數(shù)Θ(1)。每次分劃操作中，主元和表中關(guān)鍵字值的比較不超過(guò)n+1次。最好情況下：如果每次分劃中，主元都恰好是序列（子序列）的中值，分劃得到左右兩個(gè)幾乎相等的子序列，則快速排序的效率最高。遞推公式為：B(n)=2B(n/2)+Θ(n)由定理5-1可得遞推式的解為：B(n)=Θ(nlogn)快速排序算法時(shí)間復(fù)雜度分析顯然，當(dāng)序列中沒(méi)有元素或只有1個(gè)元素的時(shí)候，所需的排序時(shí)間為常數(shù)Θ(1)。每次分劃操作中，主元和表中關(guān)鍵字值的比較不超過(guò)n+1次。最壞情況下：如果每次劃分操作產(chǎn)生的兩個(gè)子序列，其中之一為空序列，則快速排序效率最低。（若總是選擇左邊第一個(gè)元素為主元，則快速排序的最壞情況發(fā)生在原始序列正向有序或反向有序時(shí)）遞推公式為：w(n) ≤w(n-1)+n+1≤W(1)+(n+1)+...+3 遞推式的解為：W(n)=O(n2)快速排序算法時(shí)間復(fù)雜度分析顯然，當(dāng)序列中沒(méi)有元素或只有1個(gè)元素的時(shí)候，所需的排序時(shí)間為常數(shù)Θ(1)。每次分劃操作中，主元和表中關(guān)鍵字值的比較不超過(guò)n+1次。平均情況下：假定序列中n個(gè)元素的各種可能排列是等概率的，則主元在序列中的大小次序是隨機(jī)的。因此在（當(dāng)前）一趟分劃操作后，它位于下標(biāo)[0,n-1]的任何位置的可能性是相等的。這意味著序列中任何一個(gè)元素為主元的概率是1/n。分劃操作將序列分成三部分，設(shè)左、右兩個(gè)子序列分別包括k個(gè)和n-k-1個(gè)元素，則對(duì)這兩個(gè)子序列分別執(zhí)行快速排序所需的平均時(shí)間分別為A(k)和A(n-k-1)。得遞推公式：

A(n)=遞推式的解為：

A(n)<2(n+1)ln(n+1)=O(nlogn)快速排序算法空間復(fù)雜度分析最壞情況下，程序所需的系統(tǒng)棧調(diào)用深度，最大為O(n)。如果希望減少使用的?？臻g，可以每次分劃后在棧中保存較大子序列的上、下界，而對(duì)較小的子序列先進(jìn)行排序。這樣可使所需的?？臻g大小降為O(logn)。最好時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nlogn)最壞時(shí)間復(fù)雜度：O(n2)輔助空間：O(n)或O(logn)快速排序1、改進(jìn)主元的選擇方法

快速排序算法的性能取決于劃分的對(duì)稱(chēng)性。通過(guò)修改算法Partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法RandomizedPartition。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在(l[left],...,l[right])中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱(chēng)的。intRandomizedPartition(intleft,intright){inti=Random(left,right);

Swap(i,left);returnPartition(left,right);

//再調(diào)用Partition函數(shù)}改善快速排序算法性能的方法改善快速排序算法性能的方法2、當(dāng)待排序的子序列長(zhǎng)度小于一定值時(shí)，快速排序的速度反而不如一些簡(jiǎn)單的排序算法（如：直接插入法）。 因此對(duì)長(zhǎng)度很小的子序列，可以不再繼續(xù)分劃，而使用直接插入法進(jìn)行排序。3、遞歸算法的效率常常不如相應(yīng)的非遞歸算法。為提高速度，可使用非遞歸的快速排序（如使用堆棧代替系統(tǒng)棧）來(lái)取代原來(lái)的遞歸算法。合并排序VS快速排序

問(wèn)題分解過(guò)程：合并排序——將序列一分為二即可。（十分簡(jiǎn)單）快速排序——需調(diào)用Partition函數(shù)將一個(gè)序列劃分為子序列。（分解方法相對(duì)較困難） 子問(wèn)題解合并得到原問(wèn)題解的過(guò)程：合并排序——需要調(diào)用Merge函數(shù)來(lái)實(shí)現(xiàn)。（Merge函數(shù)時(shí)間復(fù)雜度為O(n)）快速排序——一旦左、右兩個(gè)子序列都已分別排序，整個(gè)序列便自然成為有序序列。（異常簡(jiǎn)單，幾乎無(wú)須額外的工作，省去了從子問(wèn)題解合并得到原問(wèn)題解的過(guò)程）

構(gòu)造排序問(wèn)題二叉判定樹(shù)：(由搜索算法二叉判定樹(shù)稍作修改)兩個(gè)元素間的一次比較用一個(gè)內(nèi)結(jié)點(diǎn)表示，并用進(jìn)行比較的兩元素下標(biāo)“i：j”標(biāo)識(shí)；算法在外結(jié)點(diǎn)終止。從根到每個(gè)外結(jié)點(diǎn)的一條路徑代表一種可能的輸入序列的排序結(jié)果，因此該二叉判定樹(shù)上至少有n!個(gè)外結(jié)點(diǎn)。（參見(jiàn)圖5-5）排序算法的時(shí)間下界證明：對(duì)n個(gè)元素排序最壞情況下所需比較次數(shù)取決于二叉樹(shù)高度。1）二叉樹(shù)性質(zhì)：任意一棵二叉樹(shù)上，葉結(jié)點(diǎn)的個(gè)數(shù)比度為2的結(jié)點(diǎn)個(gè)數(shù)多一個(gè)。因此該二叉判定樹(shù)至少有n!-1個(gè)內(nèi)結(jié)點(diǎn)；3）二叉樹(shù)性質(zhì)：包含N個(gè)元素的二叉樹(shù)高度至少為。因此不計(jì)外結(jié)點(diǎn)，二叉樹(shù)高度至少為。

n≥4時(shí)，

得證。定理5-7：任何一個(gè)通過(guò)關(guān)鍵字值比較對(duì)n個(gè)元素進(jìn)行排序的算法，最壞情況下，至少要做(n/4)logn次比較。排序算法的時(shí)間下界表5-2 基于比較關(guān)鍵字值的排序算法的時(shí)間復(fù)雜度:排序算法最好情況平均情況最壞情況直接插入排序O(n)O(n2)O(n2)簡(jiǎn)單選擇排序O(n2)O(n2)O(n2)冒泡排序O(n)O(n2)O(n2)快速排序O(nlogn)O(nlogn)O(n2)兩路合并排序O(nlogn)O(nlogn)O(nlogn)堆排序O(nlogn)O(nlogn)O(nlogn)最優(yōu)算法思考題如何選出n個(gè)元素中第k小的元素？（模擬快速排序算法設(shè)計(jì)）每一步根據(jù)一個(gè)隨機(jī)選取的元素對(duì)輸入數(shù)組進(jìn)行遞歸劃分，只對(duì)含有第k小元素的那部分子數(shù)組進(jìn)行遞歸操作——尋找x[k]位置的所有者。template<classType>TypeRandomizedSelect(Typea[],intp,intr,intk){//在數(shù)組a中下標(biāo)從p到r的范圍內(nèi)查找第k小的元素

if(p==r)returna[p]; //a[p]即是第k小的元素

inti=RandomizedPartition(a,p,r);

//快速排序的一趟分劃操作

j=i-p+1;//前面子數(shù)組中（包括位置i處）元素總數(shù)

if(k<=j)

returnRandomizedSelect(a,p,i,k); else returnRandomizedSelect(a,i+1,r,k-j);}最壞情況下，算法RandomizedSelect()需要Ω(n2)計(jì)算時(shí)間。如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的兩個(gè)子數(shù)組的長(zhǎng)度都至少為原數(shù)組長(zhǎng)度的ε倍（0<ε<1是某個(gè)正常數(shù)），那么在最壞情況下用O(n)線性時(shí)間就可以完成選擇任務(wù)。（詳見(jiàn)王曉東《計(jì)算機(jī)算法設(shè)計(jì)與分析》——線性時(shí)間選擇。）例如：若ε=9/10，則最壞情況下，算法所需的計(jì)算時(shí)間T(n)滿足遞歸式T(n)≤T(9n/10)+O(n)，由此得T(n)=O(n)。補(bǔ)充：堆排序

堆排序（Heapsort,1964年RobertW.Floyd和J.Williams共同設(shè)計(jì)，1978年RobertW.Floyd獲圖靈獎(jiǎng)）是利用二叉樹(shù)的一種排序方法。

堆(Heap)也譯為堆或堆壘,是與二叉排序樹(shù)不同的一種二叉樹(shù)，它的定義為：一個(gè)完全二叉樹(shù)(完全二叉樹(shù)：各層都是滿的，只是最下面一層從右邊起連續(xù)缺幾個(gè)結(jié)點(diǎn))，它的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于原始數(shù)據(jù)的一個(gè)元素，且規(guī)定：如果一個(gè)結(jié)點(diǎn)有子結(jié)點(diǎn)，此結(jié)點(diǎn)數(shù)據(jù)必須大于或等于其子結(jié)點(diǎn)的數(shù)據(jù)。 由此可見(jiàn)，堆是完全二叉樹(shù)，且規(guī)定了父結(jié)點(diǎn)和子結(jié)點(diǎn)數(shù)據(jù)之間必須滿足的條件。

由于堆陣是完全二叉樹(shù)，采用將結(jié)點(diǎn)順序編號(hào)存于一維數(shù)組中的表示法較鏈接表示法節(jié)省存儲(chǔ)也便于運(yùn)算。設(shè)某堆的結(jié)點(diǎn)數(shù)共有n個(gè)，順序?qū)⑺鼈兇嫒胍痪S數(shù)組K中，下標(biāo)從1到n。根據(jù)順序表示二叉樹(shù)的特點(diǎn)，除下標(biāo)為1的結(jié)點(diǎn)是整個(gè)樹(shù)的根結(jié)點(diǎn)而沒(méi)有父結(jié)點(diǎn)以外，其余下標(biāo)為j的結(jié)點(diǎn)（2≤j≤n）都有父結(jié)點(diǎn)，父結(jié)點(diǎn)的下標(biāo)為i=。 故堆陣的條件可以表示成:

K[i]≥K[j]

當(dāng)2≤j≤n和i=

由堆的定義可知，其根結(jié)點(diǎn)（即在數(shù)組中下標(biāo)為1的結(jié)點(diǎn)）具有最大的數(shù)值，堆陣排序就是利用這一特點(diǎn)進(jìn)行的。堆陣排序過(guò)程分為構(gòu)成堆和利用它來(lái)排序兩個(gè)階段，下面分別進(jìn)行介紹?？梢圆捎脙煞N方法構(gòu)成堆陣：

第一種方法是從根結(jié)點(diǎn)起逐個(gè)插入結(jié)點(diǎn)，在插入結(jié)點(diǎn)過(guò)程中進(jìn)行父子結(jié)點(diǎn)數(shù)據(jù)比較和必要的互換調(diào)整，使之總滿足堆的條件；

第二種方法則是先把所有數(shù)據(jù)按任意次序置入完全二叉樹(shù)的各結(jié)點(diǎn)中，然后由下而上逐層進(jìn)行父子結(jié)點(diǎn)數(shù)據(jù)比較，進(jìn)行必要的互換調(diào)整，直至使其最后完全滿足堆的條件，數(shù)據(jù)的比較調(diào)整可以使用“篩”運(yùn)算進(jìn)行。構(gòu)成堆陣的過(guò)程

“篩”運(yùn)算從最末尾結(jié)點(diǎn)（下標(biāo)為n）的父結(jié)點(diǎn)（下標(biāo)為）開(kāi)始，向前逐結(jié)點(diǎn)進(jìn)行，直至篩完根結(jié)點(diǎn)即形成此堆陣。篩每個(gè)結(jié)點(diǎn)時(shí)，將其數(shù)值與其兩個(gè)子結(jié)點(diǎn)中數(shù)值較大者進(jìn)行比較，如小于該子結(jié)點(diǎn)數(shù)值，則與之進(jìn)行互換，互換后又將它看成父結(jié)點(diǎn)，再與下一層的子結(jié)點(diǎn)進(jìn)行比較，如此做下去，直至不小于其子結(jié)點(diǎn)的數(shù)值或已篩到端結(jié)點(diǎn)而不再有子結(jié)點(diǎn)了，此數(shù)據(jù)的“篩”運(yùn)算即完成。

由于在一個(gè)堆中根結(jié)點(diǎn)數(shù)據(jù)總是所有數(shù)據(jù)中之最大者，利用堆陣排序的方法是從根結(jié)點(diǎn)逐個(gè)取出數(shù)據(jù)，每次將新的元素再提到根結(jié)點(diǎn)，如此反復(fù)進(jìn)行。為了節(jié)約存儲(chǔ)，要求排序得到的有序數(shù)據(jù)序列仍存放于原數(shù)組中，故將從根結(jié)點(diǎn)取出的數(shù)據(jù)由數(shù)組的末端起逐單元存放。每存放一個(gè)數(shù)據(jù)，同時(shí)將原在該單元的數(shù)據(jù)換到根結(jié)點(diǎn)，但這樣互換后一般會(huì)破壞堆的條件，為此，需對(duì)根結(jié)點(diǎn)再做一次篩運(yùn)算，就又可形成新的滿足條件的堆。隨著數(shù)組末端存放的由堆中取出的數(shù)據(jù)越來(lái)越多，堆的結(jié)點(diǎn)數(shù)逐漸減少，當(dāng)?shù)饺〕隽?n-1)個(gè)數(shù)據(jù)，堆陣只剩下一個(gè)根結(jié)點(diǎn)，此最后一個(gè)數(shù)據(jù)一定是全部數(shù)據(jù)中的最小者，堆陣排序過(guò)程即全部結(jié)束。利用堆陣排序

堆陣排序分為建立堆陣和利用堆陣排序兩大步驟。設(shè)堆陣有r個(gè)滿層，元素個(gè)數(shù)n=2r-1。

最壞的情況假設(shè)每個(gè)元素都需要從原來(lái)位置“篩”到堆陣的最底層，僅原來(lái)在最底層的不必篩，這樣一來(lái)最上層的一個(gè)元素要下降r-1層；第二層的兩個(gè)元素要下降r-2層；……；中間第i層2(i-1)個(gè)元素要下降r-i層；……；下面倒數(shù)第二層，也即第r-1層的2(r-2)個(gè)元素下降一層。每篩下一層要進(jìn)行兩次比較（先左右兩子節(jié)點(diǎn)相比，然后此元素與其中較大者比）。因此在最壞的情況下，為了建立堆陣所需要的比較次數(shù)為：時(shí)間復(fù)雜性分析

上式中共有(r-1)項(xiàng)，第一項(xiàng)包括(r-1)個(gè)1，第二項(xiàng)包括(r-2)個(gè)2，第三項(xiàng)包括(r-3)個(gè)22，......，最后一項(xiàng)是1個(gè)2r-2。將它們重新組合后可得下式：

下面看利用堆陣排序所需要的比較次數(shù)。 排序時(shí)由后向前順次將元素與根結(jié)點(diǎn)對(duì)換，并將換到根結(jié)點(diǎn)的元素篩到合適的位置處。如果逐個(gè)進(jìn)行，堆陣越來(lái)越小，直至排序完畢。設(shè)在某一步堆陣有i個(gè)元素，其深度為，最壞情況將根元素篩到堆陣最下層需要比較次為。 故最壞情況排序過(guò)程的總比較次數(shù)為：因：當(dāng)n恰為2的整數(shù)次方時(shí)：例如：n=16時(shí)，上式為（1*2+2*4+3*8）當(dāng)n不恰為2的整數(shù)次方時(shí)，則后面幾項(xiàng)是：例如：n=19時(shí)，比n=16多出3項(xiàng)，每項(xiàng)值為因此幾項(xiàng)的總值得排序總的比較次數(shù)為：又因其中：故排序總的比較次數(shù)為：建立堆陣所需的比較次數(shù)：2n利用堆陣排序所需的比較次數(shù)：2nlogn因此堆陣排序最壞情況時(shí)間復(fù)雜度為O(nlogn)。此排序算法是“就地”進(jìn)行運(yùn)算，所占空間比較節(jié)省。

希爾排序方法又稱(chēng)為縮小增量排序?；舅枷耄涸O(shè)待排序?qū)ο笮蛄杏衝個(gè)對(duì)象,首先取一個(gè)整數(shù)gap<n作為間隔,將全部對(duì)象分為

gap個(gè)子序列,所有距離為gap的對(duì)象放在同一個(gè)子序列中,在每一個(gè)子序列中分別施行直接插入排序。然后縮小間隔gap,例如取gap=

gap/2

，重復(fù)上述的子序列劃分和排序工作。直到最后取

gap==1,將所有對(duì)象放在同一個(gè)序列中排序?yàn)橹?。補(bǔ)充：希爾排序(ShellSort)Gap=30123452108254925*160123452108254925*16Gap=22108254925*162108254925*16Gap=12108254925*162108254925*16希爾排序過(guò)程：typedefintSortData;voidShellSort(SortDataV[],intn){SortDatatemp;intgap=n/2;//gap是間隔

while(gap!=0) //循環(huán),直到gap為零

{for(inti=gap;i<n;i+=gap){temp=V[i]; //直接插入排序

for(intj=i;j>=gap;j=j-gap)if(temp<V[j-gap])V[j]=V[j-gap];elsebreak; V[j]=temp;}

gap=(int)(gap/2);}}

希爾排序的算法：開(kāi)始時(shí)gap的值較大,子序列中的對(duì)象較少,排序速度較快;隨著排序進(jìn)展,gap值逐漸變小,子序列中對(duì)象個(gè)數(shù)逐漸變多,由于前面大多數(shù)對(duì)象已基本有序,所以排序速度仍然很快。Gap的取法有多種。shell提出取gap=

n/2

，gap=

gap/2

，直到gap=1。對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算排序碼的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。希爾排序所需的比較次數(shù)和移動(dòng)次數(shù)約為n1.3， 當(dāng)n趨于無(wú)窮時(shí)可減少到n(log2n)2。補(bǔ)充：計(jì)數(shù)排序計(jì)數(shù)排序假設(shè)n個(gè)輸入元素中的每一個(gè)都是介于0到k之間的整數(shù)。此處k為某個(gè)整數(shù)，當(dāng)k=O(n)時(shí)，計(jì)數(shù)排序的運(yùn)行時(shí)間為Θ(n)。基本思想：對(duì)每一個(gè)輸入元素x，確定出小于x的元素個(gè)數(shù)，從而可以把x直接放到它在最終輸出數(shù)組中的位置上。例如：若有17個(gè)元素小于x，則x將位于第18個(gè)輸出位置上。（但是當(dāng)有幾個(gè)元素相同時(shí)，方案要略作修改，相同元素不能放在同一個(gè)輸出位置上）輸入：數(shù)組A[1...n] length[A]=n存放排序結(jié)果：數(shù)組B[1...n]提供臨時(shí)存儲(chǔ)區(qū)：數(shù)組C[0...k]Counting-Sort(A,B,k)fori←0tok doC[i]←0forj←1tolength[A] doC[A[j]]←C[A[j]]+1 //c[i]包含等于i的元素個(gè)數(shù)

fori←1tok doC[i]←c[i]+c[i-1] //c[i]包含小于或等于i的元素個(gè)數(shù)

forj←length[A]downto1 do B[C[A[j]]]←A[j] //排好序的輸出數(shù)組B C[A[j]]←C[A[j]]-1 //更新數(shù)組C中的值7Counting-Sort(A,B,k)fori←0tok doC[i]←0forj←1tolength[A] doC[A[j]]←C[A[j]]+1fori←1tok doC[i]←c[i]+c[i-1]forj←length[A]downto1 do B[C[A[j]]]←A[j] C[A[j]]←C[A[j]]-1 2023C0101234525302303A123456782247C78012345B12345678224C78012345362Counting-Sort(A,B,k)fori←0tok doC[i]←0forj←1tolength[A] doC[A[j]]←C[A[j]]+1fori←1tok doC[i]←c[i]+c[i-1]forj←length[A]downto1 do B[C[A[j]]]←A[j] C[A[j]]←C[A[j]]-1 25302303A123456782246C78012345B1234567824C7801234536016Counting-Sort(A,B,k)fori←0tok doC[i]←0forj←1tolength[A] doC[A[j]]←C[A[j]]+1fori←1tok doC[i]←c[i]+c[i-1]forj←length[A]downto1 do B[C[A[j]]]←A[j] C[A[j]]←C[A[j]]-1 25302303A123456781246C78012345B1234567824C7801234530135計(jì)數(shù)排序是穩(wěn)定的！Counting-Sort(A,B,k)fori←0tok doC[i]←0forj←1tolength[A] doC[A[j]]←C[A[j]]+1fori←1tok doC[i]←c[i]+c[i-1]forj←length[A]downto1 do B[C[A[j]]]←A[j] C[A[j]]←C[A[j]]-1 02235B12345678303Θ(k)Θ(n)Θ(k)Θ(n)總時(shí)間：Θ(n+k)因此實(shí)踐中，當(dāng)k=O(n)時(shí)，我們常常采用計(jì)數(shù)排序，其運(yùn)行時(shí)間為Θ(n)。計(jì)數(shù)排序的時(shí)間下界優(yōu)于（定理5-7中證明的，如表5-2）基于比較關(guān)鍵字值的排序算法時(shí)間下界Θ(nlogn)，為什么？因?yàn)橛?jì)數(shù)排序不是一個(gè)比較排序算法！事實(shí)上，其代碼中根本就不出現(xiàn)輸入元素之間的比較。相反，計(jì)數(shù)排序是用了輸入元素的實(shí)際值來(lái)確定它們?cè)跀?shù)組中的位置。當(dāng)我們采用的不是比較排序模型時(shí)，排序算法的下界Θ(nlogn)就不適用了。補(bǔ)充：基數(shù)排序

基數(shù)排序（radixsort）是一種用在老式穿卡機(jī)上的算法。一張卡片有80列，每一列可以在12個(gè)位置中的任一處穿孔。對(duì)于十進(jìn)制數(shù)字來(lái)說(shuō)，每列中只能用到10個(gè)位置。（另兩個(gè)位置用于編碼非數(shù)值字符）。一個(gè)d位數(shù)占用d個(gè)列。因?yàn)榭ㄆ判蚱饕淮沃荒懿榭匆粋€(gè)列，因此，要對(duì)n張卡片上的d位數(shù)進(jìn)行排序，就需要用到排序算法?；鶖?shù)排序還可用來(lái)對(duì)有多個(gè)關(guān)鍵字域的記錄排序。

與人們的直覺(jué)相反，基數(shù)排序是首先按最低有效位數(shù)字進(jìn)行排序。329457657839436720355720355436457657329839720329436839355457657329355436457657720839基數(shù)排序算法很重要的一點(diǎn)就是：按位排序要穩(wěn)定！常采用計(jì)數(shù)排序算法作為子過(guò)程。但計(jì)數(shù)排序不是原地排序，消耗內(nèi)存比較多。給定n個(gè)d位數(shù)，每一個(gè)數(shù)位可以取k種可能的值。如果所用的穩(wěn)定按位排序算法需要Θ(n+k)的時(shí)間，則基數(shù)排序算法能以Θ(d(n+k))的時(shí)間正確的對(duì)這些數(shù)進(jìn)行排序。Radix-Sort(A,d)

for

i←1tod

douseastablesorttosortarrayAondigiti補(bǔ)充：