數(shù)據(jù)結(jié)構(gòu)第10章內(nèi)排序

第10章內(nèi)排序10.6基數(shù)排序本章小結(jié)10.1排序的基本概念10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.7各種內(nèi)排序方法的比較和選擇110.1排序的基本概念

所謂排序,就是要整理表中的記錄,使之按關(guān)鍵字遞增(或遞減)有序排列。其確切定義如下：輸入：n個記錄,R0,R1,…,Rn-1,其相應(yīng)的關(guān)鍵字分別為k0,k1,…,kn-1。輸出：Ri0,Ri1,…,Rin-1,使得ki0≤ki1≤…≤kin-1(或ki0≥ki1≥…≥kin-1)。2

當(dāng)待排序記錄的關(guān)鍵字均不相同時,排序的結(jié)果是惟一的,否則排序的結(jié)果不一定惟一。如果待排序的表中,存在有多個關(guān)鍵字相同的記錄,經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變,則稱這種排序方法是穩(wěn)定的；反之,若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化,則稱這種排序方法是不穩(wěn)定的。在排序過程中,若整個表都是放在內(nèi)存中處理,排序時不涉及數(shù)據(jù)的內(nèi)、外存交換,則稱之為內(nèi)排序；反之,若排序過程中要進行數(shù)據(jù)的內(nèi)、外存交換,則稱之為外排序。3待排序的順序表類型的類型定義如下：

typedefintKeyType;/*定義關(guān)鍵字類型*/typedefstruct /*記錄類型*/{ KeyTypekey;/*關(guān)鍵字項*/InfoTypedata;/*其他數(shù)據(jù)項,類型為InfoType*/}RecType; /*排序的記錄類型定義*/RecTypeR[N];數(shù)組R中存放著待排序的記錄410.2插入排序

插入排序的基本思想是：每次將一個待排序的記錄,按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子表中的適當(dāng)位置,直到全部記錄插入完成為止。三種插入排序方法：

(1)直接插入排序

(2)二分插入排序

(2)希爾排序。510.2.1直接插入排序

假設(shè)待排序的記錄存放在數(shù)組R[0..n-1]中,排序過程的某一中間時刻,R被劃分成兩個子區(qū)間R[0..i-1]和R[i..n-1],其中：前一個子區(qū)間是已排好序的有序區(qū),后一個子區(qū)間則是當(dāng)前未排序的部分,不妨稱其為無序區(qū)。直接插入排序的基本操作是將當(dāng)前無序區(qū)的第1個記錄R[i]插入到有序區(qū)R[0..i-1]中適當(dāng)?shù)奈恢蒙?使R[0..i]變?yōu)樾碌挠行騾^(qū)。這種方法通常稱為增量法,因為它每次使有序區(qū)增加1個記錄。6例49386597761327i=2

(3849)6597761327i=3

(384965)97761327i=4

(38496597)761327i=5

(3849657697)1327i=6

(133849657697)27i=1()(133849657697)27jjjjjj977665493827(13273849657697)排序結(jié)果：

01234567voidInsertSort(RecTypeR[],intn)/*對R[0..n-1]按遞增有序進行直接插入排序*/{inti,j; RecTypetemp;for(i=1;i<n;i++){temp=R[i]; j=i-1;/*從右向左在有序區(qū)R[0..i-1]找R[i]的插入位置*/while(j>=0&&temp.key<R[j].key){R[j+1]=R[j];/*將關(guān)鍵字大于R[i].key的記錄后移*/j--; }R[j+1]=temp;/*在j+1處插入R[i]*/}}810.2.2二分插入排序由于插入排序是在一個有序表中進行查找和插入，若查找時采用二分查找方法，則直接插入排序就變成了二分插入排序。9voidInsertSort1(RecTypeR[],intn){inti,j,low,high,mid; RecTypetemp;for(i=1;i<n;i++){temp=R[i];low=0;high=i-1;while(low<=high){mid=(low+high)/2;if(temp.key<R[mid].key)high=mid-1;elselow=mid+1;} for(j=i-1;j>=high+1;j--)R[j+1]=R[j];/*將關(guān)鍵字大于R[i].key的記錄后移*/

R[high+1]=temp;

}}1010.2.3希爾排序

希爾排序也是一種插入排序方法,實際上是一種分組插入方法。其基本思想是：先取定一個小于n的整數(shù)d1作為第一個增量,把表的全部記錄分成d1個組,所有距離為d1的倍數(shù)的記錄放在同一個組中,在各組內(nèi)進行直接插入排序；然后,取第二個增量d2(＜d1),重復(fù)上述的分組和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有記錄放在同一組中進行直接插入排序為止。一趟分組：49

38

65

97

76

13

27

48

55

4先取組數(shù)d1=5(分5組）11取d3=1(1組）三趟分組：134

4838

274955659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76一趟分組：49

38

65

97

76

13

27

48

55

4取d2=3（分3組）二趟分組：13

27

48

55

4

49

38

65

97

76先取組數(shù)d1=5(分5組）12voidShellSort(RecTypeR[],intn)/*希爾排序算法*/{inti,j,d;RecTypetemp;d=n/2; /*d取初值n/2*/while(d>0){for(i=d;i<n;i++)/*將R[d..n-1]分別插入各組當(dāng)前有序區(qū)*/{j=i-d; while(j>=0&&R[j].key>R[j+d].key) {temp=R[j];/*R[j]與R[j+d]交換*/ R[j]=R[j+d];R[j+d]=temp; j=j-d; }}d=d/2; /*遞減增量d*/}}13

例10.2設(shè)待排序的表有10個記錄,其關(guān)鍵字分別為{9,8,7,6,5,4,3,2,1,0}。說明采用希爾排序方法進行排序的過程。14子序列的構(gòu)成不是簡單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列希爾排序可提高排序速度分組后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了關(guān)鍵字較小的記錄跳躍式前移，在進行最后一趟增量為1的插入排序時，序列已基本有序平均時間復(fù)雜度：與每趟的增量有關(guān)如：

d[t]={n/2,n/4,…,1}O(n1.5)希爾排序是不穩(wěn)定的最后一個增量值必須為1希爾排序特點1510.3交換排序

交換排序的基本思想：兩兩比較待排序記錄的關(guān)鍵字,發(fā)現(xiàn)兩個記錄的次序相反時即進行交換,直到?jīng)]有反序的記錄為止。

兩種交換排序:(1)冒泡排序

(2)快速排序1610.3.1冒泡排序

冒泡排序的基本思想是：

通過無序區(qū)中相鄰記錄關(guān)鍵字間的比較和位置的交換,使關(guān)鍵字最小的記錄如氣泡一般逐漸往上“漂浮”直至“水面”。整個算法是從最下面的記錄開始,對每兩個相鄰的關(guān)鍵字進行比較,且使關(guān)鍵字較小的記錄換至關(guān)鍵字較大的記錄之上,使得經(jīng)過一趟冒泡排序后,關(guān)鍵字最小的記錄到達最上端,接著,再在剩下的記錄中找關(guān)鍵字次小的記錄,并把它換在第二個位置上。依次類推,一直到所有記錄都有序為止。17例4938659776132730

初始關(guān)鍵字1327

4938

65977630

第二趟1327304938659776

第三趟13273038

49657697

第四趟12345678從下往上掃描1349386597762730第一趟18voidBubbleSort(RecTypeR[],intn){inti,j; RecTypetemp;for(i=0;i<n-1;i++){for(j=n-1;j>i;j--) /*比較找本趟最小關(guān)鍵字的記錄*/if(R[j].key<R[j-1].key)//相鄰記錄的比較

{ temp=R[j];/*R[j]與R[j-1]進行交換*/ R[j]=R[j-1]; R[j-1]=temp; }}}19

例10.3設(shè)待排序的表有10個記錄,其關(guān)鍵字分別為{9,8,7,6,5,4,3,2,1,0}。說明采用冒泡排序方法進行排序的過程。20

在有些情況下,在第i(i＜n-1)趟時已排好序了,但仍執(zhí)行后面幾趟的比較。實際上,一旦算法中某一趟比較時不出現(xiàn)記錄交換,說明已排好序了,就可以結(jié)束本算法。為此,改進冒泡排序算法如下：

voidBubbleSort(RecTypeR[],intn){inti,j,exchange;RecTypetemp;for(i=0;i<n-1;i++){exchange=0; for(j=n-1;j>i;j--) /*比較,找出最小關(guān)鍵字的記錄*/if(R[j].key<R[j-1].key) {temp=R[j];R[j]=R[j-1];R[j-1]=temp;

exchange=1; } if(exchange==0)return;/*中途結(jié)束算法*/}}21空間復(fù)雜度：S(n)=O(1)算法評價時間復(fù)雜度最好情況（正序）：只需一趟掃描即可比較次數(shù)：n-1移動次數(shù)：0最壞情況（逆序）比較次數(shù)：移動次數(shù)：T(n)=O(n2)22起泡排序：比較和交換在相鄰單元中進行，移動幅度僅一個單元，致使比較和移動次數(shù)較多；每經(jīng)過一趟起泡，無序序列的長度只縮小1。設(shè)想：若能在經(jīng)過一趟排序，使無序序列的長度縮小一半，則必能加快排序的速度。2310.3.2快速排序

快速排序是由冒泡排序改進而得的,它的基本思想是：在待排序的n個記錄中任取一個記錄(通常取第一個記錄，稱為基準(zhǔn)記錄),把該記錄放入適當(dāng)位置后,數(shù)據(jù)序列被此記錄劃分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的記錄放置在前一部分,所有比它大的記錄放置在后一部分,并把該記錄排在這兩部分的中間(稱為該記錄歸位),這個過程稱作一趟快速排序。之后對所有的兩部分分別重復(fù)上述過程,直至每部分內(nèi)只有一個記錄為止。簡而言之,每趟使表的第一個元素放入適當(dāng)位置,將表一分為二,對子表按遞歸方式繼續(xù)這種劃分,直至劃分的子表長為1。24快速排序過程例如:初始關(guān)鍵字序列

5，6，3，1，2，7R[]:012345選第一個元素為基準(zhǔn)元素第一趟快速排序：（2，1，3），5，（6，7）第二趟快速排序：（1），2，（3），5，6，（7）i:基準(zhǔn)位置[0..i-1][i+1..n-1][i]結(jié)束條件：待排區(qū)間只有一個記錄或無記錄R[]:012345一次劃分25

初始關(guān)鍵字：4938659776132750ij基準(zhǔn)元素temp=49ji

完成一趟排序：(273813)49(76976550)分別進行快速排序：(13)27(38)49(5065)76(97)快速排序結(jié)束：13273849506576974927ijijij4965ji1349ij4997ij調(diào)整過程中的基準(zhǔn)位置并不重要，因此，為了減少記錄的移動次數(shù)，應(yīng)先將基準(zhǔn)記錄“移出”，待求得基準(zhǔn)記錄應(yīng)在的位置之后(此時i=j),再將基準(zhǔn)記錄歸位。一趟劃分實現(xiàn)過程26voidQuickSort(RecTypeR[],ints,intt)/*對R[s]至R[t]的元素進行快速排序*/{inti=s,j=t; RecTypetemp;if(s<t)/*區(qū)間內(nèi)至少存在一個元素的情況*/{ temp=R[s]; /*用區(qū)間的第1個記錄作為基準(zhǔn)*/ while(i!=j) /*從兩端交替向中間掃描,直至i=j為止*/ {while(j>i&&R[j].key>temp.key)j--; if(i<j)/*表示找到這樣的R[j],R[i]、R[j]交換*/ {R[i]=R[j];i++;}while(i<j&&R[i].key<temp.key)i++; if(i<j)/*表示找到這樣的R[i],R[i]、R[j]交換*/ {R[j]=R[i];j--;} } R[i]=temp;QuickSort(R,s,i-1);/*對左區(qū)間遞歸排序*/QuickSort(R,i+1,t);/*對右區(qū)間遞歸排序*/}}劃分27

例10.4設(shè)待排序的表有10個記錄,其關(guān)鍵字分別為{6,8,7,9,0,1,3,2,4,5}。說明采用快速排序方法進行排序的過程。28算法評價時間復(fù)雜度最好情況（每次總是選到中間值作基準(zhǔn)）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作基準(zhǔn)）T(n)=O(n2)空間復(fù)雜度：需?？臻g以實現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n)平均：T(n)=O(nlog2n)2910.4選擇排序

選擇排序的基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄,順序放在已排好序的子表的最后,直到全部記錄排序完畢。

兩種選擇排序方法：

(1)直接選擇排序(或稱簡單選擇排序)(2)堆排序3010.4.1直接選擇排序

直接選擇排序的基本思想是：第i趟排序開始時,當(dāng)前有序區(qū)和無序區(qū)分別為R[0..i-1]和R[i..n-1](0≤i＜n-1),該趟排序則是從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄R[k],將它與無序區(qū)的第1個記錄R[i]交換,使R[0..i]和R[i+1..n-1]分別變?yōu)樾碌挠行騾^(qū)和新的無序區(qū)。

因為每趟排序均使有序區(qū)中增加了一個記錄,且有序區(qū)中的記錄關(guān)鍵字均不大于無序區(qū)中記錄的關(guān)鍵字,即第i趟排序之后R[0..i]的所有關(guān)鍵字小于等于R[i+1..n-1]中的所有關(guān)鍵字,所以進行n-1趟排序之后有R[0..n-2]的所有關(guān)鍵字小于等于R[n-1].key,也就是說,經(jīng)過n-1趟排序之后,整個表R[0..n-1]遞增有序。31例初始：[49386597761327]kjjjjjjkki=01349一趟：13

[386597764927]i=1kkjjjjj2738二趟：13

27

[6597764938]三趟：13

27

38[97764965]四趟：13

27

38

49[769765]五趟：13

27

38

49

65

[9776]六趟：13

27

38

49

65

76[97]排序結(jié)束：13

27

38

49

65

76

97實現(xiàn)過程32voidSelectSort(RecTypeR[],intn){inti,j,k;RecTypetemp;for(i=0;i<n-1;i++) /*做第i趟排序*/{k=i; for(j=i+1;j<n;j++)/*在[i..n-1]中選key最小的R[k]*/ if(R[j].key<R[k].key) k=j;/*k記下的最小關(guān)鍵字所在的位置*/ if(k!=i)/*交換R[i]和R[k]*/ {temp=R[i];R[i]=R[k];R[k]=temp;}}}33

例10.5設(shè)待排序的表有10個記錄,其關(guān)鍵字分別為{6,8,7,9,0,1,3,2,4,5}。說明采用直接選擇排序方法進行排序的過程。34算法評價時間復(fù)雜度記錄移動次數(shù)最好情況：0(已正序的紀(jì)錄不用移動)最壞情況：3(n-1)每趟均需交換比較次數(shù)：空間復(fù)雜度：S(n)=O(1)T(n)=O(n2)3510.4.2堆排序堆排序是一樹形選擇排序,它的特點是,在排序過程中,將R[1..n]看成是一棵完全二叉樹的順序存儲結(jié)構(gòu),利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系,在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。

36堆的定義:堆是滿足下列性質(zhì)的數(shù)列{k1,k2,…，kn}：或若將此數(shù)列看成是一棵順序存儲的完全二叉樹:則堆或是空樹或是滿足下列特性的完全二叉樹：根結(jié)點的值小于(或大于)左/右子樹根結(jié)點的值。分別稱作小根堆或大根堆。例（96，83，27，38，11，9）例（13，38，27，50，76，65，49，97）962791138831327384965765097堆頂元素k1必為序列中n個元素的最小值或最大值3796832738119012345696279113883初始大根堆存儲結(jié)構(gòu)內(nèi)存中38962791138839279611388383279611389832796119381127968393811279683938382796839119279683381127996833811調(diào)整實現(xiàn)過程將根結(jié)點值與左、右子樹的根結(jié)點值進行比較，并與其中大者進行交換；重復(fù)上述操作，直至葉子結(jié)點；得到新大根堆；392799683381192796833811112796833899279683381191127388396012345640

堆排序的關(guān)鍵是構(gòu)造堆,這里采用篩選算法建堆：假若完全二叉樹的某一個結(jié)點i對于它的左子樹、右子樹已是堆,接下來需要將R[2i].key與R[2i+1].key之中的最大者與R[i].key比較,若R[i].key較小則交換,這有可能破壞下一級的堆。于是繼續(xù)采用上述方法構(gòu)造下一級的堆。直到完全二叉樹中結(jié)點i構(gòu)成堆為止。對于任意一棵完全二叉樹,從i=n/2到1,反復(fù)利用上述思想建堆。大者“上浮”,小者被“篩選”下去。其調(diào)整堆的算法sift()如下：41voidsift(RecTypeR[],intlow,inthigh)//對R[low..high]進行篩選{inti=low,j=2*i;/*R[j]是R[i]的左孩子*/

RecTypetemp=R[i];while(j<=high){if(j<high&&R[j].key<R[j+1].key)j++;if(temp.key<R[j].key){R[i]=R[j];/*將R[j]調(diào)整到雙親結(jié)點位置上*/ i=j; /*修改i和j值,以便繼續(xù)向下篩選*/ j=2*i; } elsebreak; /*篩選結(jié)束*/}R[i]=temp; /*被篩選結(jié)點的值放入最終位置*/}42

有了調(diào)整堆的函數(shù),利用該函數(shù),將已有堆中的根與最后一個葉子交換,進一步恢復(fù)堆,直到一棵樹只剩一個根為止。實現(xiàn)堆排序的算法如下：voidHeapSort(RecTypeR[],intn)//對R[1..n]做堆排序{inti; RecTypetemp;for(i=n/2;i>=1;i--) /*循環(huán)建立初始堆*/sift(R,i,n);for(i=n;i>=2;i--)/*進行n-1次循環(huán),完成推排序*/{ temp=R[1];/*將第一個元素同當(dāng)前區(qū)間內(nèi)R[1]對換*/ R[1]=R[i];R[i]=temp; sift(R,1,i-1);/*篩選R[1]結(jié)點,得到i-1個結(jié)點的堆*/}}43

例10.6設(shè)待排序的表有10個記錄,其關(guān)鍵字分別為{6,8,7,9,0,1,3,2,4,5}。說明采用堆排序方法進行排序的過程。44堆排序過程：989789989789456656564564563456345622246堆排序的時間復(fù)雜度為O(nlog2n)建初始堆所需比較次數(shù)較多，以后各趟只需對堆頂元素進行篩選，所以堆排序?qū)較大的文件十分有效。4710.5歸并排序

歸并排序是多次將兩個或兩個以上的有序表合并成一個新的有序表。最簡單的歸并是直接將兩個有序的子表合并成一個有序的表。

將兩個有序表直接歸并為一個有序表的算法Merge()：480123 45674913659776780R0123 4567R1ijkMERGE(rectypeR[],intlow,intmid,inthigh)lowmidmid+1high7jk13ik49ik65ik76jk494913659776780R0123 4567R1ijk713496576800123 4567504913659776780R0123 4567R1ijk71349657680將剩余的R[i..mid]復(fù)制到R10123 4567lowmidmid+1high514913659776780R0123 4567R1ijk71349657680970123 4567lowmidmid+1high52voidMerge(RecTypeR[],intlow,intmid,inthigh){RecType*R1;inti=low,j=mid+1,k=0;/*k是R1的下標(biāo),i、j分別為第1、2段的下標(biāo)*/R1=(RecType*)malloc((high-low+1)*sizeof(RecType));while(i<=mid&&j<=high) if(R[i].key<=R[j].key)/*將第1段中的記錄放入R1中*/ {R1[k]=R[i];i++;k++;} else/*將第2段中的記錄放入R1中*/ {R1[k]=R[j];j++;k++;}有序子序列R[low..mid]有序子序列R[mid+1..high]

有序序列R1[low..high]53 while(i<=mid)/*將第1段余下部分復(fù)制到R1*/ {R1[k]=R[i];i++;k++;}while(j<=high)/*將第2段余下部分復(fù)制到R1*/ {R1[k]=R[j];j++;k++;}for(k=0,i=low;i<=high;k++,i++)/*將R1復(fù)制回R中*/ R[i]=R1[k];

free(R1);}54voidMergePass(RecTypeR[],intlength,intn){inti;for(i=0;i+2*length-1<n;i=i+2*length)/*歸并length長的兩相鄰子表*/ Merge(R,i,i+length-1,i+2*length-1);if(i+length-1<n)/*余下兩個子表,后者長度小于length*/ Merge(R,i,i+length-1,n-1); /*歸并這兩個子表*/}MergePass()實現(xiàn)了一趟歸并

55二路歸并排序算法如下：voidMergeSort(RecTypeR[],intn) /*自底向上的二路歸并算法*/{ intlength; for(length=1;length<n;length=2*length) MergePass(R,length,n);}56

例10.7設(shè)待排序的表有8個記錄,其關(guān)鍵字分別為{18,2,20,34,12,32,6,16}。說明采用歸并排序方法進行排序的過程。57歸并排序的時間復(fù)雜度為O(nlog2n)5810.6基數(shù)排序前面所討論的排序算法均是基于關(guān)鍵字之間的比較來實現(xiàn)的,而基數(shù)排序是通過“分配”和“收集”過程來實現(xiàn)排序,是一種借助于多關(guān)鍵字排序的思想對單關(guān)鍵字排序的方法。59

一般地,記錄R[i]的關(guān)鍵字R[i].key是由d位數(shù)字組成,即kd-1kd-2…k0,每一個數(shù)字表示關(guān)鍵字的一位,其中kd-1為最高位,k0是最低位,每一位的值都在0≤ki＜r范圍內(nèi),其中,r稱為基數(shù)。例如,對于二進制數(shù)r為2,對于十進制數(shù)r為10?；鶖?shù)排序有兩種：最低位優(yōu)先和最高位優(yōu)先。最低位優(yōu)先的過程是：先按最低位的值對記錄進行排序,在此基礎(chǔ)上,再按次低位進行排序,依此類推。由低位向高位,每趟都是根據(jù)關(guān)鍵字的一位并在前一趟的基礎(chǔ)上對所有記錄進行排序,直至最高位,則完成了基數(shù)排序的整個過程。

60

以r為基數(shù)的最低位優(yōu)先排序的過程是：假設(shè)線性表由結(jié)點序列a0,a1,…,an-l構(gòu)成,每個結(jié)點aj的關(guān)鍵字由d元組組成,其中0≤kji≤r-1(0≤j＜n,0≤i≤d-1)。在排序過程中,使用r個隊列Q0,Q1,…,Qr-1。排序過程如下：對i=0,1,…,d-1,依次做一次“分配”和“收集”(其實就是一次穩(wěn)定的排序過程)。分配：開始時,把Q0,Q1,…,Qr-1各個隊列置成空隊列,然后依次考察線性表中的每一個結(jié)點aj(j=0,1,…,n-1),如果aj的關(guān)鍵字k=k,就把aj放進Qk隊列中。收集：把Q0,Q1,…,Qr-1各個隊列中的結(jié)點依次首尾相接,得到新的結(jié)點序列,從而組成新的線性表。61#defineMAXE20 /*線性表中最多元素個數(shù)*/#defineMAXR10 /*基數(shù)的最大取值*/#defineMAXD8 /*關(guān)鍵字位數(shù)的最大取值*/typedefstructnode{chardata[MAXD]; /*記錄的關(guān)鍵字定義的字符串*/structnode*next;}RecType;62voidRadixSort(RecType*&p,intr,intd)/*p為待排序序列鏈表指針,r為基數(shù),d為關(guān)鍵字位數(shù)*/{ RecType*head[MAXR],*tail[MAXR],*t;/*定義各鏈隊的首尾指針*/ inti,j,k; for