1第十章內部排序本章目標熟練掌握各內部排序方法的基本思想；理解排序方法“穩定”和“不穩定”的含義。掌握排序過程和實現算法；掌握各種排序方法時間復雜度的分析方法；了解各種排序方法的特點（比較和選擇）。10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數排序10.7

各種內部排序方法的比較10.1概述所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。各科成績表；獎學金評定綜合分；...？什么是排序？為什么排序？如何排序？內部排序外部排序 將欲處理的記錄全部存放到內存中排序，數據可被隨機存取插入式排序交換式排序選擇式排序待排序的記錄太多，不能同時存放內存中，排序過程需要借助外存（比如：硬盤）來完成，記錄需要在內存和外存間移動。

排序的分類歸并排序基數排序比較標準穩定性不穩定性 排序過后能使關鍵字相等的記錄保持原順序中的相對位置 排序過后不能使關鍵字相等的記錄保持原順序中的相對位置49325649272732494956時間復雜度空間復雜度穩定性排序算法的基本操作大多數排序算法都有兩個基本的操作：(1)比較兩條記錄的關鍵字(排序碼)大小；(2)移動記錄本身或改變指向記錄的指針。

注意：

第(2)種基本操作的實現依賴于待排序記錄的存儲方式。據此可分為靜態排序和動態排序。#defineMAXSIZE20

//順序表的最大長度typedefintKeyType;

//定義關鍵字類型為整數類型typedefstruct

{

KeyTypekey;

//關鍵字項

InfoTypeotherinfo;

//其他數據項}RedType；

//記錄類型typedefstruct{

RedTyper[MAXSIZE+1];

//r[0]閑置或作哨兵單元

intlength;

//順序表的當前長度}SqList;

//順序表類型待排記錄的數據類型--順序存儲結構10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數排序10.7

各種內部排序方法的比較10.2

插入排序

2.

折半插入排序3.2-路插入排序4.表插入排序

1.直接插入排序5.希爾排序基本思想：（1）排序過程分步完成；（2）每步將一個待排序的記錄，按其關鍵字大小，插入到前面已經排好序的一組記錄（有序序列）的適當位置上；（3）通過若干步，便可將所有記錄全部插入，從而完成排序。通常，將這里的每個步驟稱為“趟”。1.直接插入排序基本操作：將一個待排序的記錄按其關鍵字的大小插入到前面已排好序的有序序列中。有序序列無序序列125786309412567830941.直接插入排序有序序列從只有一個記錄開始逐次增大；當插入第i(i>=2)個記錄r[i]時，前面的r[1],r[2],…,r[i-1]已經排好序。這時，用r[i]的關鍵字與r[i-1],r[i-2],…的關鍵字依次進行比較，找到插入位置后將r[i]插入，原來位置上及以后的所有記錄順次向后移動；當有序序列大小最終和原始記錄集大小相同時排序完畢。1.直接插入排序[64]789624[564]89624[5764]624[576489]24[5676489][567246489]5789624初始序列:第一趟排序:第二趟排序:第三趟排序:第四趟排序:第五趟排序:Temp6j89j64j7j61.直接插入排序算法:voidInsertSort（SqList&L）{for(i=2;i<=L.length;++i)ifLT(L.r[i].key,L.r[i-1].key){

L.r[0]=L.r[i];for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];

L.r[j+1]=L.r[0];}}1.直接插入排序最壞情況下（逆序）：時間復雜度為O(n2)比較次數：移動次數：2)1)(2(1-+=?=nn

(i+1)n-1i2)1)(4(2-+=+?nnin-11=i）（最好情況下（正序）：

比較次數：n-1移動次數：0時間復雜度為O(n)性能分析:空間性能：需要一個記錄的輔助空間。直接插入排序算法是一種穩定的排序算法。特點：簡單、容易實現，適用于待排序記錄基本有序或待排序記錄較少的情形。2.折半插入排序[5764]624[576489]24896第二次排序:第三次排序:Tfmp689647low6基本思想:在查找插入位置時,使用折半查找算法。mhigh2.折半插入排序算法:voidBInsertSort(SqList&L){

for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i-1;

while(low<=high){m=(low+high)/2;

ifLT(L.r[0].key,L.r[m].key)high=m-1;

elselow=m+1;}

for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];L.r[high+1]=L.r[0];}//for}//BInsertSort2.折半插入排序穩定空間代價：O(1)時間代價：比較次數與待排記錄的初始順序無關，只依賴記錄個數插入每個記錄需要O(log2i)次比較

最多移動i+1次，最少2次（臨時記錄）

最佳情況下總時間代價為O(nlog2n)，最差和平均情況下仍為O(n2)3.2-路插入排序基本思想：增設同類型數組d,視為循環向量。以d[1]為中心，原數列中比d[1]小的往前插，比d[1]大的往后插原數列：4938659776132749d數組：49d1firstfinal38first6597final76final13first27first9749finalvoidTwoWaySort(SqList&L){intfirst=1,final=1,i,j;RedTyped[MAXSIZE+1];//輔助存儲d[1].key=L.r[1].key;for(i=2;i<=L.length;i++){if(L.r[i].key>=d[1].key){//插入d1后for(j=final;d[j].key>L.r[i].key;j--)d[j+1].key=d[j].key;d[j+1].key=L.r[i].key;final++;}else{//插入d1前if(first==1){first=MAXSIZE-1;d[first].key=L.r[i].key;}else{for(j=first;d[j].key<L.r[i].key&&d[j].key&&j<MAXSIZE;j++)d[j-1].key=d[j].key;d[j-1].key=L.r[i].key;first--;}}}//forfor(i=first,j=1;L.r[j].key;i=i%(MAXSIZE-1)+1,j++)L.r[j].key=d[i].key;//將序列復制回去}4.希爾排序

基本思想：把待排序的數據元素分成若干個小組，對同一小組內的數據元素用直接插入法排序；小組的個數逐次縮小；當完成了所有數據元素都在一個組內的排序后排序過程結束。希爾排序又稱作縮小增量排序。

4.希爾排序653425871238564614779223566514257787382356341477122365462587923865771234561214653423774625879238121423253438465665778792結果序列4.希爾排序voidShellInsert(SqList&L,intdk)

{

//1.前后記錄位置的增量是dk,而不是1;

//2.r[0]只是暫存單元,不是哨兵。當j<=0時,插入位置已找到。

for(i=dk+1;i<=L.length;++i)

if(LT(L.r[i].key,L.r[i-dk].key)){//需將L.r[i]插入有序增量子表L.r[0]=L.r[i];//暫存在L.r[0]for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//記錄后移，查找插入位置L.r[j+dk]=L.r[0];//插入}}4.希爾排序voidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]對順序表L作希爾排序。

for(k=0;k<t;++k)

ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}Gap的取法有多種。最初shell提出取gap=n/2，gap=gap/2，直到gap=1。后來knuth提出取gap=gap/3+1。還有人提出都取奇數為好，也有人提出各gap互質為好。10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數排序10.7

各種內部排序方法的比較起泡排序基本思想：設數組a中存放了n個數據元素，循環進行n-1趟如下的排序過程：依次比較相鄰兩個數據元素，若a[i]>a[i+1]，則交換兩個數據元素，否則不交換。當完成一趟交換以后，最大的元素將會出現在數組的最后一個位置。依次重復以上過程，當第n-1趟結束時，整個n個數據元素集合中次小的數據元素將被放置在a[1]中，a[0]中放置了最小的數據元素。起泡排序4938659776132749979797384927137665493849276513493849271349384927133827137676654949382713特點：1.n個數排序共需進行n-1趟比較2.第i趟共需要進行n-i次比較起泡排序的原始算法voidbubble_sort(SqList&L){//將a中整數序列排列成自小至大有序的序列(起泡排序)

for(i=1,i<=L.length-1;++i)for(j=1;j<=L.length-1;++j)if(LT(L.r[j+1].key,L.r[j].key))L.r[j]←→L.r[j+1]；}起泡排序的改進算法（一）voidbubble_sort(SqList&L){//將a中整數序列排列成自小至大有序的序列(起泡排序)for(i=1;i<=L.length-1;++i)for(j=1;j<=L.length-i;++j)if(LT(L.r[j+1].key,L.r[j].key))L.r[j]←→L.r[j+1]}115246175115617524115617524161551724注意第i趟比較了n-i次，則可以有效的較少比較次數問題：剛才的改進算法是否已經最優?起泡排序的改進算法（二）123456789123456789123456789

123456789

分析：因為給定的待排序序列已經是一個正序的序列，經過第一趟的比較以后，已經沒有交換發生，但是算法仍然會繼續執行。解決：添加一個算法的結束條件，即當某一趟排序過程中只有比較而沒有交換的時候，就認定序列已經有序，可以提前結束循環。起泡排序的改進算法（二）voidbubble_sort(SqList&L){//將a中整數序列排列成自小至大有序的序列(起泡排序)for(i=1,chang=TRUE；(i<=L.length-1)&&chang;++i){chang=FALSE;for(j=1;j<L.length-i;++j)if(LT(L.r[j+1].key,L.r[j].key)){L.r[j]

←→L.r[j+1];

change=TRUE;}}}最壞情況（反序）：最好情況（正序）：比較次數：n-1移動次數：0

時間復雜度為O(n)；時間復雜度為O(n2)。比較次數：移動次數：2)1(1-=?=nn(n-i)n-1i2)1(1-=?=n3n3(n-i)n-1i平均情況：時間復雜度為O(n2)。時間性能分析快速排序算法思想：指定樞軸(通常為第一個記錄)通過一趟排序將以樞軸為中心，把待排記錄分割為獨立的兩部分，使得左邊記錄的關鍵字小于樞軸值，右邊記錄的關鍵字大于樞軸值對左右兩部分記錄序列重復上述過程，依次類推，直到子序列中只剩下一個記錄或不含記錄為止。快速排序4938659776132749pivotkey=49lowhigh27low65high13low97highhigh49第一趟結果：[273813]49[76976549]小于49大于等于49快速排序算法

intPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];//用子表的第一個記錄作樞軸記錄pivotkey=L.r[low].key;//樞軸記錄關鍵字

while(low<high){//從表的兩端交替地向中間掃描

while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//將比樞軸記錄小的記錄移到低端

while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];//將比樞軸記錄大的記錄移到高端}L.r[low]=L.r[0];//樞軸記錄到位

returnlow;//返回樞軸位置}快速排序算法

voidQSort(SqList&L,intlow,inthigh){//對順序表L中的//長度大于1

if(low<high){pivotloc=Partition(L,low,high);//將L.r[low..high]一分為二QSort(L,low,pivotloc-1);//對低子表遞歸排序，pivotloc是樞軸位置QSort(L,pivotloc+1,high);//對高子表遞歸排序

}}

voidQuickSort(SqList&L){//對順序表L作快速排序。算法10.8

QSort(L,1,L.length);}算法分析在n個元素的序列中，對一個對象定位所需時間為O(n)。若設t(n)是對n個元素的序列進行排序所需的時間，而且每次對一個對象正確定位后，正好把序列劃分為長度相等的兩個子序列，此時，總的計算時間為：T(n)cn+2t(n/2) //c是一個常數cn+2(cn/2+2t(n/4))=2cn+4t(n/4)2cn+4(cn/4+2t(n/8))=3cn+8t(n/8)………cnlog2n+nt(1)=o(nlog2n)10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數排序10.7

各種內部排序方法的比較直接選擇排序基本思想：從待排序的數據元素集合中選取最小的數據元素并將它與原始數據元素集合中的第一個數據元素交換位置；然后從不包括第一個位置上數據元素的集合中選取最小的數據元素并將它與原始數據元素集合中的第二個數據元素交換位置；如此重復，直到數據元素集合中只剩一個數據元素為止。直接選擇排序149238365497576613727849ki=1jkjjjjkjjk1349直接選擇排序149238365497576613727849i=kjjjjjj1349kk2voidSelectSort(SqList&L){for(inti=1;i<L.length;i++) k=SelectMinKey(L,i);if(i!=k)L.r[i]←→L.r[k];}voidSelectMinKey(SqList&L,constinti){intk=i; for(j=i+1;j<=L.length;j++)if(L.r[j].key<L.r[k].key) k=j;//當前具最小關鍵碼的對象returnk; }直接選擇排序的算法最壞情況：3(n-1)次直接選擇排序算法的性能分析移動次數：最好情況（正序）：0次比較次數：)()1(21211nOnninni=-=-?-=）（簡單選擇排序的時間復雜度為O(n2)。樹形選擇排序排序思想：首先取得n個對象的關鍵碼，進行兩兩比較，得到n/2個比較的優勝者(關鍵碼小者)，作為第一步比較的結果保留下來。然后對這n/2個對象再進行關鍵碼的兩兩比較，…，如此重復，直到選出一個關鍵碼最小的對象為止。133813973865493876131327652749139749387613652749381338651327∞27382738657627279749387613652749382738657627∞13∞38384938657649算法分析除第一次選擇具有最小關鍵碼的對象需要進行n-1次關鍵碼比較外，重構勝者樹選擇具有次小、再次小關鍵碼對象所需的關鍵碼比較次數均為O(log2n)。總關鍵碼比較次數為O(nlog2n)。對象的移動次數不超過關鍵碼的比較次數，故錦標賽排序總的時間復雜度為O(nlog2n)這種排序方法雖然減少了許多排序時間，但是使用了較多的附加存儲。堆排序把待排序的數據元素集合構成一個完全二叉樹結構，則每次選擇出一個最大（或最小）的數據元素設數組a中存放了n個數據元素，數組下標從0開始，如果當數組下標2i+1<n時有：a[i]≥a[2i+1]；如果當數組下標2i+2<n時有：a[i]≥a[2i+2]，則這樣的數據結構稱為最大堆。性質5（2）如果2×i+1<n，則序號為i結點的左孩子結點的序號為2×i+1；如果2×i+1≥n，則序號為i結點無左孩子結點。堆排序(續)設數組a中存放了n個數據元素，數組下標從0開始，如果當數組下標2i+1<n時有：a[i]≤a[2i+1]；如果當數組下標2i+2<n時有：a[i]≤a[2i+2]，則這樣的數據結構稱為最小堆。9683273811091236248547913053堆排序基本思想：以初始關鍵字序列，建立堆；輸出堆頂最小元素；調整余下的元素，使其成為一個新堆；重復2,3步，直到n個元素輸出，得到一個有序序列。關鍵問題：如何由一個無序序列建成一個堆?如何調整余下的元素成為一個新堆?堆調整過程1338277697654949rc=13篩選過程voidHeapAdjust(SqListR[],ints,intm){

//已知R[s..m]中記錄的關鍵字除R[s].key之外均滿足堆的定義，本函數調整R[s]的關鍵字，使R[s..m]成為一個大頂堆rc=R[s];for(j=2*s;j<=m;j*=2){

//沿key較大的孩子結點向下篩選if(j<m&&R[j].key<R[j+1].key)++j;//j為key較大 //的記錄的下標if(rc.key>=R[j].key)break;//rc應插入在位置s上R[s]=R[j];s=j;}R[s]=rc;//插入}

//HeapAdjust建堆過程無序序列建堆過程

方法：從完全二叉樹的最后一個非葉結點

n/2開始，反復調用篩選過程，直到第一個結點，則得到一個堆。建堆算法voidHeapSort(SqListR[],intn){//對記錄序列R[1..n]進行堆排序。

for(i=n/2;i>0;--i)//把R[1..n]建成大頂堆

HeapAdjust(R,i,n);

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

HeapAdjust(R,1,i-1);

}//將R[1..i-1]重新調整為大頂堆}//HeapSort性能分析對深度為k的堆，“篩選”所需進行的關鍵字比較的次數至多為2(k-1);對n個關鍵字，建成深度為h(=log2n+1)的堆，所需進行的關鍵字比較的次數至多為4n;調整“堆頂”n-1次，總共進行的關鍵字比較的次數不超過2(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)因此，堆排序的時間復雜度為O(nlogn)，不穩定。10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數排序10.7

各種內部排序方法的比較歸并排序基本思想：將一個具有n個待排序記錄的序列看成是n個長度為1的有序序列，然后進行兩兩歸并，得到n/2個長度為2的有序序列，再進行兩兩歸并，得到n/4個長度為4的有序序列，……，直至得到一個長度為n的有序序列為止。歸并排序過程<初態>(49)(38)(65)(97)(76)(13)(27)(3849)<第2趟>(38496597)(132776)<第3趟>(13273849657697)<第1趟>(6597)(1376)(27)歸并排序算法voidMerge(RedTypeSR[],RedType&TR[],inti,intm,intn){//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]intj,k,l;for(j=m+1,k=i;i<=m&&j<=n;++k)//將SR中記錄由小到大地并入TRifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];if(i<=m)TR[k…n]=SR[i…m];//將剩余的SR[i..m]復制到TRif(j<=n)TR[k…n]=SR[j…n];//將剩余的SR[j..n]復制到TR}歸并排序算法(續)voidMSort(RedTypeSR[],RedType&TR1[],ints,intt){//將SR[s..t]歸并排序為TR1[s..t]if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//將SR[s..t]平分為SR[s..m]和SR[m+1..t]MSort(SR,TR2,s,m);//遞歸地將SR[s..m]歸并為有序的TR2[s..m]MSort(SR,TR2,m+1,t);//遞歸地將SR[m+1..t]歸并為有序的TR2[m+1..t]Merge(TR2,TR1,s,m,t);//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]}}voidMergeSort(SqList&L){//對順序表L作歸并排序。算法10.14MSort(L.r,L.r,1,L.length);}10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數排序10.7

各種內部排序方法的比較基數排序排序思想：基數排序是按組成關鍵字的各位的值進行分配和收集，與前面介紹的排序方法不同，它無需進行關鍵字之間的比較。設關鍵字有d位，每位的取值范圍為r(稱為基數)，則需要進行d趟分配與收集，需要設立r個隊列。例如，關鍵字是4位字符串，需要26個隊列，4趟分配與收集；關鍵字3位十進制數，需要10個隊列，3趟分配與收集基數排序過程278—109—063—930—589—184—505—269—008—083f[0]f[1]f[2]f[3]

f[4]f[5]f[6]f[7]f[8]f[9]e[0]e[1]e[2]e[3]

e[4]e[5]e[6]e[7]e[8]e[9]278pp109p063p930p589p184p505p269p008p083930—063—083—184—505—278—008—109—589—269505—008—109—930—063—269—278—083—184—589f[0]f[1]f