人的差異在于業余時間第二十二講第二十二講人的差異在于業余時間第二十二講第二十二講1、歸并排序2、總復習210.5歸并排序歸并排序(MergeSort)也是一種常用的排序方法，“歸并”的含義是將兩個或兩個以上的有序表合并成一個新的有序表。如圖8-11為兩組有序表的歸并，有序表{4,25,34,56,69,74}和{15,26,34,47,52}，通過歸并把它們合并成一個有序表{4,15,25,26,34,34,47,52,56,69,74}。圖8-11兩組有序表的歸并3voidMerge(RecTypeR[],RecTypeR1[],intlow,intm,inthigh){//R[low..m]和R[m+1..high]是兩個有序表inti=low,j=m+l,k=low;//k是Rl的下標，i、j分別為R[low..m]和R[m+1..high]的下標

while(i<=m&&j<=high){

//在R[low..m]和R[m+1..high]均未掃描完時循環

if(R[i].key<=R[j].key){//將R[low..m]中的記錄放入R1中

R1[k]=R[i];i++;k++;

}else{//將R[m+1..high]中的記錄放入R1中

R1[k]=R[j];j++;k++;

}}6while(i<=m){//將R[low..m]余下部分復制到R1

R1[k]=R[i];i++;k++;}

while(j<=high){//將R[m+1..high]余下部分復制到R1

R1[k]=R[j];

j++;k++;}}72．一趟歸并排序的算法MergePass()。一趟歸并排序的算法調用n/(2*length)次歸并算法merge()，將R[1..n]中前后相鄰且長度為length的有序子表進行兩兩歸并，得到前后相鄰且長度為2*length的有序表，并存放在R1[1..n]中。如果n不是2*length的整數倍，則可出現兩種情況：一種情況是，剩下一個長度為length的有序子表和一個長度小于length的子表，合并之后其有序表的長度小于2*length；另一種情況是，只剩下一個子表，其長度小于等于length，此時不調用算法merge()，只需將其直接放入數組R1中，準備進行下一趟歸并排序。算法描述如下：8voidMergePass(RecTypeR[],RecTypeR1[],intlength,intn){inti=0,j;while(i+2*length-l<n){Merge(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;//歸并長度為length的兩相鄰有序子表

}

if(i+length-1<n-1)//余下兩個有序子表，其中一個長度小于lengh

Merge(R,R1,i,i+length-1,n-1);//歸并兩個有序表

else

for(j=i;j<n;j++)//剩下一個有序子表，其長度小于lengh

R1[j]=R[j];}93．歸并排序算法Merge--_Sort()兩路歸并排序需要由多趟歸并過程實現。第一趟length=1，以后每執行一趟歸并后將length加倍。第一趟歸并的結果存放在R1中；第二趟將數組R1中的有序子表兩兩合并，結果存放在數組R中；如此反復進行。為使最終排序結果存放在數組R中，進行歸并的趟數必須是偶數。因此當只需奇數趟歸并即可完成排序時，應再進行一趟歸并，只是此時只剩下一個長度不大于length的有序表，直接從數組R1復制到R中即可。算法描述如下：voidMerge--_Sort(RecTypeR[],intn){intlength=1;while(length<n){MergePass(R,R1,length,n);length=2*length;MergePass(R1,R,length,n);length=2*length;}}10【例10-8】初始序列為｛23，56，42，37，15，84，72，27，18｝用二路歸并排序法排序。【解】排序后的結果為：｛15，18，23，27，37，42，56，72，84｝，整個歸并過程如圖8-12所示。圖10-12歸并排序示例11顯然，n個記錄進行二路歸并排序時，歸并的趟數為O(log2n)，每趟歸并中，關鍵字的比較次數不超過n，因此，二路歸并排序的時間復雜度為O(nlog2n)。對序列進行歸并排序時，除采用二路歸并排序外，還可以采用多路歸并排序方法（可參考其它有關書籍）。歸并排序需要的輔助空間R1與待排序記錄的數量相等，因此二路歸并排序的空間復雜度為O(n)，這是常用的排序方法中空間復雜度最差的一種排序方法。另外，從排序的穩定性看，二路歸并排序是一種穩定的排序方法。1210.6各種排序方法的比較在前面幾節中討論了內部排序的方法。對于內部排序主要介紹了四大類排序方法：插入排序（直接插入排序、折半插入排序和希爾排序）、交換排序（冒泡排序和快速排序）、選擇排序（簡單選擇排序和堆排序）、歸并排序。詳細討論了各種排序方法的基本原理，并從時間復雜性、空間復雜性以及排序的穩定性三方面討論了各種排序方法的時效性，介紹了各排序方法的實現算法及其存在的優缺點。如果待排序的數據量很小，最好選擇編程簡單的排序算法，因為在這種情況下采用編程復雜、效率較高的排序方法所能節約的計算機時間是很有限的。反之，如果待處理的數據量很大，特別是當排序過程作為應用程序的一部分需要經常執行時，就應該認真分析和比較各種排序方法，從中選出運行效率最高的方法。13下面具體比較一下各種排序方法，以便實現不同的排序處理。(1)插入排序的原理：向有序序列中依次插入無序序列中待排序的記錄，直到無序序列為空，對應的有序序列即為排序的結果，其主旨是“插入”。(2)交換排序的原理：先比較大小，如果逆序就進行交換，直到有序。其主旨是“若逆序就交換”。(3)選擇排序的原理：先找關鍵字最小的記錄，再放到已排好序的序列后面，依次選擇，直到全部有序，其主旨是“選擇”。(4)歸并排序的原理：依次對兩個有序子序列進行“合并”，直到合并為一個有序序列為止，其主旨是“合并”。(5)基數排序的原理：按待排序記錄的關鍵字的組成成分進行排序的一種方法，即依次比較各個記錄關鍵字相應“位”的值，進行排序，直到比較完所有的“位”，即得到一個有序的序列。各種排序方法的工作原理不同，對應的性能也有很大的差別，下面通過一個表格可以看到各排序方法具體的時間性能、空間性能等方面的區別。14表10-2內部排序方法的時間性能、空間性能表15依據這些因素，可得出如下幾點結論：(1)若n較小（如n值小于50），對排序穩定性不作要求時，宜采用選擇排序方法，若關鍵字的值不接近逆序，亦可采用直接插入排序法。但如果規模相同，且記錄本身所包含的信息域比較多的情況下應首選簡單選擇排序方法。因為直接插入排序方法中記錄位置的移動操作次數比直接選擇排序多，所以選用直接選擇排序為宜。(2)如果序列的初始狀態已經是一個按關鍵字基本有序的序列，則選擇直接插入排序方法和冒泡排序方法比較合適，因為“基本”有序的序列在排序時進行記錄位置的移動次數比較少。(3)如果n較大，則應采用時間復雜度為O(nlog2n)的排序方法，即快速排序、堆排序或歸并排序方法。快速排序是目前公認的內部排序的最好方法，當待排序的關鍵字是隨機分布時，快速排序所需的平均時間最少；堆排序所需的時間與快速排序相同，但輔助空間少于快速排序，并且不會出現最壞情況下時間復雜性達到O(n2)的狀況。這兩種排序方法都是不穩定的，若要求排序穩定則可選用歸并排序。通常可以將它和直接插入排序結合在一起用。先利用直接插入排序求得兩個子文件，然后，再進行兩兩歸并。16前面討論的排序算法，除基數排序外，都是在一維數組上實現的，當記錄本身信息量較大時，為了避免移動記錄而浪費大量的時間，可以采用鏈表作為存儲結構，如插入排序和歸并排序都易于在鏈表上實現；但有的方法，如快速排序和堆排序，在鏈表上卻難于實現，在這種情況下，可以提取關鍵字建立索引表，然后，對索引表進行排序。然而更為簡單的方法是引入一個整型向量作為輔助表。排序前，若排序算法中要求交換，則只需交換相對應的向量，而無需交換具體的記錄內容；排序結束后，向量就指示了記錄之間的順序關系。17本章小結

排序是軟件設計中最常用的運算之一。排序分為內部排序和外部排序，涉及多種排序的方法。內部排序是將待排序的記錄全部放在內存的排序。本章所討論的各種內部排序的方法大致可分為：插入排序、交換排序、選擇排序、歸并排序和基數排序。插入排序算法的基本思想是：將待序列表看做是左、右兩部分，其中左邊為有序序列，右邊為無序序列，整個排序過程就是將右邊無序序列中的記錄逐個插入到左邊的有序序列中。直接插入排序是這類排序算法中最基本的一種，然而，該排序法時間性能取決于待排序記錄的初始特性。折半插入排序是通過折半查找的方法在有序表中查找記錄插入位置的排序方法。希爾排序算法是一種改進的插入排序，其基本思想是：將待排記錄序列劃分為若干組，在每組內先進行直接插入排序，以使組內序列基本有序，然后再對整個序列進行直接插入排序。其時間性能不取決于待排序記錄的初始特性。18交換排序的基本思想是：兩兩比較待排序列的記錄關鍵字，發現逆序即交換。基于這種思想的排序有冒泡排序和快速排序兩種。冒泡排序的基本思想是：從一端開始，逐個比較相鄰的兩個記錄，發現逆序即交換。然而，其時間性能取決于待排序記錄的初始特性。快速排序是一種改進的交換排序，其基本思想是：以選定的記錄為中間記錄，將待排序記錄劃分為左、右兩部分，其中左邊所確記錄的關鍵字不大于右邊所有記錄的關鍵字，然后再對左右兩部分分別進行快速排序。19選擇排序的基本思想是：在每一趟排序中，在待排序子表中選出關鍵字最小或最大的記錄放在其最終位置上。直接選擇排序和堆排序是基于這一思想的兩個排序算法。直接選擇排序算法采用的方法較直觀：通過對待排序子表中完整地比較一遍以確定最大(小)記錄，并將該記錄放在子表的最前(后)面。堆排序就是利用堆來進行的一種排序，其中堆是一個滿足特定條件的序列，該條件用完全二叉樹模型表示為每個結點不大于(小于)其左、右孩子的值。利用堆排序可使選擇下一個最大(小)數的時間加快，因而提高算法的時間復雜度，達到O(nlog2n)。歸并排序是一種基于歸并的排序，其基本操作是指將兩個或兩個以上的有序表合并成一個新的有序表。首先將n個待排序記錄看成n個長度為1的有序序列，第一趟歸并后變成n/2個長度為2或1的有序序列；再進行第二趟歸并，如此反復，最終得到一個長度為n的有序序列。歸并排序的時間復雜度為O(nlog2n)，最初待排序記錄的排列順序對運算時間影響不大，不足之處就是需要占用較大的輔助空間。2019．對一組數據（84，47，25，15，21）排序，數據的排列次序在排序的過程中的變化為（1）8447251521（2）1547258421（3）1521258447（4）1521254784則采用的排序是()。選擇B.冒泡C.快速D.插入22．下列排序算法中()不能保證每趟排序至少能將一個元素放到其最終的位置上。A.快速排序B.shell排序C.堆排序D.冒泡排序AB2123．下列排序算法中()排序在一趟結束后不一定能選出一個元素放在其最終位置上。選擇B.冒泡C.歸并D.堆26．一組記錄的關鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（）。A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)CC2243．對下列關鍵字序列用快速排序法進行排序時，速度最快的情形是（）。A．{21,25,5,17,9,23,30}B．{25,23,30,17,21,5,9}C．{21,9,17,30,25,23,5}Ｄ．{5,9,17,21,23,25,30}44．對關鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結果為（）。(2,5,12,16)26(60,32,72)B.(5,16,2,12)28(60,32,72)C.(2,16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)AB2348.快速排序方法在（）情況下最不利于發揮其長處。A.要排序的數據量太大B.要排序的數據中含有多個相同值C.要排序的數據個數為奇數D.要排序的數據已基本有序50.以下序列不是堆的是()。A.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.(100,85,40,77,80,60,66,98,82,10,20)DD2451．下列四個序列中，哪一個是堆（）。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1552.堆排序是（）類排序，堆排序平均執行的時間復雜度和需要附加的存儲空間復雜度分別是（）

A.插入B.交換C.歸并D.基數E.選擇

F.O（n2）和O（1）G.O（nlog2n）和O（1）H.O（nlog2n）和O（n）I.O（n2）和O（n）CEG251、選擇題（40分，20道*2），考查基本概念，基本原理；2、填空題（10分，10個空*2），考查基本概念，基本原理，部分簡單操作和程序的編寫；3、應用題（操作題目）（30分，3~4道），考查一些常用基本算法的具體實現；4、程序設計題目（20分，10個空*2），考查常用重要算法的程序的編寫和改進；考試題型26各章重點內容第一章：基本概念和術語，時間復雜度；第二章：線性表的基本概念和存儲表示，線性鏈表的插入刪除操作，循環鏈表的各種操作；第三章：順序棧的表示和實現，應用（表達式求值，數制轉換），鏈隊列的表示和實現，循環隊列的表示和實現；第四章：串的基本概念，表示和實現（幾種表示方法，以及優缺點），KMP算法；27第五章：數組的概念