第2章分治策略

第2章分治策略本章主要知識點：2.1分治法的基本思想（DivideandConquer）2.2二分搜索技術2.3大整數(shù)的乘法2.4棋盤覆蓋2.5歸并排序2.6快速排序2.7尋找第k小元素2.8循環(huán)賽日程表計劃授課時間：4～6課時1第2章分治策略問題：有16枚硬幣，其中有一枚是偽造的，并且那枚偽造硬幣的重量和真硬幣的重量不同(假設比真幣輕)。你能不能用最少的比較次數(shù)找出這枚偽造的硬幣?提供一臺可用來比較兩組硬幣重量的儀器解決問題：1、兩兩比較2、硬幣分成兩組，一次比較兩組。一次比較后，可以舍棄完全是真幣的那一組，只對另一組進行下一步的比較。關鍵：將大問題分割成若干小問題，小問題與原有問題是完全類似的。分治法（“分而治之”）。分治法在設計查找、排序等算法時很有效，最常用的分治法有二分法、歸并法、快速排序等。22.1分治法的基本思想分治法的基本思想大問題分解為子問題，這些子問題互相獨立且與原問題相同。分別求解子問題。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。合并解，自底向上逐步求出原來問題的解。分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。32.1分治法的基本思想分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。）利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。42.1分治法的基本思想分治法的基本步驟divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解決小規(guī)模的問題dividePintosmallersubinstancesP1,P2,...,Pk；//分解問題for(i=1,i<=k,i++)

yi=divide-and-conquer(Pi);//遞歸的解各子問題returnmerge(y1,...,yk);//將各子問題的解合并為原問題的解}人們從大量實踐中發(fā)現(xiàn)，在用分治法設計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。52.1分治法的基本思想分治法的復雜性分析分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解。設分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有（右上）。通過迭代法求得方程解（右下）。注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當mi≤n<mi+1時，T(mi)≤T(n)<T(mi+1)。6補充：遞歸方程求解常用方法：代入法迭代法套用公式法差分方程法母函數(shù)法7補充：遞歸方程求解1、代入法先推測遞歸方程的顯式解，然后用數(shù)學歸納法證明這一推測的正確性。那么，顯式解的漸近階即為所求。例如：8補充：遞歸方程求解2、迭代法通過反復迭代，將遞歸方程的右端變換成一個級數(shù)，然后求級數(shù)的和，再估計和的漸近階。另外可畫遞歸樹。

9遞歸樹T(n)=T(n/3)+T(2n/3)+n

當我們累計遞歸樹各層的值時，得到每一層的和都等于n，從根到葉的最長路徑是先按橫向求出每層結(jié)點的值之和，并記錄在各相應層右端頂格處，然后從根到葉逐層地將頂格處的結(jié)果加起來便是我們要求的結(jié)果。10補充：遞歸方程求解3、套用公式法對于形如

T(n)=aT(n/b)+f(n)

的遞歸方程，給出三種情況下方程解的漸近階的三個相應估計公式供套用。11補充：遞歸方程求解3、套用公式法4、差分方程法有些遞歸方程可以看成一個差分方程，因而可以用解差分方程(初值問題)的方法來解遞歸方程5、母函數(shù)法122.2二分搜索技術給定已按升序排好序的n個元素a[1:n]，現(xiàn)要在這n個元素中找出一特定元素x。適用分治法求解問題的基本特征：該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個子問題是相互獨立的。很顯然此問題分解出的子問題相互獨立，即在a[i]的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。13二分檢索原理將二分檢索問題問題表示為：I=(n,a1,…,an,x)選取一個下標k，可得到三個子問題：I1=(k-1,a1,…,ak-1,x)I2=(1,ak

,x)I3=(n-k,ak+1,…,an,x)對所求解的問題（或子問題）所選的下標都是中間元素的下標，k=(n+1)/2」2.2二分搜索技術142.2二分搜索技術問題描述已知一個按非降次序排列的元素表a1,a2,…,an，判定某個給定元素x是否在該表中出現(xiàn)，若是，則找出該元素在表中的位置，并置于j，否則，置j為0。一般解決方法（從頭到尾查找一遍）a1a2a3a4…anx…成功和不成功最壞情況下需要O（n）次比較15二分搜索算法：publicstaticint

binarySearch(int[]a,intx,intn){//在a[0]<=a[1]<=...<=a[n-1]中搜索x//找到x時返回其在數(shù)組中的位置，否則返回-1intleft=0;intright=n-1;while(left<=right){

intmid=(left+right)/2;//

mid=low+((high-low)/2);

if(x==a[mid])returnmid;if(x>a[mid])left=mid+1;elseright=mid-1;}return-1;//未找到x}思考：二分搜索查找遞歸算法？2.2二分搜索技術16//初始left=0;right=N-1;publicstaticint

binarySearch(inta[],intx,intleft,intright){//找到x時返回其在數(shù)組中的位置，否則返回-1if(left>right)return-1;//未找到xelse{intmid=(left+right)/2;if(x==a[mid])returnmid;if(x>a[mid])returnbinarySearch(a,x,mid+1,right);elsereturnbinarySearch(a,x,left,mid);}}思考：二分搜索查找遞歸算法2.2二分搜索技術17二分檢索實例:設在A(0:8)中順序放了以下9個元素：檢索x=9,9==A[4],一次比較就成功,最好情況-15-6079235482101A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]①②③③④②③④檢索x=-15,-15<A[4],-15<A[1],-15==A[0],3次比較,成功檢索x=101,101>A[4],101>A[6],101>A[7],101==A[8],4次比較,成功檢索x=8,8<A[4],8>A[1],8>A[2],8>A[3],4次比較,不成功檢索2.2二分搜索技術18二分檢索算法所需的空間和時間所需空間:

用n個位置存放數(shù)組A，還有l(wèi)ow,high,mid,x,j五個變量需要存儲，共需空間n+5所需計算空間:

對于計算時間，需要分別考慮以下幾種情況：成功檢索的最好情況、平均情況、最壞情況不成功檢索的最好情況、平均情況、最壞情況2.2二分搜索技術19二分檢索的時間復雜度定理:若n在區(qū)域[2k-1,2k)中，則對于一次成功的檢索，二分檢索算法至多作k次比較。對前面二分檢索實例n=9,n∈[23,24),已分析過成功檢索和不成功檢索的各種情況下的比較次數(shù)≤4,易知:Θ(logn)Θ(logn)Θ(logn)Θ(logn)Θ(logn)Θ(1)不成功的檢索成功的檢索最壞情況平均情況最好情況計算時間202.3大整數(shù)的乘法設計一個有效的算法，可以進行兩個n位大整數(shù)的乘法運算小學的方法：O(n2)

效率太低分治法:X=A10n/2+BY=C10n/2+DXY=AC10n+(AD+BC)10n/2+BD復雜度分析

T(n)=O(n2)

沒有改進

n/2位n/2位n/2位n/2位X=Y=ABCD21算法改進為了降低時間復雜度，必須減少乘法的次數(shù)。為此，我們把XY寫成另外的形式：XY=AC10n+((A-C)(B-D)+AC+BD)10n/2+BD或XY=AC10n+((A+C)(B+D)-AC-BD)10n/2+BD復雜性：這兩個算式看起來更復雜一些，但它們僅需要3次n/2位乘法[AC、BD和(A±C)(B±D)]，于是

T(n)=O(nlog3)=O(n1.59)

較大的改進

細節(jié)問題：兩個XY的復雜度都是O(nlog3)，但考慮到A+C

,B+D可能得到m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第2種方案。22算法改進voidmain(){longx,y,a,b,c,d;doublez;

cout<<"Pleaseinputthetwonumberxandy:\n";

cin>>x>>y;a=x/(long)pow(10,num_len(x)/2);b=x%(long)pow(10,num_len(x)/2);c=y/(long)pow(10,num_len(y)/2);d=y%(long)pow(10,num_len(y)/2);//z=(double)(a*c*pow(10,num_len(x))+(a*d+b*c)*pow(10,num_len(x)/2)+b*d);z=(double)(a*c*(long)pow(10,num_len(x))+((a-c)*(b-d)+a*c+b*d)*(long)pow(10,num_len(x)/2)+b*d);

cout<<"theresultis"<<z;}23算法改進（續(xù)上頁）int

num_len(longz){intt=0;

while(z>0){z=z/10;t++;}returnt;}24更快的方法小學的方法：O(n2)——效率太低分治法:O(n1.59)——較大的改進更快的方法？如果將大整數(shù)分成更多段，用更復雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。最終的，這個思想導致了快速傅利葉變換(FastFourierTransform)的產(chǎn)生。該方法也可以看作是一個復雜的分治算法，對于大整數(shù)乘法，它能在O(nlogn)時間內(nèi)解決。是否能找到線性時間的算法？目前為止還沒有結(jié)果。252.4棋盤覆蓋在一個2k×2k個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。易知，覆蓋任意一個2k×2k的特殊棋盤，用到的骨牌數(shù)恰好為(2k×2k

-1)/3。262.4棋盤覆蓋分治策略算法描述當k>0時，將2k×2k棋盤分割為4個2k-1×2k-1

子棋盤如圖(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。將3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如圖(b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。272.5歸并排序基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。Step1：把待排序的n個記錄看作長度為1的有序序列。將相鄰子序列兩兩歸并為長度為2的有序序列；Step2

：把得到的n/2個長度為2的有序子序列再歸并為長度為2*2的有序序列；Step3

：按Step2的方式，重復對相鄰有序子序列進行歸并操作，直到成為一個有序序列為止。282.5歸并排序算法mergeSort初始序列[49][38][65][97][76][13][27]第一步[3849][6597][1376][27]第二步[38496597][132776]第三步[13273849657697]動畫演示：http:///fine/resources/FlashContent.asp?id=93292.5歸并排序遞歸算法描述：voidmerge_sort(intdata[],intleft,intright){if(left<right){intmid=(left+right)/2;

merge_sort(data,left,mid);

merge_sort(data,mid+1,right);

merge(data,left,mid,right);}}初始序列[8][4][5][6][2][1][7][3]

歸并到b[48][56][12][37]

復制到a[48][56][12][37]

歸并到b[4568][1237]

復制到a[4568][1237]

歸并到b[12345678]

復制到a[12345678]

30voidmerge(intarray[],intp,intq,intr){ int

i,k; intbegin1,end1,begin2,end2;

int*temp=newint[r-p+1];

//申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列//設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起止位置begin1=p;end1=q;

begin2=q+1;end2=r;k=0; while((begin1<=end1)&&(begin2<=end2))

{if(array[begin1]<array[begin2]) {temp[k]=array[begin1];begin1++; } else {temp[k]=array[begin2];begin2++; } k++; } 31//接上頁//若第一個序列有剩余，拷貝出來粘到合并序列尾while(begin1<=end1)

temp[k++]=array[begin1++];//若第二個序列有剩余，拷貝出來粘到合并序列尾while(begin2<=end2)

temp[k++]=array[begin2++];

for(i=0;i<(r-p+1);i++)//將排序好的序列拷貝回數(shù)組中

array[p+i]=temp[i];

delete[](temp);}322.5歸并排序復雜度分析T(n)=O(nlogn)

漸進意義下的最優(yōu)算法332.5歸并排序T(n)=2*T(n/2)

+

O(n)

=2*（2*T(n/4)

+

2*O(n/2)

+

O(n)

=4*T(n/4)

+

2*O(n)

=8*T(n/8)

+

3*O(n)

...

=2^k

*

T(n/

2^k)

+

k*O(n)

令

(n=2^k,

k=log(n)

(注：log(n)是以２為底）

則原式T(n)等于

=n*T(1)+log(n)*O(n)

=n*O(1)+O(n*log(n))

=O(n)+

O(n*log(n))

=O(n*log(n))342.6快速排序快速排序是對氣泡排序的一種改進方法，它是由C.A.R.Hoare于1962年提出的。基本思想通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。動畫演示：http:///fine/resources/FlashContent.asp?id=86352.6快速排序算法過程：設要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序。一趟快速排序的算法是：

1）設置兩個變量I、J，排序開始時：I=1，J=N-1；

2）以第一個數(shù)組元素作為關鍵數(shù)據(jù)，X=A[0]；3）從J開始向前搜索，即由后開始向前搜索（J=J-1），找到第一個<=X的值；

4）從I開始向后搜索，即由前開始向后搜索（I=I+1），找到第一個>=X的值5）交換A[I],A[J]

6）重復第3-5步，直到I=J；362.6快速排序例如：待排序的數(shù)組A的值見表，初始關鍵數(shù)據(jù)：X=49

3738392.6快速排序部分排序結(jié)果：402.6快速排序算法步驟：（1）分解(Divide)：將輸入的序列L[p..r]劃分成兩個非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。（2）遞歸求解(Conquer)：通過遞歸調(diào)用快速排序算法分別對L[p..q]和L[q+1..r]進行排序。（3）合并(Merge)：由于對分解出的兩個子序列的排序是就地進行的，所以在L[p..q]和L[q+1..r]都排好序后不需要執(zhí)行任何計算L[p..r]就已排好序。412.6快速排序voidquicksort(intnumber[],intleft,intright){inti,j,s;

if(left<right) {s=number[(left+right)/2];i=left-1;j=right+1;while(1) {while(number[++i]<s);//向右找第一個大于軸的數(shù)

while(number[--j]>s);//向左找第一個小于軸的數(shù)

if(i>=j)break;

SWAP(number[i],number[j]);}

quicksort(number,left,i-1);//對左邊進行遞歸

quicksort(number,j+1,right);//對右邊進行遞歸

}}422.6快速排序?qū)τ趎個成員，快速排序法的比較次數(shù)大約為n*logn

次，交換次數(shù)大約為(n*logn)/6次。如果n為100，冒泡法需要進行4950次比較，而快速排序法僅需要200次?？焖倥判蚍ǖ男阅芘c中間值的選定關系密切，如果每一次選擇的中間值都是最大值（或最小值），該算法的速度就會大大下降?？焖倥判蛩惴ㄗ顗那闆r下的時間復雜度為O(n2)，而平均時間復雜度為O(n*logn)

43尋找支點元素sel_有多種實現(xiàn)方法，不同的實現(xiàn)方法會導致快速排序的不同性能。根據(jù)分治法平衡子問題的思想，我們希望支點元素可以使a[left..right]盡量平均地分為兩部分。幾種尋找pivot的方法(見補充快速排序文件)：a[left....right]選擇的第一個元素a[left]的值作為p(代碼3)；選擇最后一個元素a[right]的值作為p(代碼1)

；選擇中間位置的元素a[mid]的值作為p(代碼2)

；選擇a[left..right]的某一個隨機位置上的值作為p；分解/劃分算法描述44（略）2.7尋找第k小元素元素選擇問題：給定線性序集中n個元素和一個整數(shù)k，1≤k≤n，要求找出這n個元素中第k小的元素。Randomized_Select算法：模仿快速排序算法，首先對輸入數(shù)組進行劃分，然后對劃分出的子數(shù)組之一進行遞歸處理。45（略）2.7尋找第k小元素int

RANDOMIZED_SELECT(int

arr[LEN],int

p,int

r,inti)//找到arr中第i小的數(shù)，數(shù)組下標從1開始{if(p==r)returnarr[p];

intq=RANDOMIZED_PARTITION(arr,p,r);

intk=q-p+1;

if(i==k)returnarr[q];else

if(i<k)returnRANDOMIZED_SELECT(arr,p,q-1,i);elsereturnRANDOMIZED_SELECT(arr,q+1,r,i-k);}46（略）2.7尋找第k小元素算法復雜性：在最壞情況下，算法randomized_Select需要O(n2)計算時間?？梢宰C明，算法Randomized_Select可以在O(n)平均時間內(nèi)找出n個輸入元素中的第k小元素。472.8循環(huán)賽日程表分治法不僅可以用來設計算法，而且再其他方面也有廣泛應用：利用分治法設計電路、構(gòu)造數(shù)學證明等。循環(huán)賽日程標問題，設有n=2k個選手要進行循環(huán)賽，設計一個滿足以下要求的比賽日程表：每個選手必須與其他n-1個選手各賽一次；每個選手一天只能賽一次；循環(huán)賽一共進行n-1天。按此要求，可以將比賽日程表設計成n行n-1列的表格，i行j列表示第i個選手在第j天所遇到的選手。基本思路：按分治策略，將所有的選手分為兩組，n個選手的比賽日程表就可以通過為n/2個選手設計的比賽日程表來決定。遞歸地用對選手進行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這2個選手進行比賽就可以了。482.8循環(huán)賽日程表以k=3(即N=23=8)為例，可以根據(jù)問題要求，制定出如下圖所示的一種方案：以表格的中心為拆分點，將表格分成A、B、C、D四個部分，就很容易看出有A=D，B=C，并且，這一規(guī)律同樣適用于各個更小的部分。492.8循環(huán)賽日程表這樣，對8個隊的賽事排列就逐步減化為對4個隊的排列，然后又進一步減化為對2個隊的排列，最后就成為1個隊的排列。因此，這一問題可以采用分治法的思想來解決。在設計程序時，采用由小到大的方法進行擴展，而數(shù)組下標的處理是解決該問題的關鍵。思考：若n為奇數(shù)，例如5，應該如何排？50補充知識一：堆排序一、堆（heap）的概念特殊的二叉樹結(jié)構(gòu)，是一個從上到下有大小關系的二叉樹。（如父節(jié)點>=子節(jié)點或者父節(jié)點<=子節(jié)點）其中，父節(jié)點值大于或等于其孩子節(jié)點值的，叫“最大堆（maximumheap)”;父節(jié)點值小于或等于孩子節(jié)點值的，叫“最小堆（minimumheap)”.在最大堆中，根中的元素值最大；在最小堆中，根中的元素值最小。51補充知識一：堆排序在起始索引為0的“堆”中：

1)堆的根節(jié)點將存放在位置0

2)節(jié)點i的左子節(jié)點在位置2*i+1

3)節(jié)點i的右子節(jié)點在位置2*i+2

4)節(jié)點i的父節(jié)點在位置floor((i-1)/2)

:注floor表示“取整”操作在起始索引為1的“堆”中：

1)堆的根節(jié)點將存放在位置1

2)節(jié)點i的左子節(jié)點在位置2*i

3)節(jié)點i的右子節(jié)點在位置2*i+1

4)節(jié)點i的父節(jié)點在位置floor(i/2)

:注floor表示“取整”操作52補充知識一：堆排序二、堆的存儲按某種次序?qū)⒁幌盗袛?shù)據(jù)以完全二叉樹形式存放的一種表。它要求堆中的節(jié)點的值都大于或等于其孩子節(jié)點的值。

length[A]：數(shù)組元素個數(shù)。heap_size[A]：存放在數(shù)組A中的堆的元素個數(shù)。例如：{12,39,20,65,47,34,98,81,73,56}為“小頂堆”；{98,81,34,73,56,12,20,39,65,47}為"大頂堆"。parent(i):left（i）：2iright(i):2i+153補充知識一：堆排序三、堆化

數(shù)組具有對應的樹表示形式。一般情況下，樹并不滿足堆的條件。通過重新排列元素，可以建立一棵“堆化”的樹。

heapify(A,i)//設i下面的元素都已堆化l←left(i)r←right(i)ifl<=heap_size[A]andA[l]>A[i]thenlargest←lelselargest←iifr<=heap_size[A]andA[r]>A[largest]thenlargest←riflargest<>ithenexchange(A[i],A[largest])

heapify(A,largest)54補充知識一：堆排序55補充知識一：堆排序Build-heap(A)//建堆，起始索引1heap-size[A]←length[A]fori←floor(length[A]/2)downto1doheapify(A,i)四、建堆的過程是一個"從下到上"調(diào)整堆的過程例如：A(4,1,3,2,16,9,10,14,8,7)，學生演示其建最大堆過程56補充知識一：堆排序堆排序方法基本思想：將原始記錄序列建成一個堆，稱之為初始堆，并輸出堆頂元素；調(diào)整剩余的記錄序列，使之成為一個新堆，再輸出堆頂元素；依此類推，當堆中只有一個元素時，整個序列的排序結(jié)束，輸出的序列便是

原始序列的排序序列。HeapSort(A，intn){∥對記錄序列A[1..n]進行堆排序。

Build-heap(A);

for(i=n;i>1;i--){A[1]←→A[i];∥將堆頂記錄和當前未經(jīng)排序子序列A[1..i]中最后一個記錄相互交換heap-size[A]←heap-size[A]-1

heapify(A);}}例如：A={5,13,2,25,7,17,20,8,4}堆排序后,A={2,4,5,7,8,13,17,20,25}57補充知識一：堆排序五、堆的應用-優(yōu)先級隊列（priorityqueue）概念：用來維護由一組元素構(gòu)成的集合S的數(shù)據(jù)結(jié)構(gòu)，每一個元素都有一個關鍵字key。數(shù)據(jù)項按關鍵字的值有序，關鍵字最小的數(shù)據(jù)項（或者在某些實現(xiàn)中是關鍵字最大的數(shù)據(jù)項）總是在隊頭。數(shù)據(jù)項插入的時候會按照順序插入到合適的位置以確保隊列的順序。

討論基于最大堆的最大優(yōu)先級隊列應用：分時計算機作業(yè)調(diào)度58補充知識一：堆排序操作：max(S):返回S中具有最大關鍵字的元素insert(S,x):將x插入Sextract-max(S):去掉最大，從余下的選出最優(yōu)

HEAP-max(A)1.returnA[1]O(1)59補充知識一：堆排序HEAP-extract-max(A)ifheap-size[A]<1thenerror“heapunderflow”max←A[1]A[1]←A[heap-size[A]]//最后一個元素放在第一heap-size[A]←heap-size[A]-1heapify(A,1);

returnmaxO(1)O(1)O(1)O(1)O(nlog(n-1))O(1)總計O(nlogn)60補充知識一：堆排序HEAP-insert(A,key)//將key插入最大堆A中heap-size[A]←heap-size[A]+1i←heap-size[A]whilei>1andA[parent(i)]<keydoa[i]←A[parent(i)]i←parent(i)A[i]←keyO(1)O(1)O(logn)O(1)*O(logn)O(1)*O(logn)O(1)總計O(logn)61補充知識二：線性時間排序1、計數(shù)排序-CountSort集合A有n個元素，每一個元素的值是介于0到k之間的整數(shù)。輸入：A[1..n]存放排序結(jié)果：B[1..n]臨時存儲：C[0..k]計數(shù)排序的基本思想是對每一個輸入元素x，確定出小于x的元素個數(shù)。有了這一信息，就可以把x直接放到它在最終輸出數(shù)組的位置上。例如：若有5個元素小于x，則x就屬于第6個輸出位置。62補充知識二：線性時間排序1、計數(shù)排序-CountSort例如：A={3,6,4,1,3,4,1,4},數(shù)值從1-->6C2023011的個數(shù)2的個數(shù)3的個數(shù)4的個數(shù)5的個數(shù)6的個數(shù)整理C2<=12<=24778<=6將A從右往左讀，第一個數(shù)為4，查C表為7，生成排序后B數(shù)組B11334446練習：A={1,3,2,4,7,5,2,1,3,6},求排序后數(shù)組B63補充知識二：線性時間排序Count-Sort(A,B,k)//0<=a[i]<=kfori←0tokdoC[i]←0