數(shù)據(jù)結(jié)構(gòu)-合肥工業(yè)大學(xué) 9

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

},其相應(yīng)的關(guān)鍵字為{K1,K2,…，Kn

}，需確定一種排列P(1),P(2),…,P(n),使其相應(yīng)的關(guān)鍵字滿足如下的遞增(或遞減)關(guān)系：KP(1)

≤KP(2)≤KP(3)≤…≤KP(n)即，使上述文件成為一個按其關(guān)鍵字線性有序的文件{RP(1),RP(2),…，RP(n)},這樣一種運算稱為排序。9.1基本概念如果在排序期間具有相同關(guān)鍵字的記錄的相對位置不變，則稱此方法是穩(wěn)定的。排序：排序的穩(wěn)定性：內(nèi)排序插入類排序直接插入排序折半插入排序希爾排序交換類排序冒泡排序快速排序選擇類排序選擇排序堆排序歸并類排序歸并排序其他排序計數(shù)排序基數(shù)排序9.2直接插入排序假設(shè)在排序過程中，記錄序列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]復(fù)制到R[j+1]的位置上。直接插入排序：利用順序查找實現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”的插入排序。注意直接插入排序算法的三個要點：

1.從R[i-1]起向前進行順序查找，監(jiān)視哨設(shè)置在R[0]；

R[0]=R[i]；{設(shè)置“哨兵”}j=i-1;while(R[0].key<R[j].key)j=j-1;{//從后往前找}Return(j+1);{返回R[i]的插入位置為j+1}2.對于在查找過程中找到的那些關(guān)鍵字不小于R[i].key的記錄，并在查找的同時實現(xiàn)記錄向后移動；

while(R[0].key<R[j].key){R[j+1]=R[j];j=j-1;}3.i=2，3，…,n,實現(xiàn)整個序列的排序。排序算法如下：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排序的時間分析：

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

總的說來，直接插入排序所需進行關(guān)鍵字間的比較次數(shù)和記錄移動的次數(shù)均為n2/4，所以直接插入排序的時間復(fù)雜度為O(n2)。“比較”的次數(shù)：“移動”的次數(shù)：

2(n-1)9.3冒泡排序排序算法的思想：比較k1和k2,如果這些關(guān)鍵字的值不符合排序順序,就交換k1和k2；然后對記錄k2和k3,k3和k4等等進行相同的工作。直到kn-1和kn為止,到此得到一個最大(或最小)關(guān)鍵字值存在kn的位置上(通常將此過程叫做一趟)。重復(fù)這個過程,就得到在位置kn-1,kn-2等處的適當記錄,使得所有記錄最終被排好序。

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

因為到第四趟就沒有交換的偶對了,所以整個排序結(jié)束。算法描述如下:voidbubblesort(List

r,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[j]=max;all=〝F〞;}}k--;}while((all==〝T〞)||(k==1)}冒泡排序的結(jié)束條件為：最后一趟沒有進行“交換”。冒泡排序是一種穩(wěn)定的排序算法。時間分析:最好的情況（關(guān)鍵字在記錄序列中順序有序）：只需進行一趟起泡“比較”的次數(shù)：“移動”的次數(shù)：n-10

最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：需進行

n-1趟起泡“比較”的次數(shù)：“移動”的次數(shù)：

NorthChinaElectricPowerUniversity9.4選擇排序基本思想：首先在n個記錄中選擇一個具有最小或最大關(guān)鍵字的記錄，將選出的記錄與記錄集合中的第一個記錄交換位置。然后在r[2]至r[n]中選擇一個最小或最大的值與r[2]交換位置，…，依此類推，直至r[n-1]和r[n]比較完畢。voidslsort(List

r,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指示關(guān)鍵字最小的記錄的序號

if(m!=i){x=r[i];r[i]=r[m];r[m]=x;}}}例關(guān)鍵字序列{055，55，60，13，05，94，17，70},利用選擇排序算法進行排序。關(guān)鍵字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)定算法的復(fù)雜性分析：當選則第一個最小值時需進行n-1次比較，選第二個最小值時需進行n-2次比較，…，選n-1個最小值時需進行n-(n-1)次比較，所以總的比較次數(shù)為(n-1)+(n-2)+…+2+1=n(n-1)/2故排序n個記錄需要時間為O(n2)。由于執(zhí)行一次交換，需三次移動記錄，最多交換n-1次，故最多移動次數(shù)為3(n-1)NorthChinaElectricPowerUniversity9.5快速排序快速排序又稱分劃交換排序，設(shè)輸入文件有n個記錄R1,R2,…,Rn

,它們對應(yīng)的關(guān)鍵字是k1,k2,…,kn

。該方法先取序列中任一關(guān)鍵字K(通常取第一個)，然后用K從兩頭到中間進行比較/交換，就能形成一個分劃：凡是小于等于K的被移到左邊，凡是大于K的被移到右邊。1.快速排序的定義NorthChinaElectricPowerUniversity2.快速排序步驟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)重復(fù)調(diào)用上述過程，直到將整個集合排序好為止。例:初始關(guān)鍵字[4655134294051770]將46→xij第一次交換后[

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

134294055570]j第四次交換后[1705134294

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

例:初始關(guān)鍵字[4655134294051770]接上例voidqksort(Listr,intL,intP)//將r[L]至r[P]進行排序{}//qksort

3.快速排序算法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--;//一趟快排結(jié)束，將x移至正確位置

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

//反復(fù)排序前一部分

if(i<P)qksort(r,i,P);

//反復(fù)排序后一部分NorthChinaElectricPowerUniversity快速排序是目前內(nèi)部排序中最快的方法。若關(guān)鍵字的分布式均勻的，可以粗略的認為每次劃分都把文件分成長度相等的兩個文件。4.快速排序算法的性能分析但如果原來的文件是有次序的，時間復(fù)雜性為O(n2)。因此，快速排序偏愛一個無次序的文件。令T(n)為分類n個記錄所需之比較次數(shù),設(shè)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)5.快速排序算法的穩(wěn)定性分析例：關(guān)鍵字序列{5，2，02}ij第一次交換后[02202]5→xj第二次交換后[022]02

j至此，完成排序，序列為{02,2,5}第一次交換[022]5ji02→x第一趟無交換

25第二趟5不穩(wěn)定i02例K={46,79,56,38,40,84}

（1）它的初始堆是：

（2）快速排序第一趟結(jié)果：（1）467956384084384056794684（2）40，38，46，56，79，84NorthChinaElectricPowerUniversity各種排序方法的綜合比較一、時間性能

按平均的時間性能來分，有三類排序方法：時間復(fù)雜度為O(nlogn)的方法有：快速排序、堆排序和歸并排序；時間復(fù)雜度為O(n2)的有：直接插入排序、起泡排序和簡單選擇排序；時間復(fù)雜度為O(n)的排序方法只有基數(shù)排序。2.當待排記錄序列按關(guān)鍵字順序有序時:

直接插入排序和起泡排序能達到O(n)的時間復(fù)雜度;而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為O(n2)，因此是應(yīng)該盡量避免的情況。3.簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。NorthChinaElectricPowerUniversity二