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

第5章分治法

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

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

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

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

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

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

階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(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ù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個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塔問題設(shè)a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個問題: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)點：結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來實現(xiàn)遞歸函數(shù)。3、通過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。遞歸小結(jié)分治法的算法框架程序5-1：分治法算法框架SolutionTypeDandC(ProblemTypeP){ProblemTypeP1,P2,...,Pk;if(Small(P))returnS(P);//解決小規(guī)模的問題

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

//遞歸的解各子問題,并將各子問題的解合并為原問題的解

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

else{ intm=Divide(left,right);

//以m為界，將問題分解成兩個子問題

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

//分別遞歸求解子問題,并將子問題的解合并為原問題的解

}}分治法的復(fù)雜性分析一個分治法將規(guī)模為n的問題分成a個規(guī)模為n／b的子問題去解。設(shè)：S求解規(guī)模為1的問題，需要耗費常數(shù)單位時間c。再設(shè)：進(jìn)行問題分解及將a個子問題的解合并得到原始問題的解需用f(n)個單位時間的工作量。則當(dāng)f(n)=cnk時，用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間有：令n=bm（即m=logbn），通過迭代法可求得方程的解：（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的方冪時T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于b的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)bi≤n<bi+1時，T(bi)≤T(n)<T(bi+1)。如果一個算法的時間可以表示為式（5-1）那樣的遞推式，便可以應(yīng)用定理5-1得到算法的漸近時間復(fù)雜度。本章算法的數(shù)據(jù)結(jié)構(gòu)除最后一小節(jié)外，本章算法都在可排序表（sortablelist）上實現(xiàn)。可排序表——記錄（元素）的關(guān)鍵字可以比較大小的線性表。本章采用順序存儲（而不是鏈接存儲）的可排序表類作為算法處理的數(shù)據(jù)結(jié)構(gòu)?？膳判虮碇性仡愋蜑榻Y(jié)構(gòu)類型，元素值之間的比較指元素關(guān)鍵字值間的比較。

在互不相同的n個數(shù){x1,x2,…,xn}中，找出最大和最小的數(shù)。方法一：分別求最大值和最小值 分別需要n-1次和n-2次元素間的比較，共2n-3次。方法二：同時求最大元和最小元（程序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為假時才比較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ā)生在表遞增有序時，需比較n-1次；

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

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

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

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

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

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

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

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

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

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

中找出與特定元素x有相同關(guān)鍵字值的元素。搜索結(jié)果可以返回整個數(shù)據(jù)元素，也可以指示該元素在表中的位置。若表中元素的個數(shù)n=0，顯然搜索失??；若n>0，則可將有序表分解為若干個子表（最簡單的分解為兩個子表，即為有序表的二分搜索。）假設(shè)元素am為分割點。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ī)則求分割點m if(x<l[m])returnBSearch(x,left,m-1); //搜索左邊子表

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

elsereturnm; //搜索成功

}return-1; //搜索失敗}使用不同的規(guī)則求分割點m，則可得到不同的二分搜索方法，如：對半搜索、菲波那契搜索等。程序5-7對半搜索遞歸算法：template<classT>intSortableList<T>:BSearch(constT&x,intleft,intright)const{if(left<=right){ intm=(left+right)/2; //對半分割：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; }對半搜索算法將表劃分成幾乎相等大小的兩個子表。（容易用數(shù)學(xué)歸納法證明其正確性）程序的遞歸調(diào)用語句是最后一句可執(zhí)行語句，與上下文無關(guān)，此為尾遞歸。因此可以轉(zhuǎn)化為迭代函數(shù)。程序5-8對半搜索迭代算法：template<classT>intSortableList<T>:BSearch(constT&x)const{intm,left=0,right=n-1;while(left<=right){

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

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)運算需要常數(shù)時間O(1)。因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn)。遞歸函數(shù)往往效率較低，因此將程序5-7轉(zhuǎn)換為迭代算法實現(xiàn)。二叉判定樹

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

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

，并分析其時間復(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){ //對半搜索

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關(guān),僅依賴于待排序?qū)ο蟮膫€數(shù)。（在插入第i個對象時,需要經(jīng)過

log2i

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

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

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

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

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

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

Merge(left,mid,right);

//將已排好序的左、右子序列合并成一個有序序列}voidMergeSort(){ MergeSort(0,n-1); }兩路合并排序算法MergeSort將一個序列分解成兩個長度幾乎相等的子序列，對它們分別排序，然后調(diào)用Merge函數(shù)將兩個有序子序列合并成一個有序序列，完成合并排序。程序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中重新寫回序列l(wèi)中}若某子序列中還有元素沒有輸出，則依次輸出剩余元素Merge函數(shù)負(fù)責(zé)將兩個有序子序列(l[left],...l[mid])和(l[mid+1],...,l[right])合并成一個有序序列。合并過程中需要用到一個臨時數(shù)組temp[]，用來暫存合并結(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的遞歸過程可以消去。初始序列[35][40][72][49][39][80][49][3540][4972][3980][49]第一步第二步[35404972][394980]第三步[35394049497280]

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

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

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

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

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

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

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

。

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

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

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

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

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

}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時退出循環(huán)例：一趟分劃過程算法在待排序序列的尾部設(shè)置一個大值∞作為哨兵，是為了防止指針i在右移的過程中移出序列之外而無法終止。（如：初始序列為遞減次序排列時）思考：為什么排序序列左側(cè)不用設(shè)置哨兵？若當(dāng)前進(jìn)行分劃操作的初始序列中元素個數(shù)為n，則：每趟分劃操作中，主元和表中元素的比較不超過n+1次。完整的快速排序過程示例：

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

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

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

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

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

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

n≥4時，

得證。定理5-7：任何一個通過關(guān)鍵字值比較對n個元素進(jìn)行排序的算法，最壞情況下，至少要做(n/4)logn次比較。排序算法的時間下界表5-2 基于比較關(guān)鍵字值的排序算法的時間復(fù)雜度:排序算法最好情況平均情況最壞情況直接插入排序O(n)O(n2)O(n2)簡單選擇排序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個元素中第k小的元素？（模擬快速排序算法設(shè)計）每一步根據(jù)一個隨機選取的元素對輸入數(shù)組進(jìn)行遞歸劃分，只對含有第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)計算時間。如果能在線性時間內(nèi)找到一個劃分基準(zhǔn)，使得按這個基準(zhǔn)所劃分出的兩個子數(shù)組的長度都至少為原數(shù)組長度的ε倍（0<ε<1是某個正常數(shù)），那么在最壞情況下用O(n)線性時間就可以完成選擇任務(wù)。（詳見王曉東《計算機算法設(shè)計與分析》——線性時間選擇。）例如：若ε=9/10，則最壞情況下，算法所需的計算時間T(n)滿足遞歸式T(n)≤T(9n/10)+O(n)，由此得T(n)=O(n)。補充：堆排序

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

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

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

K[i]≥K[j]

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

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

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

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

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

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

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

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

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

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

希爾排序方法又稱為縮小增量排序。基本思想：設(shè)待排序?qū)ο笮蛄杏衝個對象,首先取一個整數(shù)gap<n作為間隔,將全部對象分為

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

gap/2

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

gap==1,將所有對象放在同一個序列中排序為止。補充：希爾排序(ShellSort)Gap=30123452108254925*160123452108254925*16Gap=22108254925*162108254925*16Gap=12108254925*162108254925*16希爾排序過程：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);}}

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

n/2

，gap=

gap/2

，直到gap=1。對特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算排序碼的比較次數(shù)和對象移動次數(shù)。希爾排序所需的比較次數(shù)和移動次數(shù)約為n1.3， 當(dāng)n趨于無窮時可減少到n(log2n)2。補充：計數(shù)排序計數(shù)排序假設(shè)n個輸入元素中的每一個都是介于0到k之間的整數(shù)。此處k為某個整數(shù)，當(dāng)k=O(n)時，計數(shù)排序的運行時間為Θ(n)?；舅枷耄簩γ恳粋€輸入元素x，確定出小于x的元素個數(shù)，從而可以把x直接放到它在最終輸出數(shù)組中的位置上。例如：若有17個元素小于x，則x將位于第18個輸出位置上。（但是當(dāng)有幾個元素相同時，方案要略作修改，相同元素不能放在同一個輸出位置上）輸入：數(shù)組A[1...n] length[A]=n存放排序結(jié)果：數(shù)組B[1...n]提供臨時存儲區(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的元素個數(shù)

fori←1tok doC[i]←c[i]+c[i-1] //c[i]包含小于或等于i的元素個數(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計數(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)總時間：Θ(n+k)因此實踐中，當(dāng)k=O(n)時，我們常常采用計數(shù)排序，其運行時間為Θ(n)。計數(shù)排序的時間下界優(yōu)于（定理5-7中證明的，如表5-2）基于比較關(guān)鍵字值的排序算法時間下界Θ(nlogn)，為什么？因為計數(shù)排序不是一個比較排序算法！事實上，其代碼中根本就不出現(xiàn)輸入元素之間的比較。相反，計數(shù)排序是用了輸入元素的實際值來確定它們在數(shù)組中的位置。當(dāng)我們采用的不是比較排序模型時，排序算法的下界Θ(nlogn)就不適用了。補充：基數(shù)排序

基數(shù)排序（radixsort）是一種用在老式穿卡機上的算法。一張卡片有80列，每一列可以在12個位置中的任一處穿孔。對于十進(jìn)制數(shù)字來說，每列中只能用到10個位置。（另兩個位置用于編碼非數(shù)值字符）。一個d位數(shù)占用d個列。因為卡片排序器一次只能查看一個列，因此，要對n張卡片上的d位數(shù)進(jìn)行排序，就需要用到排序算法。基數(shù)排序還可用來對有多個關(guān)鍵字域的記錄排序。

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

for

i←1tod

douseastablesorttosortarrayAondigiti補充：