算法課件-第9章(內排序)

第九章內排序★基本概念★插入排序★冒泡排序★選擇排序★計數排序★希爾排序★堆排序★快速排序★合并排序★基數排序第九章內排序★基本概念★插入排序★冒泡排序★選擇設含有n個記錄的文件{R1,R2,…，Rn

},其相應的關鍵字為{K1,K2,…，Kn

}，需確定一種排列P(1),P(2),…,P(n),使其相應的關鍵字滿足如下的遞增(或遞減)關系：KP(1)≤KP(2)≤KP(3)≤…≤KP(n)即，使上述文件成為一個按其關鍵字線性有序的文件{RP(1),RP(2),…，RP(n)},這樣一種運算稱為排序。9.1基本概念如果在排序期間具有相同關鍵字的記錄的相對位置不變，則稱此方法是穩(wěn)定的。排序：排序的穩(wěn)定性：設含有n個記錄的文件{R1,R2,…，R即，1)K(i)≤K(i+1)(1≤i≤n-1)2)若在輸入文件中i<j,且Ki=Kj,則在經過排序后的文件中仍Ri先于Rj排序內排序：整個排序過程都在內存進行的排序。外排序：當文件很大以至于內存不足以存放全部記錄，在排序過程中需要對外存進行存取訪問。例如：將下列關鍵字序列52,49,80,36,14,58,61,23,97,75調整為14,23,36,49,52,58,61,75,80,97即，1)K(i)≤K(i+1)(1≤i≤n-內部排序的方法

在排序的過程中，參與排序的記錄序列中存在兩個區(qū)域：有序區(qū)和無序區(qū)。

內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。使有序區(qū)中記錄的數目增加一個或幾個的操作稱為一趟排序。存放待排序數據的數據結構：typedefstruct{intkey;datatypeotheritem;//其他域}records;typedefstructrecordsList[n+1];內部排序的方法使有序區(qū)中記錄的數目增加一個或幾個的逐步擴大記錄有序序列長度的方法大致有下列幾類：1.插入類:將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度；2.交換類:通過“交換”無序序列中的記錄從而得到其中關鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度；3.選擇類:從記錄的無序子序列中“選擇”關鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度；4.歸并類:通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度；5.其它方法。逐步擴大記錄有序序列長度的方法大致有下列幾類：1.插入類:內排序插入類排序直接插入排序折半插入排序希爾排序交換類排序冒泡排序快速排序選擇類排序選擇排序堆排序歸并類排序歸并排序其他排序計數排序基數排序內插入類排序直接插入排序折半插入排序希爾排序交換類排序冒泡排9.2計數排序對每個記錄計算文件中有多少個其它記錄的關鍵字大于該記錄的關鍵字值，從而找到該記錄的正確排序位置。keyinfocount設一個記錄有三個域：關鍵字域該記錄的其他信息域計數域排序算法的思想：9.2計數排序對每個記錄計算文件中有多少個其它記錄的關鍵字for(i=1;i<n;i++)for(j=i+1;j<=n;j++)if(R[i].key)<R[j].key)R[i].count=R[i].count+1;elseR[j].count=R[j].count+1;}voidcountsort(ListR,intn){for(i=1;i<=n;i++)R[i].count=1;//對所有元素的count域置1；算法如下：for(i=1;i<n;i++)voi設文件有n個記錄，則外循環(huán)：i=1時，內循環(huán)要做n-1次比較；i=2時，內循環(huán)要做n-2次比較；…i=n-1時，內循環(huán)要做1次比較；總的比較次數為(n-1)+(n-2)+…+1=n(n-1)/2算法性能分析：所以，算法所需時間為O(n2)，由于不需要記錄移動和額外空間，同時算法簡單，當n較小時，可采用本算法。設文件有n個記錄，則外循環(huán)：算法性能分析：所以，算法例關鍵字序列{46，55，13，42，44，17，05，70}關鍵字4655134244170570初始化11111111i=131222221i=232333331i=332733341i=432753451i=532754561i=632754671i=732754681例關鍵字序列{46，55，13，42，44，17，05，79.3直接插入排序假設在排序過程中，記錄序列R[1..n]的狀態(tài)為：

則一趟插入排序的基本思想為：將記錄R[i]插入到有序子序列R[1..i-1]中，使記錄的有序序列從R[1..i-1]變?yōu)镽[1..i]。顯然，完成這個“插入”需分三步進行：1．查找R[i]的插入位置j+1；2．將R[j+1..i-1]中的記錄后移一個位置；3．將R[i]復制到R[j+1]的位置上。9.3直接插入排序假設在排序過程中，記錄序列R[1..n]直接插入排序：利用順序查找實現“在R[1..i-1]中查找R[i]的插入位置”的插入排序。注意直接插入排序算法的三個要點：

1.從R[i-1]起向前進行順序查找，監(jiān)視哨設置在R[0]；R[0]=R[i]；{設置“哨兵”}j=i-1;while(R[0].key<R[j].key)j=j-1;{//從后往前找}Return(j+1);{返回R[i]的插入位置為j+1}2.對于在查找過程中找到的那些關鍵字不小于R[i].key的記錄，并在查找的同時實現記錄向后移動；while(R[0].key<R[j].key){R[j+1]=R[j];j=j-1;}3.i=2，3，…,n,實現整個序列的排序。直接插入排序：利用順序查找實現“在R[1..i-1]中查找R排序算法如下：voidinsort(Listr,intn){//r為給定的表，其記錄為r[i]，i=0，1，…，n，x為暫存單元。for(i=2;i<=n;i++){r[0]=r[i];//r[0]作為標志位j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j--;}//j從i-1至0，r[j].key與r[i].key進行比較r[j+1]=r[0];}}//insort排序算法如下：排序的時間分析：

實現排序的基本操作有兩個：（1）“比較”序列中兩個關鍵字的大小；（2）“移動”記錄。對于直接插入排序：最好的情況（關鍵字在記錄序列中順序有序）：最壞的情況（關鍵字在記錄序列中逆序有序）：“比較”的次數：“移動”的次數：

總的說來，直接插入排序所需進行關鍵字間的比較次數和記錄移動的次數均為n2/4，所以直接插入排序的時間復雜度為O(n2)?！氨容^”的次數：“移動”的次數：

2(n-1)排序的時間分析：

最壞的情況（關鍵字在記錄序列中逆序有序9.4折半插入排序排序算法的思想：由于直接插入排序的內循環(huán)(從1到i-1)的查找(或說是比較)是在(部分)有序表的環(huán)境下進行的，所以內循環(huán)用“折半查找法”，比用順序查找法快。9.4折半插入排序排序算法的思想：由于直接插入排序算法描述如下：voidbinsort(Listr,intn){for(i=2;i<=n;i++){r[0]=r[i];low=1;high=i-1;while(low<=high){m=(low+high)/2;ifr[0].key<r[m].keyhigh=m-1;elselow=m+1;}for(j=i-1;j<=low;j--)r[j+1]=r[j];//把從第low起到第i-1各記錄后移r[low]=r[0];//將第i個記錄插入}}//binsort算法描述如下：9.5冒泡排序排序算法的思想：比較k1和k2,如果這些關鍵字的值不符合排序順序,就交換k1和k2；然后對記錄k2和k3,k3和k4等等進行相同的工作。直到kn-1和kn為止,到此得到一個最大(或最小)關鍵字值存在kn的位置上(通常將此過程叫做一趟)。重復這個過程,就得到在位置kn-1,kn-2等處的適當記錄,使得所有記錄最終被排好序。

例如:將5個記錄的關鍵字7,4,8,3,9進行冒泡排序。排序后k1≤k2≤…≤kn(n=5)。7443347344837773888899999①②③④

因為到第四趟就沒有交換的偶對了,所以整個排序結束。9.5冒泡排序排序算法的思想：比較k1和k2,如果這些關算法描述如下:voidbubblesort(Listr,intn){for(m=1;m<=n;m++)scanf(“%d”,r[m]);k=n;do{all=〝T〞;//all=T,標志沒有交換的;all=F,標志有交換的for(m=1;m<=k-1;m++){i=m+1;if(r[m]>r[i]){max=r[m];r[m]=r[i];r[i]=max;all=〝F〞;}}k--;}while((all==〝F〞)&&(k!=1)}冒泡排序的結束條件為：最后一趟沒有進行“交換”。冒泡排序是一種穩(wěn)定的排序算法。算法描述如下:冒泡排序的結束條件為：最后一趟沒有進行“交換”時間分析:最好的情況（關鍵字在記錄序列中順序有序）：只需進行一趟起泡“比較”的次數：“移動”的次數：n-10

最壞的情況（關鍵字在記錄序列中逆序有序）：需進行n-1趟起泡“比較”的次數：“移動”的次數：

時間分析:“比較”的次數：“移動”的次數：最壞的情況（關鍵9.6希爾排序基本思想：對待排序記錄序列先作“宏觀”調整，再作“微觀”調整。所謂“宏觀”調整，指的是，“跳躍式”的插入排序。即：將記錄序列分成若干子序列，每個子序列分別進行插入排序,待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。假設將n個記錄分成d個子序列，則這d個子序列分別為：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}其中，d稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為1。9.6希爾排序基本思想：對待排序記錄序列先作“宏觀例如：

第二趟希爾排序，設增量d=3

第三趟希爾排序，設增量d=1例如：

第二趟希爾排序，設增量d=3

希爾排序的算法描述如下:voidShellInsert(Listr,intd)//本算法對直接插入算法作了以下修改：//1.前后記錄位置的增量是d，而不是1；//2.r[0]只是暫存單元，不是哨兵。當j<=0時，插入位置已找到。{for(i=d+1;i<=n;i++)if(r[i]<r[i-d])//需將r[i]插入有序增量子表{r[0]=r[i];//暫存在R[0]j=i-d;while((j>0)and(r[0]<r[j])){r[j+d]=r[j];//記錄后移，查找插入位置j=j-d;}r[j+d]=r[0];//插入}}for(i=2;i<=n;i++){r[0]=r[i];j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j=j-1;}r[j+1]=r[0];}希爾排序的算法描述如下:for(i=2;i<=n;iVoidShell_sort(Listr,intdlta,intt);{//按增量序列dlta[0..t-1]對順序表r作希爾排序for(k=0;k<=t;k++)ShellInsert(r,dlta[k]);}VoidShell_sort(Listr,intd

先取定一個兩項之間的距離d1(≤n,其中n為整個表的長度),反復比較每兩個相距d1的項,直到以d1為距離劃分的組排序好為止(至此一趟排序完成);然后取d2<d1,再繼續(xù)以d2為距離反復比較每兩個相距為d2的項,…,依此類推.取每個di+1<di,直到dt=1為止。例如,假設文件中8個記錄的關鍵字,我們不采用順序比較,而是先從第一個關鍵字開始每隔4個關鍵字進行比較;同理第二個也從隔4個關鍵字進行比較,第三個…,第四個…,依次做下去.題中選d1=4,從小到大排序:例先取定一個兩項之間的距離d1(≤n,其中n為整個表的初始d1=44655134294170570

55與1713與05第一趟后結果4617054294551370

46與0594與1346與13第二趟后結果d2=20517134246559470

13,46分別交換兩次0513174246557094

第三趟后結果d3=113與1794與70初始d1=446551342NorthChinaElectricPowerUniversity9.7選擇排序基本思想：首先在n個記錄中選擇一個具有最小或最大關鍵字的記錄，將選出的記錄與記錄集合中的第一個記錄交換位置。然后在r[2]至r[n]中選擇一個最小或最大的值與r[2]交換位置，…，依此類推，直至r[n-1]和r[n]比較完畢。voidslsort(Listr,intn)//每次從r[j](j=i+1,…n)中選了最小值，與r[i](i=1,2,…,n-1)交換，進行分類{for(i=1;i<=n-1;i++)//共進行n-1趟排序{m=i;for(j=i+1;j<=n;j++)if(r[j].key<r[m].key)m=j;//m指示關鍵字最小的記錄的序號if(m!=i){x=r[i];r[i]=r[m];r[m]=x;}}}NorthChinaElectricPowerUni例關鍵字序列{055，55，60，13，05，94，17，70},利用選擇排序算法進行排序。關鍵字r[1]055r[2]55r[3]60r[4]13r[5]05r[6]94r[7]17r[8]70i=1,m=505556013055941770i=2,m=405136055055941770i=3,m=705131755055946070i=4,m=405131755055946070i=5,m=505131755055946070i=6,m=705131755055609470i=7,m=805131755055607094不穩(wěn)定例關鍵字序列{055，55，60，13，05，94，17，算法的復雜性分析：當選則第一個最小值時需進行n-1次比較，選第二個最小值時需進行n-2次比較，…，選n-1個最小值時需進行n-(n-1)次比較，所以總的比較次數為(n-1)+(n-2)+…+2+1=n(n-1)/2故排序n個記錄需要時間為O(n2)。由于執(zhí)行一次交換，需三次移動記錄，最多交換n-1次，故最多移動次數為3(n-1)算法的復雜性分析：由于執(zhí)行一次交換，需三次移動記錄，最多交換NorthChinaElectricPowerUniversity9.8堆排序1.定義：堆是由n個記錄的線性序列{R1,R2,…，Rn};其關鍵字序列{k1,k2,…，kn},滿足下列特性時，稱之為堆?；蛉魧⒋藬盗锌闯墒且豢猛耆鏄涞捻樞虼鎯Ρ硎?，則堆或是空樹或是滿足下列特性的完全二叉樹：其左、右子樹分別是堆，并且當左、右子樹不空時，根結點的值小于(或大于)左、右子樹根結點的值。下列兩個序列為堆，對應的完全二叉樹如下圖{96，83，27，38，11，09}9683273811091236248547305391ki≤k2iki≤k2i+1ki≥k2iki≥k2i+1大根堆小根堆{12，36，24，85，47，30，53，91}NorthChinaElectricPowerUni1)首先將一個關鍵字集合用完全二叉樹的形式排列;如給定關鍵字集合為{46,55,13,42,94,17,05,70}組成的完全二叉樹如下：46551342941705702.建堆的過程：1)首先將一個關鍵字集合用完全二叉樹的形式排列;465512)開始建堆：采用篩選法，逐步將大的關鍵字篩到堆底。篩選法的思想是這樣的：

?假設集合r有m個結點，從某個結點i（第一次i=[m/2]）開始篩選;

?先看第i個結點的左右子樹，設第i個結點的左子樹為kj,右子樹為kj+1。若kj<kj+1則沿左分支篩，否則沿右分支篩選，即（j=j+1）。將ki與kj進行比較，若ki>kj則對調，小的上來大的下去。

?

然后kj作為新的根結點，再對新的根結點的左右子樹進行判斷。重復上述過程，直到某個結點的左或右子樹根結點的下標大于m為止。2)開始建堆：采用篩選法，逐步將大的關鍵字篩到堆底。第一次調用篩選法：m=8,i=[m/2]=4,從i=4開始，看k4的左右子樹，僅有左子樹，因此42與70比較，42<70，所以不變。j=i*2=8，i=j，再向下看，此時的i無左右子樹,所以返回，如右圖所示。4655134294170570第二次調用篩選法：i=3,k3=13,13的左右子樹為17和05，因17>05,故沿右子樹比較，13>05,進行對調，此時13無左右子樹，所以返回。4655134294170570NorthChinaElectricPowerUniversity0513{46,55,13,42,94,17,05,70}{46,55,05,42,94,17,13,70}

?先看第i個結點的左右子樹，設第i個結點的左子樹為kj,右子樹為kj+1。若kj<kj+1則沿左分支篩，否則沿右分支篩選，即（j=j+1）。將ki與kj進行比較，若ki>kj則對調，小的上來大的下去。

?然后kj作為新的根結點，再對新的根結點的左右子樹進行判斷。重復上述過程，直到某個結點的左或右子樹根結點的下標大于m為止。第一次調用篩選法：m=8,i=[m/2]=4,從i=4開始，第三次調用篩選法：i=2,k2=55,因為42<94，所以沿左子樹篩選，42<55,進行對調，此時55還有左子樹70，因55<70，所以不變，再向下70無左右子樹，所以返回，此時二叉樹如右圖所示。4655054294171370第四次調用篩選法：i=1,k1=46,因為05<42，所以沿右子樹篩選，05<46,進行對調，此時46還有左右子樹17,13，因13<17，所以再沿右子樹篩選，13<46,所以對調，46無左右子樹，所以返回，此時二叉樹如右圖所示。4642055594171370NorthChinaElectricPowerUniversity554246054613{46,42,05,55,94,17,13,70}{05,42,13,55,94,17,46,70}

?先看第i個結點的左右子樹，設第i個結點的左子樹為kj,右子樹為kj+1。若kj<kj+1則沿左分支篩，否則沿右分支篩選，即（j=j+1）。將ki與kj進行比較，若ki>kj則對調，小的上來大的下去。

?然后kj作為新的根結點，再對新的根結點的左右子樹進行判斷。重復上述過程，直到某個結點的左或右子樹根結點的下標大于m為止。第三次調用篩選法：i=2,k2=55,因為42<94，所以3.建堆的算法voidsift(Listr,intk,intm)//對m個結點的集合r從某個結點i=k開始篩選，如果r[j]>r[j+1](j=2i)，則沿右//分支篩，否則沿左分支篩。把關鍵字大的篩到堆底。{i=k;j=2*i;x=r[i];r[i]=x;//將x放在適當的位置}//siftNorthChinaElectricPowerUniversitywhile(j<=m){if((j<m)&&(r[j].key>r[j+1].key))//左子樹>右子樹j++;//沿右篩}if(x.key>r[j].key){r[i]=r[j];i=j;j=2*i;

}//將關鍵字小的換到i位置，x.key再準備與下一層的比較elsej=m+1;//強制跳出while循環(huán)3.建堆的算法NorthChinaElectricP以上面建的堆為例,說明重建堆的執(zhí)行過程。輸出0570r[1]0542135594174670704213559417460513421755947046重建堆輸出1346r[1]46421755947005重建堆050570X{05,42,13,55,94,17,46,70}{13,42,17,55,94,70,46,05}134613704.堆排序過程以上面建的堆為例,說明重建堆的執(zhí)行過程。輸出0570r[1]1317424655947005輸出1770r[1]13704246559405重建堆1713425546709405輸出4294r[1]17139455467005重建堆{17,42,46,55,94,70,13,05}X177017{42,55,46,70,94,17,13,05}429442701317424655947005輸出1770r[1]13704217134655947005輸出4670r[1]42171370559405重建堆4642171355709405輸出5594r[1]46421713947005重建堆{46,55,94,70,42,17,13,05}467046X{55,70,94,46,42,17,13,05}55945570704217134655947005輸出4670r[1]42177094554642171305輸出7094r[1]94554642171305退出K循環(huán)打印949470554642171305{70,94,55,46,42,17,13,05}709470{94,70,55,46,42,17,13,05}7094554642171305輸出7094r[1]9455堆排序的過程：用拔尖的方法將堆頂輸出,把最后一個元素送到樹根上,然后從i=1開始,調用篩選算法重新建堆,再將堆頂輸出將最后一個送到樹根,再重新建堆。如此反復,直到得到最后全部排序好的關鍵字序列。算法描述如下：voidheapsort(Listr,intn)//對n個結點的集合r進行堆排序{for(i=n/2;i>=1;i--)sift(r,i,n);//從第[n/2]個結點開始進行篩選建初始堆}//headsortfor(k=n;k>=2;k--){t=r[k];r[k]=r[1];r[1]=t;printf(“%d”,r[k]);sift(r,1,k-1);}//重建堆printf(“%d”,r[1]);//輸出最后一個元素即最大元素堆排序的過程：用拔尖的方法將堆頂輸出,把最后一個元素送到樹根NorthChinaElectricPowerUniversity1）對深度為h的堆，“篩選”所需進行的關鍵字比較的次數至多為2(h-1);5.堆排序的時間復雜度分析2）對n個關鍵字，建成深度為

的堆，所需進行的關鍵字比較的次數不超過：h=(log2n」+1)NorthChinaElectricPowerUni2（log2(n-1)」+log2(n-2)」+…+log22）<2n(log2n」)共n-2項相加因此，堆排序的時間復雜度為O(nlogn)3）調整“堆頂”n-1次，總共進行的關鍵字比較的次數不超過：2（log2(n-1)」+log2(n-2)」+例：關鍵字序列{3，27，36，027}32736027已為初始堆輸出3027r[1]02727363輸出027此時為堆36r[1]36273027輸出2736r[1]重建堆2736302736302727退出K循環(huán)打印3636302727輸出序列為：3，027，27，36不穩(wěn)定6.堆排序的穩(wěn)定性分析例：關鍵字序列{3，27，36，027}32736027已NorthChinaElectricPowerUniversity9.9快速排序快速排序又稱分劃交換排序，設輸入文件有n個記錄R1,R2,…,Rn,它們對應的關鍵字是k1,k2,…,kn。該方法先取序列中任一關鍵字K(通常取第一個)，然后用K從兩頭到中間進行比較/交換，就能形成一個分劃：凡是小于等于K的被移到左邊，凡是大于K的被移到右邊。1.快速排序的定義NorthChinaElectricPowerUniNorthChinaElectricPowerUniversity2.快速排序步驟2)從最末項kn開始起指針j倒向前找到第一個kj<x.key或i≥j時，則判i<j?是，kj送ki，i=i+1；1)選定k1為起點，且將k1送x；3)從ki項起指針i向前掃描，找到第一個ki>x.key或i≥j時，則判i<j?是，ki送kj，j=j-1；4)上述過程進行到i=j時停止，將x送ki，同時i=i+1；j=j-1,即x在正確位置上,并分K為K1和K2兩個子集合；5)重復調用上述過程，直到將整個集合排序好為止。NorthChinaElectricPowerUni例:初始關鍵字[4655134294051770]將46→xij第一次交換后[

55134294051770]ji第二次交換后[17551342940570]ji第三次交換后[17

134294055570]j第四次交換后[1705134294

5570]jii至此，完成第一趟排序1755059446例:初始關鍵字[46551342940第五趟排序后0513174246557094第一趟排序后[17051342]46[945570]第二趟排序后[1305]17[42]46[945570]第三趟排序后[05]1317[42]46[945570]第四趟排序后0513174246[7055]94

例:初始關鍵字[4655134294051770]接上例第一趟排序后[170513voidqksort(Listr,intL,intP)//將r[L]至r[P]進行排序{}//qksort3.快速排序算法do{while((r[j].key>=x.key)&&(j>i))j--;//從表尾一端開始比較if(i<j){r[i]=r[j];i++;while((r[i].key<=x.key)&&(i<j))i++;//再從表的始端起進行比較if(i<j){r[j]=r[i];j--;}}}while(i!=j);i=L;j=P;x=r[i];//置初值r[i]=x;i++;j--;//一趟快排結束，將x移至正確位置

if(L<j)qksort(r,L,j);

//反復排序前一部分if(i<P)qksort(r,i,P);

//反復排序后一部分voidqksort(Listr,intL,inNorthChinaElectricPowerUniversity快速排序是目前內部排序中最快的方法。若關鍵字的分布式均勻的，可以粗略的認為每次劃分都把文件分成長度相等的兩個文件。4.快速排序算法的性能分析但如果原來的文件是有次序的，時間復雜性為O(n2)。因此，快速排序偏愛一個無次序的文件。令T(n)為分類n個記錄所需之比較次數,設n=2k，則k=log2n，有：T(n)≤cn+2T(n/2)(其中cn為進行一趟排序所需的時間)T(n)≤cn+2(cn/2+2T(n/4))≤2cn+4T(n/4)……≤kcn+2kT(1)=O(nlog2n)NorthChinaElectricPowerUni5.快速排序算法的穩(wěn)定性分析例：關鍵字序列{5，2，02}ij第一次交換后[02202]5→xj第二次交換后[022]02

j至此，完成排序，序列為{02,2,5}第一次交換[022]5ji02→x第一趟無交換25第二趟5不穩(wěn)定i025.快速排序算法的穩(wěn)定性分析例：關鍵字序列{5，2，02例K={46,79,56,38,40,84}

（1）它的初始堆是：

（2）快速排序第一趟結果：（1）467956384084384056794684（2）40，38，46，56，79，84例K={46,79,56,38,40,84}

（1）它的初NorthChinaElectricPowerUniversity歸并排序的基本思想是：將兩個或兩個以上的有序子序列“歸并”為一個有序序列。在內部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的有序子序列

歸并為一個有序序列。

9.10歸并排序NorthChinaElectricPowerUniNorthChinaElectricPowerUniversity2-路歸并排序算法voidmerge(intL,intm,intn,Listr,Listr2)//表r可看成兩個文件首尾相接的兩個文件，即需合并的兩個文件為r，合并到第三個表r2上{i=L;k=L;j=m+1;//從L開始while(i<=m)&&(j<=n)//當兩個表都有內容未排完時{if(r[i].key<=r[j].key){r2[k]=r[i];i++;}else{r2[k]=r[j];j++;}k++;}if(i>m)COPY(r,j,n,r2);//將r[j]至r[n]照抄至r2上，即表1完照抄第2個表elseCOPY(r,i,m,r2);//將r[i]至r[m]照抄至r2上}//mergeNorthChinaElectricPowerUniNorthChinaElectricPowerUniversity采用2-路歸并算法進行排序的思想：先將初始文件分成長度為１的n個子文件并且合并到相鄰的子文件。則可以得到大約n/2個長度為2的子文件，重復上述過程，直到僅剩下一個長度為n的文件。

下面的例子顯示了這個排序過程(直接合并排序),每個子文件用方括號括起來。初始文件2557483712928633n=8個子文件[25][57][48][37][12][92][86][33]第一趟[2557][3748][1292][3386]

第二趟[25374857][12338692]

第三趟[1225333748578692]NorthChinaElectricPowerUniNorthChinaElectricPowerUniversity設一個輔助數組aux,被用于保存合并x的兩個子數組所得的結果。變量size用于控制被合并的子文件的大小。因為每次被合并的兩個子文件總是x的兩個子數組,所以必須用變量來指出子數組的上下界。ib1和ub1分別表示待合并的第一個子文件的下界與上界,ib2和ub2分別表示待合并的第二個子文件的下界和上界.變量i和j用來指示待合并的兩個子文件(即源文件)的元素,變量k用于指示合并得到的目標子文件的元素。歸并排序算法：voidmergsort(Listx,intn)//x數組用來存放待合并的文件，n為待合并子文件的個數{size=1;//置被合并的文件長度為1;while(size<n){ib1=1;//為第一個文件初始化下界k=1;//k是輔助數組的標號NorthChinaElectricPowerUniNorthChinaElectricPowerUniversitywhile(ib1+size<=n)//checkiftherearetwofilestomerge{ib2=ib1+size;ub1=ib2-1;if(ib2+size-1>n)ub2=n;elseub2=ib2+size-1;merge(ib1,ub1,ub2,x,aux);ib1=ub2+1;}//復制最后一個文件i=ib1;while(k<=n){aux[x]=x[i];k++;i++;}NorthChinaElectricPowerUni//調整x和問題規(guī)模for(k=1;k<=n;k++)x[k]=aux[k];size=2*size;}//whilesize<ndo}//mergsort從上面的算法可以看出size變量的取值不超過log2n個，對size的每一個取值都掃描n個記錄,所以歸并排序的時間復雜性為O(nlog2n)//調整x和問題規(guī)模從上面的算法可以看出size變量的取值不NorthChinaElectricPowerUniversity9.11基數排序借助“多關鍵字排序”的思想來實現“單關鍵字排序”的算法。1.多關鍵字的排序假設有n個記錄的序列{R1,R2,…Rn},每個記錄Ri中含有d個關鍵字(Ki0,Ki1,…,Kid-1),則稱上述記錄序列對關鍵字(Ki0,Ki1,…,Kid-1)有序是指:對于序列中任意兩個記錄Ri和Rj(1≤i<j≤n)都滿足下列(詞典)有序關系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中K0被稱為“最主”位關鍵字，Kd-1被稱為“最次”位關鍵字。實現多關鍵字排序通常有兩種作法:最高位優(yōu)先MSD法：先對K0進行排序，并按K0的不同值將記錄序列分成若干子序列之后，分別對K1進行排序,…，依次類推,直至最后對最次位關鍵字排序完成為止。1.多關鍵字的排序NorthChinaElectricPowerUniNorthChinaElectricPowerUniversity最低位優(yōu)先LSD法：先對Kd-1進行排序，然后對Kd-2進行排序，依次類推，直至對最主位關鍵字K0排序完成為止。排序過程中不需要根據“前一個”關鍵字的排序結果，將記錄序列分割成若干個(“前一個”關鍵字不同的)子序列。對K2排序1,2,152,3,183,1,202,1,203,2,30對K1排序3,1,202,1,201,2,153,2,302,3,18對K0排序1,2,152,1,202,3,183,1,203,2,30無序序列3,2,301,2,153,1,202,3,182,1,20例如:學生記錄含三個關鍵字:系別、班號和班內的序列號，其中以系別為最主位關鍵字。LSD的排序過程如下:NorthChinaElectricPowerUniNorthChinaElectricPowerUniversity2.鏈式基數排序

假如多關鍵字的記錄序列中，每個關鍵字的取值范圍相同，則按LSD法進行排序時,可以采用“分配-收集”的方法，其好處是不需要進行關鍵字間的比較。對于數字型或字符型的單關鍵字，可以看成是由多個數位或多個字符構成的多關鍵字，此時可以采用這種“分配-收集”的辦法進行排序，稱作基數排序法。例如：對下列這組關鍵字{209,386,768,185,247,606,230,834,539}首先按其“個位數”取值分別為0,1,…，9,“分配”成10組之后按從0至9的順序將它們“收集”在一起;然后按其“十位數”取值分別為0,1,…，9“分配”成10組，之后再按從0至9的順序將它們“收集”在一起;最后按其“百位數”重復一遍上述操作，便可得到這組關鍵字的有序序列。2.鏈式基數排序NorthChinaElectricPowerUni4)對每個關鍵字位均重復2)和3)兩步。在計算機上實現基數排序時，為減少所需輔助存儲空間，應采用鏈表作存儲結構，即鏈式基數排序，具體作法為：待排序記錄以指針相鏈，構成一個鏈表；

2)“分配”時，按當前“關鍵字位”所取值，將記錄分配到不同的“鏈隊列”中，每個隊列中記錄的“關鍵字位”相同；3)“收集”時，按當前關鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;3.基數排序步驟在計算機上實現基數排序時，為減少所需輔助存儲空間，應例如,有一組關鍵字｛179,208,306,093,859,984,055,009,271,033｝這些關鍵字是10進制數,基數rd=10,位數d=3.文件的初始狀態(tài)是一個單鏈表,表頭指針指向第一個記錄:179984093009005306859271208033例如,有一組關鍵字｛179,208,306,093,859,

第一趟分配對最低位關鍵字(個位數)進行,改變記錄的指針值將文件中的記錄分配至10個隊列(桶)中去,每個隊列中的記錄關鍵字的個位數均相等，如圖(a)所示,其中f[i]和e[i]分別為第i個隊列的頭指針和尾指針;第一趟收集是改變所有非空隊尾記錄的指針域,令其指向下一個非空隊列的隊頭記錄,重新將10個隊列中的記錄鏈成一個鏈表文件:E(9)E(8)E(7)E(6)E(5)E(4)E(3)E(2)E(1)E(0)末尾指針前沿指針009859179(a)第一趟分配之后F(9)F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)F(8)208306055984093271033(b)第一趟收集后的鏈式271306984179208033055859093009179984093009005306859271208033第一趟分配對最低位關鍵字(個位數)進行,改變記錄的指306859033179271009055984208093(d)第二趟收集后的鏈式

第二趟分配,第二趟收集及第三趟分配和第三趟收集分別是對十位數和百位數進行的,其過程和個位數相同,如圖(c)所示,至此,排序完畢。若想從大到小排序,分配的過程與上述相同,收集的過程是從第e[9]隊列向第e[0]方向收集。E(9)E(8)E(7)E(6)E(5)E(4)E(3)E(2)E(1)E(0)末尾指針009208306前沿指針F(9)(c)第二趟分配之后F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)F(8)984093055033859271179271306984179208033055859093009306859033179271009055984208093E(9)E(8)E(7)E(6)E(5)E(4)E(3)E(2)E(1)E(0)末尾指針093055033(e)第三趟分配之后前沿指針F(9)F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)F(8)208179271009306984859009208093306271055179859033984(f)第三趟收集后的有序文件306859033179271009055984208093E(9)E(8)E(7)E(6)E(5)E(4)E(3)E(提醒注意：１．“分配”和“收集”的實際操作僅為修改鏈表中的指針和設置隊列的頭、尾指針；２．為查找使用，該鏈表尚需應用算法Arrange將它調整為有序表。提醒注意：NorthChinaElectricPowerUniversity基數排序的算法簡單描述如下：數據類型定義如下：#defineMAX_NUM_OF_KEY8//關鍵字項數（位數）的最大值#defineRADIX10#defineMAX_SPACE10000typedefstruct{KeysTypekeys[MAX_NUM_OF_KEY];//關鍵字InfoTypeotheritems;//其他數據項intnext;}SLCell;//靜態(tài)鏈表的結點類型typedefstruct{SLCellr[MAX_SPACE];//靜態(tài)鏈表的可利用空間，r[0]為頭結點intkeynum;//記錄的當前關鍵字個數intrecnum;//靜態(tài)鏈表的當前長度}SLList;//靜態(tài)鏈表的類型typedefintArrType[RADIX];//指針數組類型NorthChinaElectricPowerUniNorthChinaElectricPowerUniversityvoidDistribute(SLCell&r,inti,ArrType&f,ArrType&e){/*靜態(tài)鏈表L的r域中記錄已按（keys[0],…,keys[i-1]）有序。本算法按第i個關鍵字keys[i]建立RADIX個子表，使同一子表中記錄的keys[i]相同。f[0‥RADIX-1]和e[0‥RADIX-1]分別指向各子表中第一個和最后一個記錄。*/for(j=0;j<RADIX-1;j++)f[j]=0;//各子表初始化為空表for(p=r[0].next;p;p=r[p].next){j=ord(r[p].keys[i]);//ord將記錄中第i個關鍵字映射到[0‥RADIX-1]if(!f[j])f[j]=p;elser[e[j]].next=p;e[j]=p;//將p所