數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社第十章排序課件

三、表插入排序?yàn)榱藴p少在排序過程中進(jìn)行的“移動”記錄的操作，必須改變排序過程中采用的存儲結(jié)構(gòu)。利用靜態(tài)鏈表進(jìn)行排序，并在排序完成之后，一次性地調(diào)整各個記錄相互之間的位置，即將每個記錄都調(diào)整到它們所應(yīng)該在的位置上。2/11/20231算法中使用了三個指針：其中：p指示第i個記錄的當(dāng)前位置

i指示第i個記錄應(yīng)在的位置

q指示第i+1個記錄的當(dāng)前位置如何在排序之后調(diào)整記錄序列？2/11/20232voidArrange(SLinkListType&SL){p=SL.r[0].next;//p指示第一個記錄的當(dāng)前位置for(i=1;i<n;++i){

while(p<i)p=SL.r[p].next;//第i個記錄在SL中的當(dāng)前位置應(yīng)不小于i，找到第i個記錄，//并用p指示其在SL中當(dāng)前位置

q=SL.r[p].next;

//q指示尚未調(diào)整的表尾if(p!=i){

SL.r[p]←→SL.r[i];//交換記錄，使第i個記錄到位

SL.r[i].next=p;

//指向被移走的記錄}

p=q;

//p指示尚未調(diào)整的表尾，//為找第i+1個記錄作準(zhǔn)備}}//Arrange2/11/2023310.1概述10.2插入排序10.3快速排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種排序方法的比較討論2/11/2023510.1概述一、排序的定義二、排序的基本概念三、內(nèi)部排序方法的分類2/11/20236一、排序的定義

什么是排序(Sorting)？簡單地說，排序就是將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律排列起來（遞增或遞減）。排序是計算機(jī)中經(jīng)常遇到的操作。2/11/20237排序算法的穩(wěn)定性判斷標(biāo)準(zhǔn)：關(guān)鍵字相同的數(shù)據(jù)對象在排序過程中是否保持前后次序不變。如2,2*,1，排序后若為1,2*,2則該排序方法是不穩(wěn)定的。內(nèi)排序與外排序區(qū)分標(biāo)準(zhǔn)：排序過程是否全部在內(nèi)存進(jìn)行。排序的時間開銷

它是衡量算法好壞的最重要的標(biāo)志。通常用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)和數(shù)據(jù)移動次數(shù)來衡量。

2/11/20239排序的方法有很多，但簡單地判斷那一種算法最好，以便能夠普遍選用則是困難的。評價排序算法好壞的標(biāo)準(zhǔn)主要有兩條：算法執(zhí)行所需要的時間和所需要的附加空間。另外，算法本身的復(fù)雜程度也是需要考慮的一個因素。排序算法所需要的附加空間一般都不大，矛盾并不突出。而排序是一種經(jīng)常執(zhí)行的一種運(yùn)算，往往屬于系統(tǒng)的核心部分，因此排序的時間開銷是算法好壞的最重要的標(biāo)志。2/11/202310三、內(nèi)部排序的方法

內(nèi)部排序的過程是一個逐步擴(kuò)大記錄的有序序列長度的過程。經(jīng)過一趟排序有序序列區(qū)無序序列區(qū)有序序列區(qū)無序序列區(qū)2/11/202311待排記錄的數(shù)據(jù)類型:#defineMAXSIZE1000//待排順序表最大長度typedefintKeyType;//關(guān)鍵字類型為整數(shù)類型typedefstruct{KeyTypekey;//關(guān)鍵字項InfoTypeotherinfo;//其它數(shù)據(jù)項}RedType;//記錄類型typedefstruct{RedTyper[MAXSIZE+1];//r[0]閑置或用作哨兵單元intlength;//順序表長度}SqList;//順序表類型2/11/2023131.插入

將無序子序列中的一個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。2/11/2023142.交換

通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。2/11/2023154.歸并

通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。2/11/2023175.基數(shù)不需進(jìn)行記錄關(guān)鍵字間的比較，借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)行排序的方法。2/11/20231810.2插入排序2/11/202319有序序列R[1..i-1]R[i]無序序列R[i..n]有序序列R[1..i]無序序列R[i+1..n]1、一趟插入排序的基本思想2/11/202321實(shí)現(xiàn)“一趟插入排序”可分三步進(jìn)行：3．將R[i]插入(復(fù)制)到R[j+1]的位置上。2．將R[j+1..i-1]中的所有記錄均后移一個位置；1．在R[1..i-1]中查找R[i]的插入位置，R[1..j].keyR[i].key<R[j+1..i-1].key；2/11/202322直接插入排序（基于順序查找）表插入排序（基于靜態(tài)鏈表存儲）不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序（基于折半查找）希爾排序（基于逐趟縮小增量）靜態(tài)鏈表：用數(shù)組描述的鏈表2/11/202323從R[i-1]起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在R[0]；R[0]=R[i];//設(shè)置“哨兵”循環(huán)結(jié)束表明R[i]的插入位置為j+1R[0]jR[i]for(j=i-1;R[0].key<R[j].key;--j);//從后往前找j=i-1插入位置2/11/202325對于在查找過程中找到的那些關(guān)鍵字不小于R[i].key的記錄，并在查找的同時實(shí)現(xiàn)記錄向后移動；for(j=i-1;R[0].key<R[j].key;--j);

R[j+1]=R[j]R[0]jR[i]j=i-1上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”插入位置2/11/202326例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序結(jié)果：2/11/202329內(nèi)部排序的時間分析：實(shí)現(xiàn)內(nèi)部排序的基本操作有兩個：（2）“移動”記錄。（1）“比較”序列中兩個關(guān)鍵字的大??；2/11/202330算法評價時間復(fù)雜度若待排序記錄按關(guān)鍵字從小到大排列(正序)關(guān)鍵字比較次數(shù)：記錄移動次數(shù)：0若待排序記錄按關(guān)鍵字從大到小排列(逆序)關(guān)鍵字比較次數(shù)：記錄移動次數(shù)：若待排序記錄是隨機(jī)的，取平均值關(guān)鍵字比較次數(shù)：記錄移動次數(shù)：T(n)=O(n2)空間復(fù)雜度：S(n)=O(1)2/11/202331直接插入排序的穩(wěn)定性直接插入排序是一種穩(wěn)定的排序方法。原理：關(guān)鍵字相同的兩個對象，在整個排序過程中，不會通過比較而相互交換。2/11/202332

因?yàn)镽[1..i-1]是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉?、折半插入排序2/11/202333voidBInsertSort(SqList&L){}//BInsertSort……//在L.r[1..i-1]中折半查找插入位置；for(i=2;i<=L.length;++i){}//forL.r[0]=L.r[i];//將L.r[i]暫存到L.r[0]for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//記錄后移L.r[high+1]=L.r[0];//插入2/11/202334low=1;high=i-1;while(low<=high){}m=(low+high)/2;//折半if(L.r[0].key<L.r[m].key)

high=m-1;//插入點(diǎn)在低半?yún)^(qū)elselow=m+1;//插入點(diǎn)在高半?yún)^(qū)2/11/202335例算法評價時間復(fù)雜度：T(n)=O(n2)空間復(fù)雜度：S(n)=O(1)i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)2/11/202336基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。具體做法為：將記錄序列分成若干子序列，分別對每個子序列進(jìn)行插入排序。4、希爾排序（縮小增量排序）2/11/202337其中，d稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為1。例如：將n個記錄分成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]}2/11/202338例如：162512304711233691831

第一趟希爾排序，設(shè)增量d=51123

12

9

181625

36

30

4731

第二趟希爾排序，設(shè)增量d=3918

121123

162531

304736第三趟希爾排序，設(shè)增量d=1

9111216182325303136472/11/202339voidShellInsert(SqList&L,intdk){for(i=dk+1;i<=n;++i)

if(L.r[i].key<L.r[i-dk].key){L.r[0]=L.r[i];//暫存在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];//插入

}//if}//ShellInsert2/11/202340voidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]對順序表L作希爾排序for(k=0;k<t;++t)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}//ShellSort2/11/202341為什么shell排序的時間性能優(yōu)于直接插入排序呢？因?yàn)橹苯硬迦肱判蛟诔鯌B(tài)為正序時所需時間最少，實(shí)際上，初態(tài)為基本有序時直接插入排序所需的比較和移動次數(shù)均較少。另一方面，當(dāng)n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復(fù)雜度O(n)和最壞時間復(fù)雜度O(n2)差別不大。在shell排序開始時增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但組內(nèi)元素已經(jīng)過多次排序，數(shù)組已經(jīng)比較接近有序狀態(tài)，所以新的一趟排序過程也較塊。2/11/202342希爾排序中g(shù)ap的取法Shell最初的方案是gap=n/2,gap=gap/2，直到gap=1.Knuth的方案是gap=gap/3+1其它方案有：都取奇數(shù)為好；或gap互質(zhì)為好等等。2/11/202343希爾排序的時間復(fù)雜度對希爾排序的復(fù)雜度的分析很困難，在特定情況下可以準(zhǔn)確地估算關(guān)鍵字的比較和對象移動次數(shù)，但是考慮到與增量之間的依賴關(guān)系，并要給出完整的數(shù)學(xué)分析，目前還做不到。Knuth的統(tǒng)計結(jié)論是，平均比較次數(shù)和對象平均移動次數(shù)在n1.25

與1.6n1.25之間。希爾排序的穩(wěn)定性希爾排序是一種不穩(wěn)定的排序方法。如序列322*52/11/202344

假設(shè)在排序過程中，記錄序列R[1..n]的狀態(tài)為：第i趟起泡排序無序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1無序序列R[1..n-i]有序序列R[n-i+1..n]比較相鄰記錄，將關(guān)鍵字最大的記錄交換到n-i+1的位置上5、起泡排序2/11/202345冒泡排序的排序過程將第一個記錄的關(guān)鍵字與第二個記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個記錄上對前n-1個記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個記錄位置重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交換記錄的操作”為止2/11/202346起泡排序示例i(0)(1)(2)(3)(4)(5)21254925*160810821254925*162081621254925*30816212525*4940816212525*492/11/202347起泡排序算法BUBBLESORT(rectypeR[]){inti,j,noswap;rectypetemp;for(i=0;i<n-2;i++){nos;for(j=n-1;j>=i;j++)if(R[j+1].key<R[j].key){temp＝R[j+1];R[j+1]=R[j];R[j]＝temp;nos;}if(noswap)break;}}2/11/202348起泡排序的時間復(fù)雜度考慮關(guān)鍵字的比較次數(shù)和對象移動次數(shù)1、在最好情況下，初始狀態(tài)是遞增有序的，一趟掃描就可完成排序，關(guān)鍵字的比較次數(shù)為n-1，沒有記錄移動。2、若初始狀態(tài)是反序的，則需要進(jìn)行n-1趟掃描，每趟掃描要進(jìn)行n-i次關(guān)鍵字的比較，且每次需要移動記錄三次，因此，最大比較次數(shù)和移動次數(shù)分別為：起泡排序方法是穩(wěn)定的。空間復(fù)雜度：S(n)=O(1)2/11/202349本節(jié)結(jié)束2/11/202350第四十九講數(shù)據(jù)結(jié)構(gòu)主講：劉立嘉快速排序與歸并排序2/11/202351基本思想：通過一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄進(jìn)行排序，以達(dá)到整個序列有序排序過程：對r[s……t]中記錄進(jìn)行一趟快速排序，附設(shè)兩個指針i和j，設(shè)樞軸記錄rp=r[s]，x=rp.key初始時令i=s,j=t首先從j所指位置向前搜索第一個關(guān)鍵字小于x的記錄，并和rp交換再從i所指位置起向后搜索，找到第一個關(guān)鍵字大于x的記錄，和rp交換重復(fù)上述兩步，直至i==j為止再分別對兩個子序列進(jìn)行快速排序，直到每個子序列只含有一個記錄為止1、快速排序2/11/202352一、一趟快速排序（一次劃分）

目標(biāo)：找一個記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動至該記錄之后。致使一趟排序之后，記錄的無序序列R[s..t]將分割成兩部分：R[s..i-1]和R[i+1..t]，且

R[j].key≤R[i].key≤R[j].key(s≤j≤i-1)

樞軸

(i+1≤j≤t)。2/11/202353stlowhigh設(shè)R[s]=52為樞軸

將R[high].key和樞軸的關(guān)鍵字進(jìn)行比較，要求R[high].key≥

樞軸的關(guān)鍵字

將R[low].key和樞軸的關(guān)鍵字進(jìn)行比較，要求R[low].key≤

樞軸的關(guān)鍵字high23low80high14low52例如R[0]52lowhighhighhighlow2/11/202354可見，經(jīng)過“一次劃分”，將關(guān)鍵字序列52,49,80,36,14,58,61,97,23,75調(diào)整為:23,49,14,36,(52)58,61,97,80,75在調(diào)整過程中，設(shè)立了兩個指針：low和high，它們的初值分別為：s和t，之后逐漸減小high，增加low，并保證

R[high].key≥52，和R[low].key≤52,否則進(jìn)行記錄的“交換”。2/11/202355intPartition(SqList&L,intlow,inthigh){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[low]←→L.r[high];//將比樞軸記錄大的記錄交換到高端}

returnlow;//返回樞軸所在位置}//Partition2/11/202356intPartition(SqList&L,intlow,inthigh){}//PartitionL.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;2/11/202357二、快速排序

首先對無序的記錄序列進(jìn)行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進(jìn)行快速排序。無序的記錄序列無序記錄子序列(1)無序子序列(2)樞軸一次劃分分別進(jìn)行快速排序2/11/202358void

QSort(SqList&L,intlow,inthigh)

{

//對記錄序列L.r[low..high]進(jìn)行快速排序

if(low<high){

}}//QSortpivotloc=Partition(L,low,high);//對L.r[low..high]進(jìn)行一次劃分QSort(L,low,pivotloc-1);

//對低子序列遞歸排序，pivotloc是樞軸位置QSort(L,pivotloc+1,high);

//對高子序列遞歸排序2/11/202359voidQuickSort(SqList&L){

//對順序表進(jìn)行快速排序

QSort(L,1,L.length);}//QuickSort

第一次調(diào)用函數(shù)Qsort時，待排序記錄序列的上、下界分別為1和L.length。2/11/2023602、最好情況是每次所取的基準(zhǔn)都是當(dāng)前無序區(qū)的“中值”記錄，劃分的結(jié)果是基準(zhǔn)的左右兩個無序子區(qū)的長度大致相等。考慮關(guān)鍵字的比較次數(shù)和對象移動次數(shù)1、最壞情況是每次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗洠瑒澐值慕Y(jié)果是基準(zhǔn)的左邊（或右邊）為空，劃分前后無序區(qū)的元素個數(shù)減少一個，因此，排序必須做n-1趟，每一趟中需做n-i次比較，所以最大比較次數(shù)為三、快速排序的時間分析2/11/202361設(shè)C(n)表示對長度為n的序列進(jìn)行快速排序所需的比較次數(shù)，顯然，它應(yīng)該等于對長度為n的無序區(qū)進(jìn)行劃分所需的比較次數(shù)n-1，加上遞歸地對劃分所得的左右兩個無序子區(qū)進(jìn)行快速排序所需的比較次數(shù)。假設(shè)文件長度n=2k，k=log2n，因此有：2/11/202362

快速排序的記錄移動次數(shù)不會大于比較次數(shù)，所以，快速排序的最壞時間復(fù)雜度為O(n2)；最好時間復(fù)雜度為O(nlog2n)?？梢宰C明，快速排序的平均時間復(fù)雜度也是O(nlog2n)?？焖倥判蚴遣环€(wěn)定的排序方法。空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n)2/11/202363若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時，快速排序?qū)⑼懟癁槠鹋菖判颍鋾r間復(fù)雜度為O(n2)。為避免出現(xiàn)這種情況，需在進(jìn)行一次劃分之前，進(jìn)行“予處理”，即：先對R(s).key,R(t).key和R[(s+t)/2].key，進(jìn)行相互比較，然后取關(guān)鍵字為“三者之中”的記錄為樞軸記錄。2/11/202364

歸并排序的過程基于下列基本思想進(jìn)行：

將兩個或兩個以上的有序子序列“歸并”為一個有序序列。2、歸并排序2/11/202365在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。有序序列R[l..n]有序子序列R[l..m]有序子序列R[m+1..n]這個操作對順序表而言，是輕而易舉的。2/11/202366voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){//將有序的記錄序列SR[i..m]和SR[m+1..n]//歸并為有序的記錄序列TR[i..n]for(j=m+1,k=i;

i<=m

&&

j<=n;++k)

{//將SR中記錄由小到大地并入TRif(LQ(SR[i].key,SR[j].key))TR[k]=SR[i++];elseTR[k]=SR[j++];}2/11/202367if(i<=m)TR[k..n]=SR[i..m];//將剩余的SR[i..m]復(fù)制到TRif(j<=n)TR[k..n]=SR[j..n];//將剩余的SR[j..n]復(fù)制到TR}//Merge2/11/202368歸并排序的算法如果記錄無序序列R[s..t]的兩部分R[s..(s+t)/2]和R[(s+t)/2+1..t]分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。由此，應(yīng)該先分別對這兩部分進(jìn)行2-路歸并排序。2/11/202369例如：52,23,80,36,68,14(s=1,t=6)[52,23,80]

[36,68,14][52,23][80][52][23,52][

23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]2/11/202370void

Msort(RcdTypeSR[],RcdType&TR1[],ints,intt)

{//將SR[s..t]歸并排序?yàn)門R1[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]}}//Msort2/11/202371voidMergeSort(SqList&L){//對順序表L作2-路歸并排序MSort(L.r,L.r,1,L.length);}//MergeSort以上是遞歸的算法，下面介紹遞推過程的算法2/11/202372歸并算法MERGE(rectyprR[],rectypeR1[],intlow,intmid,inthigh){inti,j,k;i=low;j=mid+1;k=low;while((i<=mid)&&(j<=high))if(R[i].key<=R[j].key)R1[k++]=R[i++];elseR1[k++]=R[j++];while(j<=mid)R1[k++]=R[i++];while(j<=high)R1[k++]=R[j++];}2/11/202373

歸并排序就是利用上述歸并操作實(shí)現(xiàn)排序的。其基本思想是：將待排序列R[0]到R[n-1]看成n個長度為1的有序子序列，把這些子序列兩兩歸并，便得到high(n/2)個有序的子序列。然后再把這high(n/2)個有序的子序列兩兩歸并，如此反復(fù)，直到最后得到一個長度為n的有序序列。上述每次的歸并操作，都是將兩個子序列歸并為一個子序列，這就是“二路歸并”，類似地還可以有“三路歸并”或“多路歸并”。2/11/202374歸并過程示例(25)(57)(48)(37)(12)(92)(86)(2557)(3748)(1292)(86)(25374857)(128692)(12253748578692)2/11/202375一趟歸并算法MERGEPASS(rectypeR[],rectypeR1[],intlength){inti,j;i=0;while(i+2*length-1<n){MERGE(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;}if(i+length-1<n-1)MERGE(R,R1,i,i+length-1,n-1);elsefor(j=i;j<n;j++)R1[j]=R[j];}2/11/202376歸并排序算法MERGESORT(rectypeR[]){intlength=1;while(length<n){MERGEPASS(R,R1,length);length=2*length;MERGEPASS(R1,R,length);length=2*length;}}

2/11/202377算法復(fù)雜性分析歸并排序是穩(wěn)定的排序方法。歸并排序在第i趟歸并后，有序子文件長度為2i，因此，因此，對于具有n個記錄的序列來說，必須做high(log2n)趟歸并，每趟歸并所花的時間為O(n)。所以，二路歸并排序算法的時間復(fù)雜度為O(nlog2n)，輔助數(shù)組所需的空間為O(n)。2/11/202378本節(jié)結(jié)束2/11/202379第五十講數(shù)據(jù)結(jié)構(gòu)主講：劉立嘉選擇排序2/11/202380假設(shè)排序過程中，待排記錄序列的狀態(tài)為：有序序列R[1..i-1]無序序列R[i..n]第i趟簡單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R[1..i]無序序列R[i+1..n]1、簡單選擇排序/直接選擇排序2/11/202381簡單選擇排序的算法描述如下：voidSelectSort(SqList&L){

//對記錄序列作簡單選擇排序。for(i=1;i<L.length;++i){

//選擇第i小的記錄，并交換到位}}//SelectSortj=SelectMinKey(L,i);

//在L.r[i..L.length]中選擇關(guān)鍵字最小的記錄if(i!=j)L.r[i]←→L.r[j];//與第i個記錄交換2/11/202382直

接

選擇

排序

示

例4938659776132749’1338659776492749’1327659776493849’1327389776496549’1327384976976549’1327384949’9765761327384949’6597761327384949’6576972/11/202383算法評價時間復(fù)雜度記錄移動次數(shù)最好情況：0最壞情況：3(n-1)比較次數(shù)：空間復(fù)雜度：S(n)=O(1)算法的穩(wěn)定性：不穩(wěn)定。T(n)=O(n2)2/11/202384堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或堆的定義:(小頂堆)(大頂堆)2、堆排序2/11/202385rir2i

r2i+1

若將該數(shù)列視作完全二叉樹，則r2i是ri的左孩子；r2i+1是ri的右孩子。1236276549817355403498例如:是堆14不2/11/202386988127731109是大頂堆12968338例如:2/11/2023879881244730是小頂堆1212368553912/11/202388

堆排序即是利用堆的特性對記錄序列進(jìn)行排序的一種排序方法。在輸出堆頂?shù)淖钚≈抵?使得剩余n-1個元素的序列重又建成一個堆,則得到n個元素中的次小值.如此反復(fù)執(zhí)行,便能得到一個有序序列,這個過程稱之為堆排序.如何“建堆”？兩個問題:如何“篩選”？2/11/202389堆排序的第一個工作是建堆，即把整個記錄數(shù)組R[1]到R[n]調(diào)整為一個堆。顯然,只有一個結(jié)點(diǎn)的樹是堆，而在完全二叉樹中，所有序號i>=low(n/2)的結(jié)點(diǎn)都是葉子，因此以這些結(jié)點(diǎn)為根的子樹都已是堆。這樣，我們只需依次將序號為low(n/2)，low(n/2)-1，...，1的結(jié)點(diǎn)作為根的子樹都調(diào)整為堆即可。我們以大根堆為例進(jìn)行說明2/11/202390

若已知結(jié)點(diǎn)R[i]的左右子樹已是堆，如何將以R[i]為根的完全二叉樹也調(diào)整為堆？解決這一問題可采用“篩選法”，其基本思想是：因?yàn)镽[i]的左右子樹已是堆，這兩棵子樹的根分別是各自子樹中關(guān)鍵字最大的結(jié)點(diǎn)，所以我們必須在R[i]和它的左右孩子中選取關(guān)鍵字最大的結(jié)點(diǎn)放到R[i]的位置上。若R[i]的關(guān)鍵字已是三者中的最大者，則無須做任何調(diào)整，以R[i]為根的子樹已構(gòu)成堆，否則必須將R[i]和具有最大關(guān)鍵字的左孩子R[2i]或右孩子R[2i+1]進(jìn)行交換。假定R[2i]的關(guān)鍵字最大，將R[i]和R[2i]交換位置，交換之后有可能導(dǎo)致R[2i]為根的子樹不再是堆，但由于R[2i]的左右子樹仍然是堆，于是可以重復(fù)上述過程，將以R[2i]為根的子樹調(diào)整為堆，...，如此逐層遞推下去，最多可能調(diào)整到樹葉。2/11/202391例子：關(guān)鍵字序列為42，13，91，23，24，16，05，88，n=8，故從第四個結(jié)點(diǎn)開始調(diào)整421391232416058842139123241605882/11/20239242139188241605234213918824160523不調(diào)整2/11/202393421391882416052342139188241605232/11/202394428891232416051342889123241605132/11/20239591884223241605139188422324160513建成的堆2/11/202396篩選算法SIFT(rectypeR[],inti;intm){intj;rectypetemp;temp=R[i];j=2*i;while(j<=m){if((j<m)&&(R[j].key<R[j+1].key))j++;if(temp.key<R[j].key){R[i]=R[j];i=j;j=2*i;}elsebreak;}R[i]=temp;}2/11/202397

上述算法只是對一個指定的結(jié)點(diǎn)進(jìn)行調(diào)整。有了這個算法，則將初始的無序區(qū)R[1]到R[n]建成一個大根堆，可用以下語句實(shí)現(xiàn)：for(i=n/2;i>=1;i--)SIFT(R,i,n)

由于建堆的結(jié)果把關(guān)鍵字最大的記錄選到了堆頂?shù)奈恢?，而排序的結(jié)果應(yīng)是升序，所以，應(yīng)該將R[1]和R[n]交換，這就得到了第一趟排序的結(jié)果。第二趟排序的操作首先是將無序區(qū)R[1]到R[n-1]調(diào)整為堆。這時對于當(dāng)前堆來說，它的左右子樹仍然是堆，所以，可以調(diào)用SIFT函數(shù)將R[1]到R[n-1]調(diào)整為大根堆，選出最大關(guān)鍵字放入堆頂，然后將堆頂與當(dāng)前無序區(qū)的最后一個記錄R[n-1]交換，如此反復(fù)進(jìn)行下去。2/11/20239891884223241605139188422324160513（a）初始堆R[1]到R[8]2/11/20239913884223241605911388422324160591（b）第一趟排序之后2/11/2023100（c）重建的堆R[1]到R[7]882442231316059188244223131605912/11/202310105244223131688910524422313168891（d）第二趟排序之后2/11/2023102（e）重建的堆R[1]到R[6]422416231305889142241623130588912/11/2023103（f）第三趟排序之后052416231342889105241623134288912/11/2023104（g）重建的堆R[1]到R[5]242316051342889124231605134288912/11/2023105（h）第四趟排序之后132316052442889113231605244288912/11/2023106（i）重建的堆R[1]到R[4]231316052442889123131605244288912/11/2023107（j）第五趟排序之后051316232442889105131623244288912/11/2023108（k）重建的堆R[1]到R[3]161305232442889116130523244288912/11/2023109（l）第六趟排序之后051316232442889105131623244288912/11/2023110（m）重建的堆R[1]到R[2]130516232442889113051623244288912/11/2023111（n）第七趟排序之后051316232442889105131623244288912/11/2023112堆排序算法HEAPSORT(rectypeR[]){inti;rectypetemp;for(i=n/2;i>=1;i--)SIFT(R,i,n);for(i=n;i>=1;i--){temp=R[1];R[1]=R[i];R[i]=temp;SIFT(R,1,i-1);}}2/11/2023113堆排序的時間復(fù)雜度分析：1.對深度為k的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；3.調(diào)整“堆頂”n-1次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過2(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)因此，堆排序的時間復(fù)雜度為O(nlogn)。2.對n個關(guān)鍵字，建成深度為h(=log2n+1)的堆，

所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多4n；2/11/2023114堆排序的空間復(fù)雜性為O(1)堆排序是不穩(wěn)定的排序方法。優(yōu)點(diǎn)：對小文件效果不明顯，但對大文件有效。2/11/2023115本節(jié)結(jié)束2/11/2023116第五十一講數(shù)據(jù)結(jié)構(gòu)主講：劉立嘉基數(shù)排序2/11/2023117

基數(shù)排序采用“分配”和“收集”的辦法，是一種借助“多關(guān)鍵字排序”的思想來實(shí)現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。多關(guān)鍵字的排序鏈?zhǔn)交鶖?shù)排序1、基數(shù)排序2/11/2023118一、多關(guān)鍵字的排序多關(guān)鍵字排序方法示例如對撲克牌的排序每張撲克牌有兩個“關(guān)鍵字”：花色和面值它們之間有次序的優(yōu)先。對以上排序，可以先對花色排序，或先對面值排序。2/11/2023119多關(guān)鍵字有序的概念考慮對象序列{V0,V1,...,Vn-1}，每個對象Vi含d個關(guān)鍵字(Ki1,Ki2,...,Kid)。若對序列中的任意兩個對象Vi和Vj都有

(Ki1,Ki2,...,Kid)<(Kj1,Kj2,...,Kjd)則稱序列對關(guān)鍵字(Ki1,Ki2,...,Kid)有序，且K1稱為最高位關(guān)鍵字，Kd稱為最低位關(guān)鍵字。2/11/2023120多關(guān)鍵字排序原理：根據(jù)組成關(guān)鍵字的各位的值進(jìn)行排序。實(shí)現(xiàn)基數(shù)排序的兩種方法：

1最高位優(yōu)先(MSD)排序：從關(guān)鍵字的高位到低位

2最低位優(yōu)先(LSD)排序：從關(guān)鍵字的低位到高位MSD方法通常是一個遞歸的過程。2/11/2023121多關(guān)鍵字排序（續(xù)）LSD和MSD方法也可應(yīng)用于對一個關(guān)鍵字進(jìn)行的排序。此時可將單關(guān)鍵字Ki看成是一個子關(guān)鍵字組：

(Ki1,Ki2,...,Kid)如對關(guān)鍵字取值范圍為0到999的一組對象，可看成是(K1,K2,K3)的組合。MSD方法按K1,K2,K3的順序?qū)λ袑ο笈判?；LSD方法按K3,K2,K1的順序?qū)λ袑ο笈判颉?/11/2023122例：對一副撲克牌該如何排序？答：若規(guī)定花色為第一關(guān)鍵字（高位），面值為第二關(guān)鍵字（低位），則使用MSD和LSD方法都可以達(dá)到排序目的。MSD方法的思路：先設(shè)立4個花色“箱”，將全部牌按花色分別歸入4個箱內(nèi)（每個箱中有13張牌）；然后對每個箱中的牌按面值進(jìn)行插入排序（或其它穩(wěn)定算法）。LSD方法的思路：先按面值分成13堆（每堆4張牌），然后對每堆中的牌按花色進(jìn)行排序（用插入排序等穩(wěn)定的算法）。想一想：用哪種方法更快些？2/11/2023123因?yàn)橛蟹纸M，故此算法需遞歸實(shí)現(xiàn)。討論：是借用MSD方式來排序呢，還是借用LSD方式？例：初始關(guān)鍵字序列T=（32,13,27,32*,19，33），請分別用MSD和LSD進(jìn)行排序，并討論其優(yōu)缺點(diǎn)。法1（MSD）：原始序列：32,13,27,32*,19，33

先按高位Ki1

排序：（13,19）,27,（32,32*，33）

再按低位Ki2排序：13,19，27,32,32*,33法2（LSD）：原始序列：32,13,27,32*,19，33先按低位Ki2排序：

32,32*,13,33,27,19

再按高位Ki1排序：

13,19,27,32,32*,33無需分組，易編程實(shí)現(xiàn)！2/11/2023124

例如:學(xué)生記錄含三個關(guān)鍵字:系別、班號和班內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。無序序列對K2排序?qū)1排序?qū)0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18

1,2,152,1,202,3,183,1,203,2,30LSD的排序過程如下:2/11/2023125二、鏈?zhǔn)交鶖?shù)排序假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范圍相同，則按LSD法進(jìn)行排序時，可以采用“分配-收集”的方法，其好處是不需要進(jìn)行關(guān)鍵字間的比較。對于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用這種“分配-收集”的辦法進(jìn)行排序，稱作基數(shù)排序法。2/11/2023126單邏輯關(guān)鍵字怎樣“按位值”排序？設(shè)n個記錄的序列為：{V0,V1,…,Vn-1}，可以把每個記錄Vi的單關(guān)鍵碼Ki

看成是一個d元組（Ki1,Ki2,…,Kid），則其中的每一個分量Kij

(1

jd)也可看成是一個關(guān)鍵字。4注1：

Ki1＝最高位，Kid＝最低位；Ki共有d位，可看成d元組；注2：每個分量Kij

(1

j

d)有radix種取值，則稱radix為基數(shù)。26(9,8,4)(0,1,…,9)（a,b,…,z）(d,i,a,n)310例1：關(guān)鍵碼984可以看成是

元組；基數(shù)radix為

。例2：關(guān)鍵碼dian可以看成是

元組；基數(shù)radix為

。思路：2/11/2023127例如：對下列這組關(guān)鍵字{209,386,768,185,247,606,230,834,539}首先按其“個位數(shù)”取值分別為0,1,…,9“分配”成10組，之后按從0至9的順序?qū)⑺鼈儭笆占痹谝黄?；然后按其“十位?shù)”取值分別為0,1,…,9“分配”成10組，之后再按從0至9的順序?qū)⑺鼈儭笆占痹谝黄?；最后按其“百位?shù)”重復(fù)一遍上述操作。2/11/2023128

在計算機(jī)上實(shí)現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為：

１．待排序記錄以指針相鏈，構(gòu)成一個鏈表；２．“分配”時，按當(dāng)前“關(guān)鍵字位”所取值，將記錄分配到不同的“鏈隊列”中，每個隊列中記錄的“關(guān)鍵字位”相同；３．“收集”時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;４．對每個關(guān)鍵字位均重復(fù)2)和3)兩步。2/11/20231291792083069385998455927133B[0].fB[1].fB[2].fB[3].fB[4].fB[5].fB[6].fB[7].fB[8].fB[9].fB[0].eB[1].eB[2].eB[3].eB[4].eB[5].eB[6].eB[7].eB[8].eB[9].e27193339845530620817985992/11/20231302719333984553062081798599B[0].fB[1].fB[2].fB[3].fB[4].fB[5].fB[6].fB[7].fB[8].fB[9].fB[0].eB[1].eB[2].eB[3].eB[4].eB[5].eB[6].eB[7].eB[8].eB[9].e33984306208955859271179932/11/20231313062089335585927117998493B[0].fB[1].fB[2].fB[3].fB[4].fB[5].fB[6].fB[7].fB[8].fB[9].fB[0].eB[1].eB[2].eB[3].eB[4].eB[5].eB[6].eB[7].eB[8].eB[9].e179306984859933559320827193355931792082713068599842/11/2023132分配排序算法typedefstruct{intkey[d];intnext;datatypeother;}rectype;

rectypeR[n];

typedefstruct{intf,e;}queue;

queueB[m];2/11/2023133for(j=d-1;j>=0;j--){for(i=0;i<m;i++){B[i].f=-1;B[i].e=-1;}while(p!=-1){k=R[p].key[j];if(B[k].f==-1)B[k].f=p;elseR[B[k].e].next=p;B[k].e=p;p=R[p].next;}i=0;while(B[i].f==-1)i++;t=B[i].e;p=B[i].f;while(i<m-1){i++;if(B[i].f!=-1){R[t].next=B[i].f;t=B[i].e;}}R[t].next=-1;}returnp;}intRADIXSORT(rectypeR[]){inti,j,k,t,p;for(i=0;i<n-1;i++)R[i].next=i+1;R[n-1].next=-1;p=0;2/11/2023134注意：１．“分配”和“收集”的實(shí)際操作僅為修改鏈表中的指針和設(shè)置隊列的頭、尾指針；２．為查找使用，該鏈表尚需應(yīng)用算法Arrange將它調(diào)整為有序表。2/11/2023135算法評價特點(diǎn)：不用比較和移動，改用分配和收集，時間效率高！時間復(fù)雜度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd))其中：n——記錄數(shù)d——關(guān)鍵字?jǐn)?shù)rd——關(guān)鍵字取值范圍空間復(fù)雜度：S(n)=2rd個隊列指針+n個指針域空間穩(wěn)定性：穩(wěn)定。(一直前后有序)。2/11/2023136一、時間性能1.平均的時間性能基數(shù)排序時間復(fù)雜度為O(nlogn)：快速排序、堆排序和歸并排序時間復(fù)雜度為O(n2)：直接插入排序、起泡排序和簡單選擇排序時間復(fù)雜度為O(n):2、各種排序方法的綜合比較2/11/20231372.當(dāng)待排記錄序列按關(guān)鍵字順序有序時3.

簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。直接插入排序和起泡排序能達(dá)到O(n)的時間復(fù)雜度，快速排序的時間性能蛻化為O(n2)。2/11/2023138二、空間性能指的是排序過程中所需的輔助空間大小1.所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)

和堆排序的空間復(fù)雜度為O(1)；2.

快速排序?yàn)镺(logn)，為遞歸程序執(zhí)行過程中，棧所需的輔助空間；2/11/20231393.

歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n);4.

鏈?zhǔn)交鶖?shù)排序需附設(shè)隊列首尾指針，則空間復(fù)雜度為

O(rd)。2/11/2023140三、排序方法的穩(wěn)定性能

1.穩(wěn)定的排序方法指的是，對于兩個關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。2.當(dāng)對多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時，必須采用穩(wěn)定的排序方法。排序之前:{·····Ri(K)·····Rj(K)·····}排序之后:{·····Ri(K)Rj(K)··········}2/11/2023141例如：

排序前

(56,34,47,23,66,18,82,

47)若排序后得到結(jié)果(18,23,34,47,47,56,66,82)則稱該排序方法是穩(wěn)定的;若排序后得到結(jié)果(18,23,34,47,47,56,66,82)則稱該排序方法是不穩(wěn)定的。2/11/20231423.對于不穩(wěn)定的排序方法，只要能舉出一個實(shí)例說明即可。4.快速排序、堆排序和希爾排序是不穩(wěn)定的排序方法。例如:對{4,3,4,2}進(jìn)行快速排序，得到{2,3,4,4}2/11/2023143四、關(guān)于“排序方法的時間復(fù)雜度的下限”