第12章縮小規(guī)模算法11/19/20221第12章縮小規(guī)模算法二分搜尋技術(shù)歸并排序快速排序習(xí)題11/19/20222二分搜尋技術(shù)〔二分查找、折半查找〕要求線(xiàn)性表是挨次存儲(chǔ)構(gòu)造的有序表。n個(gè)記錄R[0]～R[n-1]按關(guān)鍵字key遞增有序,在n個(gè)記錄中找出關(guān)鍵字的值為x的記錄。11/19/20223算法的根本思想：〔1〕先求位于查找區(qū)間正中的記錄的下標(biāo)mid：mid=(low+high)/2」〔2〕用其關(guān)鍵字與給定值x比較:假設(shè)x==R[mid].key，則查找成功，返回mid值假設(shè)x<R[mid].key，則在左區(qū)間連續(xù)查找，置high=mid-1假設(shè)x>R[mid].key，則在右區(qū)間連續(xù)查找，置low=mid+1(3)重復(fù)計(jì)算mid以及R[mid].key與x比較，每比較一次，查找區(qū)間縮小一半。當(dāng)low>high時(shí)，說(shuō)明查找不成功，查找完畢，返回-1。11/19/20224查找成功的例子 查找失敗的例子11/19/20225

折半查找算法intBinSearch(DateTypeR[],KeyTypex){intlow,high,mid;//low、high表示當(dāng)前查找區(qū)間的下界、上界low=0;high=n-1;//設(shè)置查找區(qū)間下界、上界的初值while(low<=high)//當(dāng)前查找區(qū)間非空{(diào)mid=(low+high)/2;//取當(dāng)前查找區(qū)間的中點(diǎn) if(x==R[mid].key)returnmid;//查找成功，返回 elseif(x<R[mid].key))high=mid-1;//在左區(qū)間查找elselow=mid+1;//在右區(qū)間查找}return-1;//查找失敗}11/19/20226對(duì)于有序序列：-1、0、1、3、4、6、8、10、12，折半查找判定樹(shù)：樹(shù)中每個(gè)圓形結(jié)點(diǎn)表示一個(gè)記錄，結(jié)點(diǎn)的位序是該記錄在表中的位置。全部結(jié)點(diǎn)的空指針域相當(dāng)于指向一個(gè)方形結(jié)點(diǎn)，稱(chēng)為外部結(jié)點(diǎn)。用當(dāng)前查找區(qū)間的中間位置上的記錄作為根，左區(qū)間和右區(qū)間中的記錄分別作為根的左、右子樹(shù)。不妨設(shè)結(jié)點(diǎn)總數(shù)n=2h-1，則描述折半查找的判定樹(shù)是高度為h的滿(mǎn)二叉樹(shù)。2h=n+1,h=log2(n+1)。深度h不計(jì)外部結(jié)點(diǎn)。第1層結(jié)點(diǎn)有1個(gè)，查找第1層結(jié)點(diǎn)要比較1次；第2層結(jié)點(diǎn)有2個(gè)，查找第2層結(jié)點(diǎn)要比較2次；…。查找成功，最多比較h次。時(shí)間簡(jiǎn)單度為O(log2n)11/19/20227對(duì)于有序序列：-1、0、1、3、4、6、8、10、12，描述折半查找過(guò)程的判定樹(shù)及查找6和5的過(guò)程：查找成功的情形查找不成功的情形查找成功的過(guò)程就是走了一條從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑，經(jīng)受比較關(guān)鍵字的次數(shù)恰為該結(jié)點(diǎn)在樹(shù)中的層數(shù)。查找不成功的過(guò)程是一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑，所需的關(guān)鍵字比較次數(shù)是該路徑上內(nèi)部結(jié)點(diǎn)的總數(shù)。11/19/20228歸并排序算法思想

假設(shè)初始表含有n個(gè)記錄，則可看成是n個(gè)有序的子表，每個(gè)子表的長(zhǎng)度為1，然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2或1的有序子表，再兩兩歸并，……如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序子表為止。歸并的過(guò)程將兩個(gè)有序子表合并為一個(gè)有序子表的過(guò)程類(lèi)似于玩撲克牌：假設(shè)桌上有兩堆面朝上的牌，最小的排在上面，現(xiàn)要將這兩堆牌〔看作輸入〕合并成一堆有序的牌〔看作輸出〕。根本步驟是比較兩輸入堆頂上的兩張牌，取出較小的那張牌將它面朝下放到輸出堆中。重復(fù)這一步驟，直至某一輸入堆為空，這是將另一輸入堆中剩余的牌面朝下全部放入到輸出堆中即可。如下圖：11/19/20229設(shè)兩個(gè)有序子表〔相當(dāng)于輸入堆〕放在同一向量中相鄰的位置上：R[low..mid],R[mid+1..high]，先將它們合并到一個(gè)局部的暫存變量R1〔相當(dāng)于輸出堆〕中，待合并完成后將R1復(fù)制回R[low..high]中。08212525*49627293163754Rij0816212525*374954627293lowhighkR1lowmidmid+1high說(shuō)明：加“*”區(qū)分兩個(gè)2511/19/202210二路歸并算法〔MergeSort〕調(diào)用一趟歸并算法〔MergePass〕，一趟歸并算法〔MergePass〕調(diào)用歸并算法〔Merge〕。11/19/202211歸并算法voidMERGE(rectypeR[],intlow,intmid,inthigh)/*R[low..mid]與R[mid+1..high]是兩個(gè)有序子表，結(jié)果為一個(gè)有序子表R[low..high]*/{inti=low,j=mid+1,k=0;

rectype*R1=(rectype*)malloc((high-low+1)*sizeof(rectype));

if(!R1){printf(“申請(qǐng)空間不成功”);exit(0);}while((i<=mid)&&(j<=high))

if(R[i].key<=R[j].key)R1[k++]=R[i++];elseR1[k++]=R[j++];//取小者復(fù)制到R1[k]

while(i<=mid)R1[k++]=R[i++];//復(fù)制第一個(gè)子表的剩余記錄while(j<=high)R1[k++]=R[j++];//復(fù)制其次個(gè)子表的剩余記錄for(k=0,i=low;i<=high;k++,i++)R[i]=R1[k];//歸并完成后將結(jié)果復(fù)制回R[low..high]

}11/19/202212二路歸并排序第1趟歸并排序時(shí)，將R[1..n]看成是n個(gè)長(zhǎng)度為1的有序子序列(歸并項(xiàng))，先做兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的歸并項(xiàng)(假設(shè)n為奇數(shù)，則最終一個(gè)有序子序列的長(zhǎng)度為1)；再做兩兩歸并，…，如此重復(fù)，最終得到一個(gè)長(zhǎng)度為n的有序序列。11/19/202213歸并排序過(guò)程212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=1611/19/202214一趟歸并在給出二路歸并排序算法之前，必需先解決一趟歸并問(wèn)題。在某趟歸并中，設(shè)各子表長(zhǎng)度為length〔最終一個(gè)子表的長(zhǎng)度可能小于length〕，則歸并前R[1..n]中共有n/length個(gè)有序子表：R[1..length],R[length+1..2*length],…R[(n/length-1)*length+1..n]調(diào)用歸并操作將相鄰的一對(duì)子表進(jìn)展歸并時(shí)，必需對(duì)子表的個(gè)數(shù)可能是奇數(shù)，以及最終一個(gè)子表的長(zhǎng)度小于lehgth這兩種特殊狀況進(jìn)展特殊處理：假設(shè)子表的個(gè)數(shù)為奇數(shù)，則最終一個(gè)子表無(wú)須和其它子表歸并〔即本趟輪空〕；假設(shè)子表的個(gè)數(shù)為偶數(shù)，則要留意最終一對(duì)子表中的后一個(gè)子表的區(qū)間上界是n。11/19/202215一趟歸并算法voidMERGEPASS(rectypeR[],intlength)//對(duì)R[1..n]做一趟歸并，length是本趟歸并的有序子表的長(zhǎng)度{inti,j;

i=1;//i指向第一對(duì)子表的起始點(diǎn)while(i+2length1<=n);//歸并長(zhǎng)度為length的兩個(gè)子表{MERGE(R,i,i+length1,i+2length1);

i=i+2length;//i指向下一對(duì)子表的起始點(diǎn)}

if((i+length1)<n)//剩下兩個(gè)子表，其中后一個(gè)長(zhǎng)度小于length

MERGE(R,R1,i,i+length1,n);//歸并最終兩個(gè)子表

//假設(shè)i≤n且i+length-1≥n時(shí)，子表個(gè)數(shù)為奇數(shù)，無(wú)須歸并}11/19/202216二路歸并算法二路歸并排序須調(diào)用“一趟歸并”對(duì)R[1..n]進(jìn)展log2n趟歸并，每趟歸并后，有序子表的長(zhǎng)度均擴(kuò)大一倍〔最終一個(gè)可能例外〕。其算法如下：voidMERGESORT(rectypeR[])//對(duì)R進(jìn)展二路歸并排序

{intlength;

length=1;

while(length<n)//進(jìn)展log2n趟歸并{MERGEPASS(R,length);length=2length;}//有序子表長(zhǎng)度≥n是完畢循環(huán)

}

11/19/202217歸并排序算法分析長(zhǎng)度為n的表，共進(jìn)展log2n趟歸并，每趟歸并的時(shí)間為O(n)，所以歸并排序的時(shí)間簡(jiǎn)單度為O(nlog2n)。歸并排序占用附加存儲(chǔ)較多，需要另外一個(gè)與原待排序記錄數(shù)組同樣大小的幫助數(shù)組，空間簡(jiǎn)單度為O(n)。這是歸并排序算法的缺點(diǎn)。歸并排序是一個(gè)穩(wěn)定的排序方法。11/19/202218快速排序快速排序方法的根本思想是任取待排序記錄序列中的某個(gè)記錄(例如取第一個(gè)記錄)作為基準(zhǔn)，一趟劃分后以該記錄的關(guān)鍵字作為樞軸(pivot)，將整個(gè)記錄序列劃分為左右兩個(gè)無(wú)序子序列：左側(cè)子序列中全部記錄的關(guān)鍵字都小于或等于樞軸記錄的關(guān)鍵字右側(cè)子序列中全部記錄的關(guān)鍵字都大于樞軸記錄的關(guān)鍵字樞軸記錄則排在這兩個(gè)子序列中間(這也是該記錄最終應(yīng)安放的位置)。然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到全部的記錄都按關(guān)鍵字有序排在相應(yīng)位置上為止。11/19/202219快速排序算法承受快速排序方法對(duì)n個(gè)記錄排序，只須調(diào)用QuickSort(R,1,n)，即可完成對(duì)R[1..n]的排序?？焖倥判蛩惴ㄈ缦拢簐oidQUICKSORT(rectypeR[],ints1,intt1);//對(duì)R[s1]到R[t1]做快速排序{

inti;

if(s1<t1)//只有一個(gè)記錄或無(wú)記錄時(shí)無(wú)須排序

{i=PARTITION(R,s1,t1);//對(duì)R[s1]到R[t1]做劃分，i作為樞軸的位置QUICKSORT(R,s1,i1);//遞歸處理左區(qū)間QUICKSORT(R,i+1,t1);//遞歸處理右區(qū)間

}

}11/19/202220快速排序算法須調(diào)用劃分算法對(duì)無(wú)序區(qū)按基準(zhǔn)進(jìn)展劃分。劃分算法如下：intPARTITION(rectypeR[],intl,inth)//對(duì)無(wú)序區(qū)R[1..h]做劃分，返回劃分后被定位的基準(zhǔn)記錄(樞軸〕的位置{inti,j;rectypetemp;i=l;j=h;temp=R[i];//初始化，temp為基準(zhǔn)do{

while((R[j].key>=temp.key)&&(i<j))

j;//從右向左掃描，查找第一個(gè)關(guān)鍵字小于temp.key的記錄if(i<j)R[i++]=R[j];//將R[j]放入j位置，i右移while((R[i].key<=temp.key)&&(i<j))

i++;//從左向右掃描，查找第一個(gè)關(guān)鍵字大于temp.key的記錄if(i<j)R[j]=R[i];//將R[i]放入j位置，j左移}while(i!=j);

R[i]=temp;//將基準(zhǔn)temp放入樞軸位置returni;//返回樞軸位置}

11/19/202221第一次劃分的過(guò)程各趟排序之后的狀態(tài)交換排序(ExchangeSort)起泡排序的根本方法是：設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為n。最多作n-1趟排序。在第i趟中順次兩兩比較r[j+1].Key和r[j].Key，j=1,2,,i-1。假設(shè)發(fā)生逆序，則交換r[j+1]和r[j]。交換排序的根本思想是兩兩比較待排序?qū)ο蟮年P(guān)鍵字，假設(shè)發(fā)生逆序(即排列挨次與排序后的次序正好相反)，則交換之，直到全部對(duì)象都排好序?yàn)橹埂Ｆ鹋菖判?BubbleSort)11/19/20222421254925*16081234562125*i=6251649chang=10812345625*chang=1i=5492125160812345611/19/20222525*123456i=34916chang=108252125*123456i=24916chang=008252149i=40816chang=125*252112345611/19/202226voidBubbleSort(SqList*L){for(inti=L->length,change=TRUE;i>1&&change;--i)//進(jìn)展n-1趟排序。假設(shè)前一趟未發(fā)生交換，則完畢排序{ change=FALSE;//設(shè)置未交換標(biāo)志 for(intj=1;j<i;++j)//趟內(nèi)比較n-i次 if(L->r[j+1].key<L->r[j].key))//假設(shè)不符合非遞減的挨次，則進(jìn)展交換{temp=L->r[j]; L->r[j]=L->r[j+1]; L->r[j+1]=temp; change=TRUE;//設(shè)置本趟發(fā)生交換的標(biāo)志 }}}起泡排序的算法〔不講〕11/19/202227算法分析在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí)，此算法只執(zhí)行一趟起泡，做n-1次關(guān)鍵字比較，不移動(dòng)對(duì)象。這是最好的情形。最壞的情形是算法執(zhí)行了n-1趟起泡，第i趟(1in)做了n-i次關(guān)鍵字比較，執(zhí)行了n-i次對(duì)象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)〔KCN〕和對(duì)象移動(dòng)次數(shù)〔RMN〕為：11/19/202228

起泡排序需要一個(gè)附加對(duì)象以實(shí)現(xiàn)對(duì)象值的對(duì)換。起泡排序是一個(gè)穩(wěn)定的排序方法。11/19/202229雙向起泡排序〔不講〕voiddbubblesort(sequenlistr[],intn){ inti=1,j,change=1; sequenlisttemp; while(change){ change=0;//設(shè)置本趟交換標(biāo)志的初值 for(j=n-i+1;j>=i+1;j--)//從右向左掃描 if(r[j].key<r[j-1].key) {temp=r[j];r[j]=r[j-1];r[j-1]=temp; change=1;//設(shè)置本趟發(fā)生交換標(biāo)志 }

11/19/202230 for(j=i+1;j<=n-i;j++)//從左向右掃描 if(r[j].key>r[j+1].key) { temp=r[j];r[j]=r[j+1];r[j+1]=temp; change=1;//設(shè)置本趟發(fā)生交換標(biāo)志} for(intk=1;k<=n;k++)//輸出本趟排序的結(jié)果 printf(“%5d“,r[k].key); printf(“\n“); i++; }}11/19/202231選擇排序的根本思想是：每一趟(例如第i趟，i=1,…,n-1)在后面的n-i+1個(gè)待排序?qū)ο笾羞x出關(guān)鍵字最小的對(duì)象,作為有序?qū)ο笮蛄械牡趇個(gè)對(duì)象。待到第n-1趟作完，待排序?qū)ο笾皇Ｏ?個(gè)，就不用再選了。選擇排序(SelectionSort)〔不講〕根本步驟為：i從1開(kāi)頭，直到n-1，進(jìn)展n-1趟排序，第i趟的排序過(guò)程為：在一組對(duì)象r[i]～r[n](i=1,2,…,n-1)中選擇具有最小關(guān)鍵字的對(duì)象；并和第i個(gè)對(duì)象進(jìn)展交換；11/19/202232簡(jiǎn)潔選擇排序的算法voidSelectSort(SqList*L){for(inti=1;i<L->length;++i){intk=i; for(intj=i+1;j<=L->length;++j) if(L->r[k].key>L->r[j].key)k=j; if(i!=k){temp=L->r[i]; L->r[i]=L->r[k]; L->r[k]=temp; } }}11/19/20223321254925*16081234562125*i=1492516251608490825*4921i=2i=3081625*2521初始最小者08交換21,08最小者16交換25,16最小者21交換49,2111/19/2022344925*123456