新編-《數(shù)據(jù)結(jié)構(gòu)用C語言描述》第八章jsp課件

概述插入排序交換排序選擇排序歸并排序基數(shù)排序各種內(nèi)排方法比較第八章排序概述第八章排序1概述排序：將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關鍵字有序的序列。

數(shù)據(jù)表(datalist):它是待排序數(shù)據(jù)對象的有限集合。主關鍵字(key):數(shù)據(jù)對象有多個屬性域,即多個數(shù)據(jù)成員組成,其中有一個屬性域可用來區(qū)分對象,作為排序依據(jù)，稱為關鍵字。也稱為關鍵字。概述排序：將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關鍵2排序方法的穩(wěn)定性:

如果在對象序列中有兩個對象r[i]和r[j],它們的關鍵字k[i]

==k[j]

,且在排序之前,對象r[i]排在r[j]前面。如果在排序之后,對象r[i]仍在對象r[j]的前面,則稱這個排序方法是穩(wěn)定的,否則稱這個排序方法是不穩(wěn)定的。內(nèi)排序與外排序:

內(nèi)排序是指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對象個數(shù)太多，不能同時存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動的排序。排序方法的穩(wěn)定性:如果在對象序列中有兩個對象r[i]和r3排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。typedefstruct{intkey;datatypeother;}rectype;rectypeR[n];排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的4內(nèi)排序分類依不同原則 插入排序、交換排序、選擇排序、歸并排序、和基數(shù)排序等。依所須工作量 簡單排序---時間復雜度o(n2) 先進排序方法---時間復雜度o(nlogn) 基數(shù)排序---時間復雜度o(d.n)內(nèi)排序分類依不同原則5插入排序(InsertSorting)基本思想

當插入第i(i1)個對象時,前面的R[0],R[1],…,R[i-1]已經(jīng)排好序。這時,用R[i]的關鍵字與R[i-1],R[i-2],…的關鍵字順序進行比較,找到插入位置即將R[i]插入,原來位置上的對象向后順移。

基本思想每步將一個待排序的對象,按其關鍵字大小,插入到前面已經(jīng)排好序的一組對象的適當位置上,直到對象全部插入為止。直接插入排序(InsertSort)插入排序(InsertSorting)基本思想當插入第6直接插入排序過程012345tempi=1i=2012345temp2108254925*162125084925*16252125084925*162125084925*16492125084925*16i=32125084925*1625*2125084925*16直接插入排序過程0127i=4i=52125084925*1616162125084925*162125084925*162125084925*1608i=4i=52125084925*1616162128直接插入排序的算法InsertSort(rectypeR[],intn){inti,j;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--];R[j+1]=R[0];}}直接插入排序的算法9算法分析設待排序?qū)ο髠€數(shù)為n,則該算法的主程序執(zhí)行n-1趟。關鍵字比較次數(shù)和對象移動次數(shù)與對象關鍵字的初始排列有關。最好情況下,排序前對象已按關鍵字從小到大有序,每趟只需與前面有序?qū)ο笮蛄械淖詈笠粋€對象比較1次,移動2次對象,總的關鍵字比較次數(shù)為n-1,對象移動次數(shù)為2(n-1)。算法分析設待排序?qū)ο髠€數(shù)為n,則該算法的主程序執(zhí)行n-110最壞情況下,第i趟時第i個對象必須與前面i個對象都做關鍵字比較,并且每做1次比較就要做1次數(shù)據(jù)移動。則總關鍵字比較次數(shù)KCN和對象移動次數(shù)RMN分別為在平均情況下的關鍵字比較次數(shù)和對象移動次數(shù)約為n2/4。因此，直接插入排序的時間復雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法。最壞情況下,第i趟時第i個對象必須與前面i個對11折半插入排序(BinaryInsertsort)基本思想

設在順序表中有一個對象序列R[0],R[1],…,R[n-1]。其中,R[0],R[1],…,R[i-1]是已經(jīng)排好序的對象。在插入R[i]時,利用折半搜索法尋找R[i]的插入位置。折半插入排序的算法折半插入排序(BinaryInsertsort)基本思想12typedefintSortData;RoidBinInsSort(SortDataR[],intn){SortDatatemp;intLeft,Right;

for(inti=1;i<n;i++){Left=0;Right=i-1;temp=R[i];while(Left<=Right){ intmid=(Left+Right)/2; if(temp<R[mid])Right=mid-1; elseLeft=mid+1;}for(intk=i-1;k>=Left;k--)R[k+1]=R[k];//記錄后移R[Left]=temp;//插入

}}typedefintSortData;13折半插入排序012345tempi=1i=2012345temp52133i=35521532144i=4215388i=52153161684421384516折半插入排序01214折半搜索比順序搜索查找快,所以折半插入排序就平均性能來說比直接插入排序要快。它所需的關鍵字比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關,僅依賴于對象個數(shù)。在插入第i個對象時,需要經(jīng)過log2i+1次關鍵字比較,才能確定它應插入的位置。因此,將n個對象(為推導方便,設為n=2k)用折半插入排序所進行的關鍵字比較次數(shù)為：

算法分析

折半搜索比順序搜索查找快,所以折半插入排序就平均性能來說比15當n較大時,總關鍵字比較次數(shù)比直接插入排序的最壞情況要好得多,但比其最好情況要差。在對象的初始排列已經(jīng)按關鍵字排好序或接近有序時,直接插入排序比折半插入排序執(zhí)行的關鍵字比較次數(shù)要少。折半插入排序的對象移動次數(shù)與直接插入排序相同,依賴于對象的初始排列。折半插入排序是一個穩(wěn)定的排序方法。折半插入排序的時間復雜度為o(n2)。當n較大時,總關鍵字比較次數(shù)比直接插入排序的最壞情況要16希爾排序(ShellSort)基本思想設待排序?qū)ο笮蛄杏衝個對象,首先取一個整數(shù)gap<n作為間隔,將全部對象分為gap個子序列,所有距離為gap的對象放在同一個子序列中,在每一個子序列中分別施行直接插入排序。然后縮小間隔gap,例如取gap=gap/2，重復上述的子序列劃分和排序工作。直到最后取gap==1,將所有對象放在同一個序列中排序為止。希爾排序方法又稱為縮小增量排序。希爾排序(ShellSort)基本思想設待排序?qū)ο笮蛄杏?7i

=3Gap=30123452108254925*160123452108254925*16i

=2Gap=22108254925*162108254925*16i

=1Gap=12108254925*162108254925*16希爾排序過程i=3Gap=30118ShellSort(rectypeR[],intn){rectypetemp;intgap=n/2;//gap是間隔 while(gap!=0){ //循環(huán),直到gap為零for(inti=gap;i<n;i++){temp=R[i]; //直接插入排序for(intj=i;j>=gap;j=j-gap)if(temp<R[j-gap])R[j]=R[j-gap];elsebreak; R[j]=temp;} gap=(int)(gap/2);}}

希爾排序的算法ShellSort(rectypeR[],int19開始時gap的值較大,子序列中的對象較少,排序速度較快;隨著排序進展,gap值逐漸變小,子序列中對象個數(shù)逐漸變多,由于前面大多數(shù)對象已基本有序,所以排序速度仍然很快。Gap的取法有多種。shell提出取gap=n/2，gap=gap/2，直到gap=1。對特定的待排序?qū)ο笮蛄校梢詼蚀_地估算關鍵字的比較次數(shù)和對象移動次數(shù)。希爾排序所需的比較次數(shù)和移動次數(shù)約為n1.3 當n趨于無窮時可減少到n(log2n)2開始時gap的值較大,子序列中的對象較少,排序速度較20交換排序(ExchangeSort)基本方法設待排序?qū)ο笮蛄兄械膶ο髠€數(shù)為n。一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個記錄地關鍵字，如果發(fā)生逆序，則交換之，其結(jié)果是這n-i+1個記錄中，關鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。

基本思想是兩兩比較待排序?qū)ο蟮年P鍵字,如發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之,直到所有對象都排好序為止。起泡排序(BubbleSort)交換排序(ExchangeSort)基本方法設待排序21210825492516214925251608214925251608214925251608214925251608初始關鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序的過程21082549251621492525160821492522210825492516081621254925212516492125084925251621214925251608初始關鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序的過程21082549251608162125492521251623起泡排序的算法BubbleSort(rectypeR[],intn){inti,j,noswap;rectypetemp;for(i=0;i<n-1;i++){noswap=1; //標志置為1,假定未交換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;noswap=0;//標志置為0,有交換}if(noswap)break;}}思考題：如何實現(xiàn)雙起泡起泡排序的算法24

第i趟對待排序?qū)ο笮蛄蠷[i-1],R[i],,R[n-1]進行排序,結(jié)果將該序列中關鍵字最小的對象交換到序列的第一個位置(i-1),其它對象也都向排序的最終位置移動。。最多做n-1趟起泡就能把所有對象排好序。在對象的初始排列已經(jīng)按關鍵字從小到大排好序時,此算法只執(zhí)行一趟起泡,做n-1次關鍵字比較,不移動對象。這是最好的情形。第i趟對待排序?qū)ο笮蛄蠷[i25最壞的情形是算法執(zhí)行n-1趟起泡,第i趟(1in)做n-i次關鍵字比較,執(zhí)行n-i次對象交換。這樣在最壞情形下總的關鍵字比較次數(shù)KCN和對象移動次數(shù)RMN為：起泡排序是一個穩(wěn)定的排序方法。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟(1in)26快速排序(QuickSort)基本思想是任取待排序?qū)ο笮蛄兄械哪硞€對象(例如取第一個對象)作為基準,按照該對象的關鍵字大小,將整個對象序列劃分為左右兩個子序列：

左側(cè)子序列中所有對象的關鍵字都小于或等于基準對象的關鍵字右側(cè)子序列中所有對象的關鍵字都大于基準對象的關鍵字快速排序(QuickSort)基本思想是任取待排序?qū)ο笮?7基準對象則排在這兩個子序列中間(這也是該對象最終應安放的位置)。然后分別對這兩個子序列重復施行上述方法，直到所有的對象都排在相應位置上為止?；鶞蕦ο笠卜Q為樞軸（或支點）記錄?；鶞蕦ο髣t排在這兩個子序列中間(這也是該對象最終應安放的位置28QuickSort(List){if(List的長度大于1){ 將序列List劃分為兩個子序列LeftList和RightList;QuickSort(LeftList); QuickSort(RightList); 將兩個子序列LeftList和RightList 合并為一個序列List;}}快速排序算法描述QuickSort(List){快速排序算法描述29快速排序的過程2108254925*16初始關鍵字08254925*162108254925*1608254925*1608254925*1608254925*1621prikey一次交換二次交換三次交換四次交換完成一趟排序ijijjiijjiji快速排序的過程2108254925*16初始關鍵字082543008254925*1621完成一趟排序分別進行快速排序08254925*1621有序序列08254925*162108254925*1621完成一趟排序分別進行快速排序08231

快速排序的算法QuickSort(rectypeR[],intlow,inthigh)//在序列l(wèi)owhigh中遞歸地進行快速排序{if(low<high) {inti=Partition(R,low,high);//劃分

QuickSort(R,low,i-1);//對左序列同樣處理

QuickSort(R,i+1,high);//對右序列同樣處理}}快速排序的算法32intPartition(rectypeR[],intlow,inthigh){R[0]=R[low];//子表的第一個記錄作基準對象tempkey=R[low].key;//基準對象關鍵字While(low<high){While(low<high&&R[high].key>=tempkey)high--;R[low]=R[high];//小于基準的移到區(qū)間的左側(cè)While(low<high&&R[low].key<=tempkey)low++;R[high]=R[low];//大于基準的移到區(qū)間的右側(cè)}R[low]=R[0];returnlow;}intPartition(rectypeR[],33

算法quicksort是一個遞歸的算法,其遞歸樹如圖所示。算法partition利用序列第一個對象作為基準，將整個序列劃分為左右兩個子序列。算法中執(zhí)行了一個循環(huán),只要是關鍵字小于基準對象關鍵字的對象都移到序列左側(cè),最后基準對象安放到位,函數(shù)返回其位置。2125*25490816算法quicksort是一個遞歸的算法,其遞歸樹如34算法分析快速排序的趟數(shù)取決于遞歸樹的高度。如果每次劃分對一個對象定位后,該對象的左側(cè)子序列與右側(cè)子序列的長度相同,則下一步將是對兩個長度減半的子序列進行排序,這是最理想的情況。在n個元素的序列中,對一個對象定位所需時間為O(n)。若設t(n)是對n個元素的序列進行排序所需的時間,而且每次對一個對象正確定位后,正好把序列劃分為長度相等的兩個子序列,此時,總的計算時間為：算法分析快速排序的趟數(shù)取決于遞歸樹的高度。35

T(n)cn+2T(n/2)//c是一個常數(shù)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)可以證明,函數(shù)quicksort的平均計算時間也是O(nlog2n)。實驗結(jié)果表明:就平均計算時間而言,快速排序是所有內(nèi)排序方法中最好的一個?？焖倥判蚴沁f歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)。T(n)cn+2T(n/2)//36最大遞歸調(diào)用層次數(shù)與遞歸樹的高度一致,理想情況為log2(n+1)。因此，要求存儲開銷為O(log2n)。在最壞的情況,即待排序?qū)ο笮蛄幸呀?jīng)按其關鍵字從小到大排好序的情況下,其遞歸樹成為單支樹,每次劃分只得到一個比上一次少一個對象的子序列。總的關鍵字比較次數(shù)將達快速排序是一種不穩(wěn)定的排序方法。最大遞歸調(diào)用層次數(shù)與遞歸樹的高度一致,理想情況為log237

基本思想每一趟(例如第i趟,i=0,1,…,n-2)在后面n-i個待排序記錄中選出關鍵字最小的記錄,作為有序序列中的第i個記錄。待到第n-2趟作完,待排序記錄只剩下1個,就不用再選了。選擇排序基本思想每一趟(例如第i趟,選擇排序38直接選擇排序是一種簡單的排序方法,它的基本步驟是：在一組對象R[i]～R[n-1]中選擇具有最小關鍵字的對象；若它不是這組對象中的第一個對象,則將它與這組對象中的第一個對象對調(diào);在這組對象中剔除這個具有最小關鍵字的對象。在剩下的對象R[i+1]～R[n-1]中重復執(zhí)行第①、②步,直到剩余對象只有一個為止。直接選擇排序(SelectSort)直接選擇排序是一種簡單的排序方法,它的基本步驟是：直接選3921254925*16080123452125*i=0492516251608490825*4921i=1i=2081625*2521初始最小者08交換21,08最小者16交換25,16最小者21交換49,21

直接選擇排序的過程21254925*16080140最小者25*無交換4925*01234525*i=42516084925*4921結(jié)果i=308162521最小者25無交換25211608各趟排序后的結(jié)果最小者25*4925*0141 直接選擇排序的算法SelectSort(rectypeR[],intn){inti,j,k;rectypetemp;for(i=0;i<n-1;i++){k=i;//選擇具有最小關鍵字的對象for(j=i+1;j<n;j++)if(R[j].key<R[k].key)k=j;//當前具最小關鍵字的對象if(k!=i)//對換到第i個位置 {temp=R[i];R[i]=R[k];R[k]=temp;} }} 直接選擇排序的算法42直接選擇排序的關鍵字比較次數(shù)KCN與對象的初始排列無關。設整個待排序?qū)ο笮蛄杏衝個對象,則第i趟選擇具有最小關鍵字對象所需的比較次數(shù)總是n-i-1次?？偟年P鍵字比較次數(shù)為對象的移動次數(shù)與對象序列的初始排列有關。當這組對象的初始狀態(tài)是按其關鍵字從小到大有序的時候,對象的移動次數(shù)RMN=0，達到最少。最壞情況是每一趟都要進行交換，總的對象移動次數(shù)為RMN=3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。直接選擇排序的關鍵字比較次數(shù)KCN與對象的初始排列無關。43堆排序(Heapsort)堆(Heap)設有一個關鍵字集合，按完全二叉樹的順序存儲方式存放在一個一維數(shù)組中。對它們從根開始，自頂向下，同一層自左向右從0開始連續(xù)編號。若滿足

Ki

K2i&&KiK2i+1或Ki

K2i&&KiK2i+1,則稱該關鍵字集合構(gòu)成一個堆。前者成為小根堆，后者稱為大根堆。堆排序(Heapsort)堆(Heap)設有一個44完全二叉樹順序表示Ki

K2i&KiK2i+1完全二叉樹順序表示Ki

K2i&&KiK2i+1090987877878454565653131532323531717完全二叉樹完全二叉樹0909878778784545656545堆排序(HeapSort)利用堆及其運算,可以很容易地實現(xiàn)選擇排序的思路。堆排序分為兩個步驟根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法SIFT()形成初始堆;通過一系列的對象交換和重新調(diào)整堆進行排序。堆排序(HeapSort)46自下向上逐步調(diào)整為小根堆5353171778780923456587i0923456587i=4i=3i初始小根堆的建立過程自下向上逐步調(diào)整為小根堆535317177878092345475353171778780923456587i0923456587i=2i5353171778780923456587i09234564853171778780923456587i0923456587i=1i5353171778780923456587i0923456584953171778780923456587i0923456587i53建成堆53171778780923456587i09234565850初始大根堆的建立過程212525*491608123456i212525*164908136542i初始關鍵字集合i=3時的局部調(diào)整初始大根堆的建立過程212525*491608123456i51212525*491608123456i492525*162108136542i=1時的局部調(diào)整形成大根堆i=2時的局部調(diào)整212525*491608123456i492525*16252大根堆的篩選算法SIFT(rectypeR[],inti,intm){intj=2*i;rectypetemp=R[i];while(j<=m){if(j<m&&R[j].key<R[j+1].key) j=j+1;//選兩子女的大者if(temp.key>=R[j])break;else{

大根堆的篩選算法SIFT(rectypeR[],i53

R[i]=R[j];//大子女上移i=j;j=2*i;//向下繼續(xù)調(diào)整}}R[i]=temp;//回放到合適位置}將表轉(zhuǎn)換成堆for(i=n/2;i>=1;i--)SIFT(R,i,n);

R[i]=R[j];54基于初始堆(大頂堆)進行堆排序最大堆堆頂R[0]具有最大的關鍵字,將R[0]與R[n-1]對調(diào),把具有最大關鍵字的對象交換到最后,再對前面的n-1個對象,使用堆的調(diào)整算法SIFT(0,n-2),重新建立最大堆,具有次最大關鍵字的對象又上浮到R[0]位置。再對調(diào)R[0]和R[n-2],調(diào)用SIFT(0,n-3),對前n-2個對象重新調(diào)整，…。如此反復執(zhí)行，最后得到全部排序好的對象序列。這個算法即堆排序算法，基于初始堆(大頂堆)進行堆排序最大堆堆頂R[0]具有最大的關55492525*211608012345082525*16214902543149252125*160808252125*1649交換0號與5號對象,5號對象就位初始最大堆基于初始堆進行堆排序492525*211608012345082525*1621562525*082116490123451625*082521490254312525*210816491625*210825

49交換0號與4號對象,4號對象就位從0號到4號重新調(diào)整為最大堆2525*082116490123451625*0825215725*1608212549012345081625*25214902543125*16210825

4908162125*

25

49交換0號與3號對象,3號對象就位從0號到3號重新調(diào)整為最大堆25*1608212549012345081625*252158211625*082549012345081625*25214902543121160825*

25

49081621

25*

25

49交換0號與2號對象,2號對象就位從0號到2號重新調(diào)整為最大堆211625*082549012345081625*252159160825*212549012345081625*25214902543116082125*

25

490816

21

25*

25

49交換0號與1號對象,1號對象就位從0號到1號重新調(diào)整為最大堆160825*212549012345081625*252160堆排序的算法HeapSort(rectypeR[])//對表R[1]到R[n]進行排序,使得表中對象關鍵字非遞減有序。{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); //重建最大堆}}堆排序的算法61若設堆中有n個結(jié)點,且2k-1

n2k,則對應的完全二叉樹有k層。在第i層上的結(jié)點數(shù)2i(i=0,1,…,k-1)。在第一個形成初始堆的for循環(huán)中對每一個非葉結(jié)點調(diào)用了一次堆調(diào)整算法SIFT(),因此該循環(huán)所用的計算時間為：其中,i是層序號,2i是第i層的最大結(jié)點數(shù),(k-i-1)是第i層結(jié)點能夠移動的最大距離。堆排序的算法分析若設堆中有n個結(jié)點,且2k-1n2k,62第二個for循環(huán)中調(diào)用了n-1次SIFT()算法,該循環(huán)的計算時間為O(nlog2n)。因此,堆排序的時間復雜性為O(nlog2n)。該算法的附加存儲主要是在第二個for循環(huán)中用來執(zhí)行對象交換時所用的一個臨時對象。因此，該算法的空間復雜性為O(1)。堆排序是一個不穩(wěn)定的排序方法。第二個for循環(huán)中調(diào)用了n-1次SIFT()算法,該循環(huán)63歸并排序(MergeSort)歸并將兩個或兩個以上的有序表合并成一個新的有序表。兩路歸并(2-waymerging)原始序列R[]中兩個有序表R[l]…R[m]和R[m+1]…R[n]，它們可歸并成一個有序表,存于另一對象序列R1的l…n中。歸并排序(MergeSort)歸并將兩個或兩個以上的有序6408212525*49627293163754lowmidmid+1highR0816212525*374954627293lowhighkR1設變量i和j是表R[l…m]和R[m+1…n]的當前檢測指針。k是存放指針。當i和j都在兩個表的表長內(nèi)變化時,根據(jù)對應項的關鍵字的大小,依次把關鍵字小的對象排放到新表k所指位置中；當i與j中有一個已經(jīng)超出表長時，將另一個表中的剩余部分照抄到新表中。ij08212525*4962729365merge(rectypeR[],rectypeR1[],intlow,intmid,inthigh){inti=low,j=mid+1,k=low; while(i<=mid&&j<=high)//兩兩比較將較小的并入if(R[i]<=R[j]){R1[k]=R[i];i++;k++;}else{R1[k]=R[j];j++;k++;}while(i<=mid){R1[k]=R[i];i++;k++;}//將mid前剩余的并入while(j<=high){R1[k]=R[j];j++;k++;}//將mid后剩余的并入} 兩路歸并算法merge(rectypeR[],rectype66一趟歸并排序的情形設R[0]到R[n-1]中n個對象已經(jīng)分為一些長度為len的歸并項,將這些歸并項兩兩歸并,歸并成長度為2len的歸并項,結(jié)果放到R1[]中。如果n不是2len的整數(shù)倍,則一趟歸并到最后,可能遇到兩種情形：剩下一個長度為len的歸并項和另一個長度不足len的歸并項,可用merge算法將它們歸并成一個長度小于2len的歸并項。只剩下一個歸并項，其長度小于或等于len,將它直接抄到R1[]中。一趟歸并排序的情形設R[0]到R[n-1]中n個對象已經(jīng)67迭代的歸并排序算法迭代的歸并排序算法就是利用兩路歸并過程進行排序的。其基本思想是：假設初始對象序列有n個對象，首先把它看成是n個長度為1的有序子序列(歸并項)，先做兩兩歸并，得到n/2個長度為2的歸并項(如果n為奇數(shù)，則最后一個有序子序列的長度為1)；再做兩兩歸并，…，如此重復，最后得到一個長度為n的有序序列。迭代的歸并排序算法迭代的歸并排序算法就是利用兩路歸并過程進行68迭代的歸并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=16迭代的歸并排序算法212525*25*9362720837169MergePass(rectypeR[],rectypeR1[],intlen){inti=0;while(i+2*len-1<=n-1){merge(R,R1,i,i+len-1,i+2*len-1);i+=2*len;//循環(huán)兩兩歸并}if(i+len<=n-1)merge(R,R1,i,i+len-1,n-1);elsefor(intj=i;j<=n-1;j++)R1[j]=R[j];}MergePass(rectypeR[],rec70歸并排序的主算法MergeSort(rectypeR[],intn){//按對象關鍵字非遞減的順序?qū)Ρ碇袑ο笈判騬ectypeR1[n];intlen=1;while(len<n){MergePass(R,R1,len);len*=2; MergePass(R1,R,len);len*=2;}}歸并排序的主算法71在迭代的歸并排序算法中,函數(shù)MergePass()做一趟兩路歸并排序,要調(diào)用merge()函數(shù)n/(2*len)

O(n/len)次,函數(shù)MergeSort()調(diào)用MergePass()正好log2n次,而每次merge()要執(zhí)行比較O(len)次,所以算法總的時間復雜度為O(nlog2n)。歸并排序占用附加存儲較多,需要另外一個與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個算法的缺點。歸并排序是一個穩(wěn)定的排序方法。在迭代的歸并排序算法中,函數(shù)MergePass()做一72基數(shù)排序多關鍵字排序例對52張撲克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A兩個關鍵字：花色（<<<）

面值（2<3<……<A）并且“花色”地位高于“面值”多關鍵字排序方法最高位優(yōu)先法（MSD)：先對最高位關鍵字k1（如花色）排序，將序列分成若干子序列，每個子序列有相同的k1值；然后讓每個子序列對次關鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復，直至就每個子序列對最低位關鍵字kd排序；最后將所有子序列依次連接在一起成為一個有序序列基數(shù)排序多關鍵字排序73最低位優(yōu)先法(LSD)：從最低位關鍵字kd起進行排序，然后再對高一位的關鍵字排序，……依次重復，直至對最高位關鍵字k1排序后，便成為一個有序序列鏈式基數(shù)排序基數(shù)排序：借助“分配”和“收集”對單邏輯關鍵字進行排序的一種方法鏈式基數(shù)排序方法：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序設置10個隊列，f[i]和e[i]分別為第i個隊列的頭指針和尾指針第一趟分配對最低位關鍵字（個位）進行，改變記錄的指針值，將鏈表中記錄分配至10個鏈隊列中，每個隊列記錄的關鍵字的個位相同最低位優(yōu)先法(LSD)：從最低位關鍵字kd起進行排序，然后再74第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將10個隊列鏈成一個鏈表重復上述兩步，進行第二趟、第三趟分配和收集，分別對十位、百位進行，最后得到一個有序序列第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一75例：初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：例：初始狀態(tài)：2781090639305891845052676505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：50500810993006326927808318458977008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二趟收集：00806308310918426927850558993078各種排序方法的比較各種排序方法的比較79概述插入排序交換排序選擇排序歸并排序基數(shù)排序各種內(nèi)排方法比較第八章排序概述第八章排序80概述排序：將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關鍵字有序的序列。

數(shù)據(jù)表(datalist):它是待排序數(shù)據(jù)對象的有限集合。主關鍵字(key):數(shù)據(jù)對象有多個屬性域,即多個數(shù)據(jù)成員組成,其中有一個屬性域可用來區(qū)分對象,作為排序依據(jù)，稱為關鍵字。也稱為關鍵字。概述排序：將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關鍵81排序方法的穩(wěn)定性:

如果在對象序列中有兩個對象r[i]和r[j],它們的關鍵字k[i]

==k[j]

,且在排序之前,對象r[i]排在r[j]前面。如果在排序之后,對象r[i]仍在對象r[j]的前面,則稱這個排序方法是穩(wěn)定的,否則稱這個排序方法是不穩(wěn)定的。內(nèi)排序與外排序:

內(nèi)排序是指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對象個數(shù)太多，不能同時存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動的排序。排序方法的穩(wěn)定性:如果在對象序列中有兩個對象r[i]和r82排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。typedefstruct{intkey;datatypeother;}rectype;rectypeR[n];排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的83內(nèi)排序分類依不同原則 插入排序、交換排序、選擇排序、歸并排序、和基數(shù)排序等。依所須工作量 簡單排序---時間復雜度o(n2) 先進排序方法---時間復雜度o(nlogn) 基數(shù)排序---時間復雜度o(d.n)內(nèi)排序分類依不同原則84插入排序(InsertSorting)基本思想

當插入第i(i1)個對象時,前面的R[0],R[1],…,R[i-1]已經(jīng)排好序。這時,用R[i]的關鍵字與R[i-1],R[i-2],…的關鍵字順序進行比較,找到插入位置即將R[i]插入,原來位置上的對象向后順移。

基本思想每步將一個待排序的對象,按其關鍵字大小,插入到前面已經(jīng)排好序的一組對象的適當位置上,直到對象全部插入為止。直接插入排序(InsertSort)插入排序(InsertSorting)基本思想當插入第85直接插入排序過程012345tempi=1i=2012345temp2108254925*162125084925*16252125084925*162125084925*16492125084925*16i=32125084925*1625*2125084925*16直接插入排序過程01286i=4i=52125084925*1616162125084925*162125084925*162125084925*1608i=4i=52125084925*16161621287直接插入排序的算法InsertSort(rectypeR[],intn){inti,j;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--];R[j+1]=R[0];}}直接插入排序的算法88算法分析設待排序?qū)ο髠€數(shù)為n,則該算法的主程序執(zhí)行n-1趟。關鍵字比較次數(shù)和對象移動次數(shù)與對象關鍵字的初始排列有關。最好情況下,排序前對象已按關鍵字從小到大有序,每趟只需與前面有序?qū)ο笮蛄械淖詈笠粋€對象比較1次,移動2次對象,總的關鍵字比較次數(shù)為n-1,對象移動次數(shù)為2(n-1)。算法分析設待排序?qū)ο髠€數(shù)為n,則該算法的主程序執(zhí)行n-189最壞情況下,第i趟時第i個對象必須與前面i個對象都做關鍵字比較,并且每做1次比較就要做1次數(shù)據(jù)移動。則總關鍵字比較次數(shù)KCN和對象移動次數(shù)RMN分別為在平均情況下的關鍵字比較次數(shù)和對象移動次數(shù)約為n2/4。因此，直接插入排序的時間復雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法。最壞情況下,第i趟時第i個對象必須與前面i個對90折半插入排序(BinaryInsertsort)基本思想

設在順序表中有一個對象序列R[0],R[1],…,R[n-1]。其中,R[0],R[1],…,R[i-1]是已經(jīng)排好序的對象。在插入R[i]時,利用折半搜索法尋找R[i]的插入位置。折半插入排序的算法折半插入排序(BinaryInsertsort)基本思想91typedefintSortData;RoidBinInsSort(SortDataR[],intn){SortDatatemp;intLeft,Right;

for(inti=1;i<n;i++){Left=0;Right=i-1;temp=R[i];while(Left<=Right){ intmid=(Left+Right)/2; if(temp<R[mid])Right=mid-1; elseLeft=mid+1;}for(intk=i-1;k>=Left;k--)R[k+1]=R[k];//記錄后移R[Left]=temp;//插入

}}typedefintSortData;92折半插入排序012345tempi=1i=2012345temp52133i=35521532144i=4215388i=52153161684421384516折半插入排序01293折半搜索比順序搜索查找快,所以折半插入排序就平均性能來說比直接插入排序要快。它所需的關鍵字比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關,僅依賴于對象個數(shù)。在插入第i個對象時,需要經(jīng)過log2i+1次關鍵字比較,才能確定它應插入的位置。因此,將n個對象(為推導方便,設為n=2k)用折半插入排序所進行的關鍵字比較次數(shù)為：

算法分析

折半搜索比順序搜索查找快,所以折半插入排序就平均性能來說比94當n較大時,總關鍵字比較次數(shù)比直接插入排序的最壞情況要好得多,但比其最好情況要差。在對象的初始排列已經(jīng)按關鍵字排好序或接近有序時,直接插入排序比折半插入排序執(zhí)行的關鍵字比較次數(shù)要少。折半插入排序的對象移動次數(shù)與直接插入排序相同,依賴于對象的初始排列。折半插入排序是一個穩(wěn)定的排序方法。折半插入排序的時間復雜度為o(n2)。當n較大時,總關鍵字比較次數(shù)比直接插入排序的最壞情況要95希爾排序(ShellSort)基本思想設待排序?qū)ο笮蛄杏衝個對象,首先取一個整數(shù)gap<n作為間隔,將全部對象分為gap個子序列,所有距離為gap的對象放在同一個子序列中,在每一個子序列中分別施行直接插入排序。然后縮小間隔gap,例如取gap=gap/2，重復上述的子序列劃分和排序工作。直到最后取gap==1,將所有對象放在同一個序列中排序為止。希爾排序方法又稱為縮小增量排序。希爾排序(ShellSort)基本思想設待排序?qū)ο笮蛄杏?6i

=3Gap=30123452108254925*160123452108254925*16i

=2Gap=22108254925*162108254925*16i

=1Gap=12108254925*162108254925*16希爾排序過程i=3Gap=30197ShellSort(rectypeR[],intn){rectypetemp;intgap=n/2;//gap是間隔 while(gap!=0){ //循環(huán),直到gap為零for(inti=gap;i<n;i++){temp=R[i]; //直接插入排序for(intj=i;j>=gap;j=j-gap)if(temp<R[j-gap])R[j]=R[j-gap];elsebreak; R[j]=temp;} gap=(int)(gap/2);}}

希爾排序的算法ShellSort(rectypeR[],int98開始時gap的值較大,子序列中的對象較少,排序速度較快;隨著排序進展,gap值逐漸變小,子序列中對象個數(shù)逐漸變多,由于前面大多數(shù)對象已基本有序,所以排序速度仍然很快。Gap的取法有多種。shell提出取gap=n/2，gap=gap/2，直到gap=1。對特定的待排序?qū)ο笮蛄?，可以準確地估算關鍵字的比較次數(shù)和對象移動次數(shù)。希爾排序所需的比較次數(shù)和移動次數(shù)約為n1.3 當n趨于無窮時可減少到n(log2n)2開始時gap的值較大,子序列中的對象較少,排序速度較99交換排序(ExchangeSort)基本方法設待排序?qū)ο笮蛄兄械膶ο髠€數(shù)為n。一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個記錄地關鍵字，如果發(fā)生逆序，則交換之，其結(jié)果是這n-i+1個記錄中，關鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。

基本思想是兩兩比較待排序?qū)ο蟮年P鍵字,如發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之,直到所有對象都排好序為止。起泡排序(BubbleSort)交換排序(ExchangeSort)基本方法設待排序100210825492516214925251608214925251608214925251608214925251608初始關鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序的過程210825492516214925251608214925101210825492516081621254925212516492125084925251621214925251608初始關鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序的過程210825492516081621254925212516102起泡排序的算法BubbleSort(rectypeR[],intn){inti,j,noswap;rectypetemp;for(i=0;i<n-1;i++){noswap=1; //標志置為1,假定未交換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;noswap=0;//標志置為0,有交換}if(noswap)break;}}思考題：如何實現(xiàn)雙起泡起泡排序的算法103

第i趟對待排序?qū)ο笮蛄蠷[i-1],R[i],,R[n-1]進行排序,結(jié)果將該序列中關鍵字最小的對象交換到序列的第一個位置(i-1),其它對象也都向排序的最終位置移動。。最多做n-1趟起泡就能把所有對象排好序。在對象的初始排列已經(jīng)按關鍵字從小到大排好序時,此算法只執(zhí)行一趟起泡,做n-1次關鍵字比較,不移動對象。這是最好的情形。第i趟對待排序?qū)ο笮蛄蠷[i104最壞的情形是算法執(zhí)行n-1趟起泡,第i趟(1in)做n-i次關鍵字比較,執(zhí)行n-i次對象交換。這樣在最壞情形下總的關鍵字比較次數(shù)KCN和對象移動次數(shù)RMN為：起泡排序是一個穩(wěn)定的排序方法。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟(1in)105快速排序(QuickSort)基本思想是任取待排序?qū)ο笮蛄兄械哪硞€對象(例如取第一個對象)作為基準,按照該對象的關鍵字大小,將整個對象序列劃分為左右兩個子序列：

左側(cè)子序列中所有對象的關鍵字都小于或等于基準對象的關鍵字右側(cè)子序列中所有對象的關鍵字都大于基準對象的關鍵字快速排序(QuickSort)基本思想是任取待排序?qū)ο笮?06基準對象則排在這兩個子序列中間(這也是該對象最終應安放的位置)。然后分別對這兩個子序列重復施行上述方法，直到所有的對象都排在相應位置上為止?；鶞蕦ο笠卜Q為樞軸（或支點）記錄?；鶞蕦ο髣t排在這兩個子序列中間(這也是該對象最終應安放的位置107QuickSort(List){if(List的長度大于1){ 將序列List劃分為兩個子序列LeftList和RightList;QuickSort(LeftList); QuickSort(RightList); 將兩個子序列LeftList和RightList 合并為一個序列List;}}快速排序算法描述QuickSort(List){快速排序算法描述108快速排序的過程2108254925*16初始關鍵字08254925*162108254925*1608254925*1608254925*1608254925*1621prikey一次交換二次交換三次交換四次交換完成一趟排序ijijjiijjiji快速排序的過程2108254925*16初始關鍵字0825410908254925*1621完成一趟排序分別進行快速排序08254925*1621有序序列08254925*162108254925*1621完成一趟排序分別進行快速排序082110

快速排序的算法QuickSort(rectypeR[],intlow,inthigh)//在序列l(wèi)owhigh中遞歸地進行快速排序{if(low<high) {inti=Partition(R,low,high);//劃分

QuickSort(R,low,i-1);//對左序列同樣處理

QuickSort(R,i+1,high);//對右序列同樣處理}}快速排序的算法111intPartition(rectypeR[],intlow,inthigh){R[0]=R[low];//子表的第一個記錄作基準對象tempkey=R[low].key;//基準對象關鍵字While(low<high){While(low<high&&R[high].key>=temp