天天看點
傳回

資料結構學習：：關于排序

近幾天重新學習資料結構，其實也不算重新，因為當年根本沒有學過。（像堆排序，基數排序等）。主要學習的是内部排序這一塊，馬上趁熱打鐵，将心得體會寫一下。

内部排序包括了以下幾種類别：插入排序，選擇排序，交換排序，歸并排序和基數排序。這是根據排序算法的本質特征來劃分的。

首先要給出的當然是資料結構了：

Code:

  1. typedef int KeyType;  
  2. typedef struct{  
  3.     KeyType *r;  
  4.     int length;  
  5. }SqList;  

插入排序

顧名思義，這是通過将元素插入适當的位置進行排序的算法。

首先說簡單插入排序，算法就是認為前i-1個元素是有序的，然後從i開始，通過查找将元素i插入到适當的位置。看看代碼：

Code:

  1. void InsertSort(SqList &list){  
  2.     int i,j;  
  3.     KeyType tmp;  
  4.     for (i=1;i<list.length;i++)  
  5.         if (Compare(list.r[i],list.r[i-1])< 0) {  
  6.             tmp = list.r[i];  
  7.             list.r[i] = list.r[i-1];  
  8.             for (j=( i-2<0?0:i-2 ); Compare(list.r[j], tmp) > 0; j--)  // as soon as list.r[j]> tmp(which is going to insert into the list) lsit.r[j] need   
  9.                 list.r[j+1]=list.r[j];  
  10.             list.r[j+1]=tmp;  
  11.         }  
  12. }  

說說代碼，i從1開始，首先比較r[i]跟r[i-1]，如果r[i]小，則表示r[i]需要往前插，此時，記下r[i]，然後順便将r[i-1]往後移。其實這句可以不寫，因為後面移動元素的時候可以完成這項工作。

下面做的事情是，從i-2開始往前比較，因為i-1比較過了。比較到什麼時候停呢？直到找到一個r[j]，它比tmp要小，其實應該叫ins，表示要插入的元素，這時就停了。就是說一天沒找到比tmp小的元素，就将這個r[j]往後挪: r[j+1]=r[j] 然後 j--,繼續往前找。最後停下來之後，将tmp插入到r[j+1]的位置，為什麼？因為r[j]比tmp小啊，是以j+1就是插入點了。

這裡要注意一下的是，書上的源碼是數列從下标1開始存儲，用r[0]做哨兵，我做了修改，不過就沒有那麼友善了，需要為i=1的時候做一個修正。

然後當時我就想，既然插入排序是往前查找一個比 r[i] 小的數，查找家族中有折半查找啊，通過它不就可以提高算法效率了嗎？果然下一頁就是使用折半查找改進的插入排序，代碼：

Code:

  1. void halfInsertSort(SqList &list){  
  2.     int low, high,mid;  
  3.     int i,j;  
  4.     KeyType ins;  
  5.     for (i=1;i<list.length;i++)  
  6.         if (Compare(list.r[i],list.r[i-1]) < 0 )  {  
  7.             //ins is the element which is going to be inserted.  
  8.             ins=list.r[i];  
  9.             list.r[i]=list.r[i-1];  
  10.             low = 0;  
  11.             high = i-1;  
  12.             while (low<=high){  
  13.                 mid = (low + high) /2;  
  14.                 //If ins > r[mid] , it means the inserting point is at the posterior segment, so move low to mid+1   
  15.                 if (Compare(ins,list.r[mid]) >= 0 ) low=mid+1;  
  16.                 else high = mid-1;  
  17.             }  
  18.             //move elements  
  19.             //Attention: low = high+1  
  20.             for (j=i-1;j>low;j--) list.r[j]=list.r[j-1];  
  21.             //insert ins to the inserting point  
  22.             list.r[low] = ins;    
  23.         }  
  24. }  

整個步驟都是一樣的，還是從i =1開始，比較i和i-1，如果i小，即是由插入的可能，然後接下來的事情就不同了。接下來是折半查找啊。經典算法了：low=0,high=i-1。這就是說，要在區間[0,i-1]中找到一個最終插入的點。有人可能要問，折半查找，通常區間中肯定有一個元素跟ins（被插入元素）是相等的，就是說能定位到唯一一個點，然後這裡通常都找不到跟ins一樣的元素，應該是怎樣的呢？

我也想過這個問題。不妨這樣來想，用二分查找，是為了找到一個插入點，而它應該就是離ins最近，然後又比它小的元素。我們用ins跟r[mid]比較，如果ins比這個中間元素要大，那表示說，在後半個區間裡，還可能會有比ins小而且離ins跟近的元素。反之，如果Ins比中間元素小，那就繼續向前找咯。  其次，最終循環結束的條件是low>high，而這個時候的前一狀态，是low=high。我們可以肯定一點，無論如何，low和high最後肯定會有相等的時候。而這個時候mid=low=high，而這時的r[mid]，應該就是我們要找的元素了。看看最後的比較吧：如果元素比ins比較小，還是一樣，low=mid+1=low+1, 如果元素比ins大，high=mid-1=high-1。我們容易知道，最後的這個元素，其實是有可能比ins大，也有可能小的，如果這個元素是比ins小的，那插入點在這個元素之後，如果這個元素比ins大，插入點就是這個元素所在的下标。我們不妨對比一下，這兩行“如果”，那麼插入點是什麼就出來了：low或者high+1. 事實上，他們兩個也是相等的，是以，用哪個都行。

後面還有一個二路插入排序和希爾排序。還沒有将代碼寫出來，是以暫時跳過。：）

交換排序

接下來是交換排序。就是說，這類排序是通過交換兩個元素來實作的。經典的冒泡排序就是交換排序的典型例子。

我們來看冒泡排序的代碼：

Code:

  1. void BubbleSort(SqList &list){  
  2.     int i,j;  
  3.     for (i=list.length-1;i>=0;i--)  
  4.         for (j=0;j<i;j++){  
  5.             if (Compare(list.r[j],list.r[j+1]) > 0 ) //If r[j]>r[j+1] then let r[j+1] move fowards.   
  6.                 Swap(list.r[j],list.r[j+1]);  
  7.         }  
  8. }  

呵呵，很簡單的一個算法。對算法的基本了解是：讓大（或者小）的元素往數組後面走，第一次是就将最大的放到最後，然後将第二大的放在倒數第二個位置，以此類推。展現在算法中就是兩層循環，外循環控制的是元素最終放置的位置，即從最後一個往前推，外層循環每完成一次，即有一個元素放置在後面。内層循環控制元素的“冒泡”。即從第一個元素一直到i-1,i是最終放置的位置。如果r[j]比r[j+1]大，就把他倆交換。這樣最終肯定将前i個元素中最大的那個移動到i處。

接下來出場的是快速排序。快排被教科書上定性為擁有最佳平均性能的排序算法。那當然是要着重掌握的了。快速排序的核心觀點是，如果能夠将一個無序序列對一個點而言分成兩段，在點的前面的一段中的所有元素都比該店的元素要小，而後段的所有元素都比該點的元素要大，而這個點稱為pivot, 樞軸。如果能這樣做的話，就可以不斷對子序列進行同樣操作，即遞歸的方法對一個無序序列進行排序了。

還是看看代碼吧：

Code:

  1. void quickSort(SqList &list,int low ,int high){  
  2.     if (low < high) {  
  3.         int pivot_location = partition(list,low,high);  
  4.         quickSort(list,low,pivot_location - 1 );  
  5.         quickSort(list,pivot_location + 1, high);  
  6.     }  
  7. }  
  8. int partition(SqList &list,int low,int high){  
  9.     KeyType pivot_key = list.r[low];  
  10.     while (low<high){  
  11.         while (low<high && list.r[high] >= pivot_key ) high--;  
  12.         //Swap(list.r[low],list.r[high]);  
  13.         list.r[low] = list.r[high];  
  14.         while (low<high && list.r[low] <= pivot_key) low++;  
  15.         //Swap(list.r[low],list.r[high]);  
  16.         list.r[high] = list.r[low];  
  17.         }  
  18.         list.r[low] = pivot_key;  
  19.         return low;  
  20. }  

主體很簡單，就是一個遞歸調用，定義了一個頭low，一個尾high，兩個指針，表示的是序列的頭尾。關鍵的函數是Partition，它負責對子序列進行分段，并且傳回樞軸的位置。

是以重點還是在如何分段和計算樞軸，書上的算法是：取序列的第一個元素作為樞軸元素，然後從high，也就是序列的尾部從後往前找：high--，找到第一個小于樞軸元素的元素，然後将這個元素賦給r[low]；然後從序列的頭部從前往後找：low++，将找到的第一個大于樞軸元素的元素賦給r[high]。重複着兩個動作，直到low>=high，其實也就是low=high，最終跳出循環的條件肯定就是low和high指向同一個元素了。而這個元素所在的位置，應該是最後一個被找到并且的元素（不管是比樞軸元素大，還是比他小），而且，這個位置恰恰就是樞軸元素應該在的位置，是以将樞軸元素放回去，傳回low或者high都可以。（二者相等）

看回這個方法本身，首先，令第一個元素為樞軸元素，然後從頭和尾兩端進行推壓，将靠後的比樞軸元素小的元素往前挪，将靠前的比樞軸元素大的元素往後挪，通過前後元素的反複交換，進而最終得到一個對樞軸元素而言，分别較大和較小的序列。（個人感覺還是很玄妙的，而且仍然沒有領悟到它的精髓，請大家指教哈）

選擇排序

簡單選擇排序的政策是從i到n的序列中，選擇裡面最小（或者大）的元素放在i處。這是最最樸素的排序算法了。這沒什麼好說的了，貼代碼完事：

Code:

  1. void SelectSort(SqList &list){  
  2.     int i,j;  
  3.     int max_pointer;  
  4.     KeyType max;  
  5.     for (i=0;i<list.length-1;i++){  
  6.         max = list.r[i];  
  7.         max_pointer = i;  
  8.         for (j=i+1;j<list.length;j++)     
  9.             if (Compare(list.r[j],max) > 0 ) {  
  10.                  max = list.r[j];  
  11.                  max_pointer = j;  
  12.             }  
  13.         if (max_pointer!=i) Swap(list.r[i],list.r[max_pointer]);  
  14.     }  
  15. }  

重點是堆排序。

還是要說一下改進簡單排序算法的思想。由于在選擇最小/最大元素的過程，有許多重複的比較，這就為改進提供了可能。怎麼重複法呢？比如A>B，B>C，那麼肯定A>C，根本無需再做比較。這種排序思想就是錦标賽排序，就是說跟比賽的晉級是一樣的道理，兩兩相比，強者晉級，然後這些強者再進行兩兩相比。結果就出現了二叉樹的形狀。

可以使用完全二叉樹這種資料結構來實作，其中，每個非終端節點都是孩子結點中的較小者（或較大者），于是根節點上的就是最小或最大的元素。那如何實作排序輸出呢？方法是首先輸入根節點，然後将葉子節點中等于根節點的那個節點設為MAX（某個大值），然後再按照父節點是孩子節點中較小者（較大者）這個原則來重新調整二叉樹。重複以上步驟，直到全部節點都輸出完畢。

然而這個方法還是被批評輔助空間較多，與MAX進行多餘比較。是以J.willioms在1964年提出了堆排序（我膜拜一下）。

堆排序，首先要介紹的是堆，這種資料結構，它是一棵完全二叉樹（是以可以使用數組來實作），其中，堆中的所有的父親節點都比它的兩個孩子要大（或者小）

堆排序算法即是利用了堆這種資料結構，以大頭堆為例（即父節點比孩子節點都大的堆）如果存在這樣的堆，則根節點一定是最大的元素，将其輸出，然後對剩餘的n-1個結點重新進行堆重建，結果得到的堆的根節點就是次大的元素。重複執行上述步驟，即可完成堆排序。

那如何建立堆呢？這個問題是最關鍵的。

思想很簡單，對一棵無序的完全二叉樹，從最後一個非終端節點開始到根節點進行調整，将父節點與孩子節點中最大的那個交換。當然如果父親節點已經是三者中最大的那個，就當然不用換了。如果發生了交換，需要注意，交換後的孩子節點（他可能也是某子樹中的父親節點）有沒有破壞堆的性質，如果有，則需要繼續進行調整，直到到達終端節點。

按照上面的步驟得到一個堆之後，還需要進一步的調整，已使之成為一個有序的完全二叉樹。如何辦到呢？方法是，将根節點，即最大的元素，與二叉樹中最後的節點交換，這就等于說，将最大的元素放到最後。然後對1-n-1的完全二叉樹進行堆調整。因為是對1-n-1這些節點進行調整，是以最大的元素已經被排除在外了。然後調整後，又得到一個次大的元素，又可以将其放置在n-1的位置上，将n-1位置上原來的元素放在堆頂。依此步驟重複，直到最後堆剩一個元素。至此完全二叉樹有序。

來看看代碼吧：

Code:

  1. void heapSort(HeapList &list){  
  2.     int i ;  
  3.     for (i=list.length/2-1;i>=0;i--){  
  4.         heapAdjust(list,i,list.length-1);     
  5.     }  
  6.     for (i=list.length-1;i>=0;i--){  
  7.         Swap(list.r[0],list.r[i]);  
  8.         heapAdjust(list,0,i-1);  
  9.     }  
  10. }  
  11. void heapAdjust(HeapList &list,int first,int last){  
  12.     int j;  
  13.     for (j=(first+1)*2-1 ; j<=last; j=(j+1)*2-1){  
  14.         if ( j<last && Compare(list.r[j],list.r[j+1])<0  ) j++; //this means select the bigger one between r[j] and r[j+1]  
  15.         if ( Compare(list.r[first],list.r[j])>0 ) {   
  16.             break;   
  17.         }   
  18.         Swap(list.r[first],list.r[j]);  
  19.         first=j;  
  20.     }  
  21. }  

需要注意的是在函數heapAdjust中，由于我處理的完全二叉樹是從下标0開始的，是以對左孩子進行定位時，語句是：j=(j+1)*2-1。

歸并排序

歸并排序是基于一種歸并的思想，即對兩個分别有序的序列，可以進行一種歸并的操作，使這兩段序列合并成有序的一段。算法也很簡單，即從頭到尾比較兩個序列，将小的元素放在新的序列中，知道某一段序列結束，然後将另一段序列中剩下的元素全部拷貝到新序列中，算法結束。代碼如下：

Code:

  1. typedef struct{  
  2.     KeyType r[MAX_LENGTH];  
  3.     int length;  
  4. }SqList_ex;  

以上是資料結構，注意結構體中的數組不能用指針。為什麼，下面會詳述。

Code:

  1. void Merge(SqList_ex source,SqList_ex &target, int seg1,int seg1_end,int seg2_end){  
  2.     int i,j;  
  3.     int k=seg1;  
  4.     for (i=seg1,j=seg1_end+1; i<=seg1_end&&j<=seg2_end; ) {  
  5.         if (Compare (source.r[i], source.r[j]) <0 ) target.r[k++]=source.r[i++];  
  6.         else target.r[k++]=source.r[j++];
  7.     }  
  8.     if (i<=seg1_end)   
  9.         for (;i<=seg1_end;i++) {  
  10.             target.r[k++]=source.r[i];  
  11.         }  
  12.     if (j<=seg2_end)  
  13.         for (;j<=seg2_end;j++) {  
  14.             target.r[k++]=source.r[j];  
  15.         }  
  16. }  

算法是很簡單的，需要解釋的是幾個參數，呵呵。

source是需要被合并的結構體（裡面包含了一個數組和它的長度），target是合并後的結構體。seg1，seg1_end是source中數組第一段的起始下表和結束下标，seg1_end+1到seg2_end是第二段的起始下标和結束下标。注意它們是分别有序的兩段序列。

這個不是重點，重點是source和target。看看這個函數是怎樣調用的：

Code:

  1. Merge(list,list,head,mid,tail);  

source跟target的實參都是同一個list結構體！有人會問，這怎麼回事啊。自己跟自己歸并，最後又是寫回自己上，不會出錯嗎？

這裡就涉及C語言參數傳遞和C++的引用了。

因為C語言的參數傳遞基本都是值傳遞（還有一中是指針傳遞，這裡不涉及，是以就不說了~）結構體參數也是值傳遞，是以，在Merge函數中，作為實參傳進來的list變量已經被拷貝到記憶體的另一塊地方了，而它的新名字叫做source。 再看看我們的target，雖然傳進來的實參仍然是list，但是，由于target是一個引用變量，也就是說，進行參數傳遞，或者說形參初始化的時候，隻會對這個引用變量target進行指派，即SqList &target=list，這時候，target就像是list另一個名字一樣，是以對target進行修改，就恰恰是對list進行修改。 總的來說，在Merge的過程中，源數組先拷貝了一份，放在别的一個地方，然後進行歸并并且将結果寫回到原來的數組上。這樣就保證了歸并過程是有效的。

有一點有趣的事情可以跟大家分享一下，在我原來定義的資料結構中SqList（看回本文開始的地方），數組并不是使用[]的定義方式，而是使用了指針，因為指針更能節省記憶體，不需要開辟長度為MAX_LENGTH這麼大的記憶體空間。但是在寫歸并排序的過程中，我發現，使用指針的順序表資料結構是行不通的。 上面代碼都一點不變，但是使用數組指針的結構體

Code:

  1. 1. typedef int KeyType;    
  2. 2.     
  3. 3. typedef struct{    
  4. 4.     KeyType *r;    
  5. 5.     int length;    
  6. 6. }SqList;    

就是會出錯。為什麼呢？呵呵，跟對象的深淺克隆有異曲同工之妙的。 大家不妨想想是不是？ 完整的代碼放上來： Code:

  1. void mergeSort(SqList_ex &list,int head ,int tail){  
  2.     int mid;  
  3.     if (head == tail) return;  
  4.     mid = (head + tail) / 2;  
  5.     mergeSort(list,head,mid);  
  6.     mergeSort(list,mid+1,tail);  
  7.     Merge(list,list,head,mid,tail);  
  8. } 

整個歸并排序的過程就是一個遞歸的過程。将無序序列分成兩段，因為他們還是無序的，是以對他們進行遞歸的再次歸并排序，當他們都歸并有序後，再進行Merge的歸并操作即可。 反回來說，就是先把相鄰的兩個元素進行合并（它們長度為1，肯定分别有序），然後再将相鄰的2個有序的長度為2的子序列進行合并，最終實作整個序列的有序化。這個方法其實真名是二路歸并排序。其實還有多路歸并排序，不過屬于外部排序的範疇，以後再寫一篇學習日志了。  

to be con..

資料結構 算法 list pivot merge 終端
上一篇: python腳本提取葉綠體基因組的大小單拷貝區、反向重複區
下一篇: WHO總幹事《柳葉刀》發文力挺中國戰疫科學家！Nature确診标準大讨論

繼續閱讀