數據結構之內外排序

• 2019 年 12 月 2 日
• 筆記

一、內排序

1．插入排序（InsertSort）

插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那麼插入元素把想插入的元素放在相等元素的後面。這樣，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，所以插入排序是穩定的。

插入排序是對冒泡排序的改進。它比冒泡排序快2倍。一般不用在數據大於1000的場合下使用插入排序，或者重複排序超過200數據項的序列。

void insertSort(int a[],int n)   //插入排序  {      int i,j;      int t;      for(i=1;i<n;i++)      {          t=a[i];   //保存當前無序表中的第一個數據          j=i-1;          while(j>=0 && a[j]>t)          {              a[j+1]=a[j];              j--;          }          a[j+1]=t;   //將數據插入有序表中      }  }  

2．希爾排序（ShellSor）

希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對於有序的序列效率很高。所以，希爾排序的時間複雜度會比O(n2)好一些。由於多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以shell排序是不穩定的。

Shell排序的分組合理性會對演算法產生重要的影響。現在多用D.E.Knuth的分組方法。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相對比較簡單，它適合於數據量在5000以下並且速度並不是特別重要的場合。它對於數據量較小的數列重複排序是非常好的。

void shellSort(int a[],int n)   //希爾排序  {      int i,j,gap;      int t;      for(gap=n/2;gap>0;gap/=2)          for(i=gap;i<n;i++)          {              t=a[i];              j=i-gap;              while(j>=0 &&a[j]>t)              {                  a[j+gap]=a[j];                  j-=gap;              }              a[j+gap]=t;          }  }  

3．冒泡排序（BubbleSort）

冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，就不會再把它們倆交換一下的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。

冒泡排序是最慢的排序演算法，在實際運用中它是效率最低的演算法。

void bubbleSort(int a[],int n)   //冒泡排序  {      int i,j;      int t;      for(i=0;i<n;i++)          for(j=0;j<n-i-1;j++)              if(a[j]>a[j+1])              {                  t=a[j];                  a[j]=a[j+1];                  a[j+1]=t;              }  }  

4．快速排序（QuickSort）

快速排序有兩個方向，左邊的i下標一直往右走，當a[i]<= a[center_inde]，其中center_index是中樞元素的數組下標，一般取為數組第0個元素。而右邊的j下標一直往左走，當a[j]> a[center_index]。如果i和j都走不動了，i<= j, 和a[j],重複上面的過程，直到i>j。交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂，比如序列為{5，3，3，4，3，8，9，10，11}，現在中樞元素5和3（第5個元素，下標從1開始計）交換就會把元素3的穩定性打亂，所以快速排序是一個不穩定的排序演算法，不穩定發生在中樞元素和a[j]交換的時刻。

快速排序是一個就地排序，分而治之，大規模遞歸的演算法。從本質上來說，它是歸併排序的就地版本。快速排序可以由下面四步組成。 ⑴如果不多於1個數據，直接返回。 ⑵一般選擇序列最左邊的值作為支點數據。 ⑶將序列分成2部分，一部分都大於支點數據，另外一部分都小於支點數據。 ⑷對兩邊利用遞歸排序數列。

快速排序比大部分排序演算法都要快。儘管我們可以在某些特殊的情況下寫出比快速排序快的演算法，但是就通常情況而言，沒有比它更快的了。快速排序是遞歸的，對於記憶體非常有限的機器來說，它不是一個好的選擇。

void quickSort(int a[],int s,int e)  //對a[s]至a[e]的元素進行快速排序  {      int i=s,j=e;      int t;      if(s<e)      {          t=a[s];          while(i!=j)          {              while(j>i && a[j]>t) j--;  //從右向左掃描，找第一個小於t的a[j]              if(i<j)  //表示找到這樣的a[j]              {                  a[i]=a[j];                  i++;              }              while(i<j && a[i]<=t) i++;   //從左向右掃描，找第一個大於t的a[i]              if(i<j)   //表示找到這樣的a[i]              {                  a[j]=a[i];                  j--;              }          }          a[i]=t;    //將a[s]放到a[s]至a[e]的恰當位置i處，使得其左邊的元素都不大於它，其右邊的元素都不小於它。          quickSort(a,s,i-1);    //對左區間遞歸排序          quickSort(a,i+1,e);    //對右區間遞歸排序      }  }  

5．選擇排序（SelectSort）

選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩餘元素裡面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那麼，在一趟選擇，如果當前元素比一個元素小，而該小的元素又出現在一個和當前元素相等的元素後面，那麼交換後穩定性就被破壞了。例如，序列{5，8，5，2，9}，第一趟選擇第1個元素5會和2交換，那麼原序列中2個5的相對前後順序就被破壞了，所以選擇排序不是一個穩定的排序演算法。

在實際應用中處於和冒泡排序基本相同的地位。它們只是排序演算法發展的初級階段，在實際中使用較少。

void selectSort1(int a[],int n)   //選擇排序  {      int i,j;      int t;      for(i=0;i<n-1;i++)   //數據起始位置，從0到倒數第二個數據          for(j=i+1;j<n;j++)   ////在剩下的數據中循環          {              if(a[i]>a[j])    // //如果有比它小的，交換兩者              {                  t=a[i];                  a[i]=a[j];                  a[j]=t;              }          }  }    void selectSort2(int a[],int n)   //選擇排序的改進，減少了交換的次數  {      int i,j,small;      int t;      for(i=0;i<n-1;i++)  //數據起始位置，從0到倒數第二個數據      {          small=i;    //記錄最小數據的下標          for(j=i+1;j<n;j++)   //在剩下的數據中尋找最小數據          {              if(a[j]<a[small])   //如果有比它更小的，記錄下標                  small=j;          }          t=a[small];    //將最小數據和未排序的第一個數據交換          a[small]=a[i];          a[i]=t;      }  }  

6．堆排序（HeapSort）

堆的結構是結點i的孩子為2i和2i+1節點，大頂堆要求父結點大於等於其2個子結點，小頂堆要求父結點小於等於其2個子結點。在一個長為n的序列，堆排序的過程是從第n/2開始和其子結點共3個值選擇最大（大頂堆）或者最小（小頂堆），這3個元素之間的選擇當然不會破壞穩定性。但當為n/2-1,n/2-2, …1這些個父結點選擇元素時，就會破壞穩定性。有可能第n/2個父節點交換把後面一個元素交換過去了，而第n/2-1個父結點把後面一個相同的元素沒有交換，那麼這2個相同的元素之間的穩定性就被破壞了。所以，堆排序不是穩定的排序演算法。

堆排序適合於數據量非常大的場合（百萬數據）。堆排序不需要大量的遞歸或者多維的暫存數組。這對於數據量非常巨大的序列是合適的。比如超過數百萬條記錄，由於快速排序，歸併排序都使用遞歸來設計演算法，在數據量非常大的時候，可能會發生堆棧溢出錯誤。堆排序會將所有的數據建成一個堆，最大的數據在堆頂，然後將堆頂數據和序列的最後一個數據交換。接下來再次重建堆，交換數據，依次下去，就可以排序所有的數據。

void max_heapify(int a[], int start, int end)   //調整為大頂堆  {      //父結點和子結點下標      int dad = start, son = start * 2 + 1;      while(son <= end)   //子結點下標在數組範圍內才能比較      {          //先比較左右孩子的大小，選擇大孩子的下標          if(son+1 <= end && a[son+1] > a[son]) son++;            if(a[son] > a[dad])          {              int t = a[son];              a[son] = a[dad];              a[dad] = t;              dad = son;              son = dad * 2 + 1;          }          else              break;      }  }    void heapSort(int a[], int n)   //堆排序  {      int i;      //初始化數組為大頂堆，i=n/2-1表示最後一個父結點的下標      for(i=n/2-1; i>=0; i--) max_heapify(a, i, n-1);        for(i=n-1; i>0; i--)    //根作為最大值調整到當前序列的最後      {          int t = a[0];          a[0] = a[i];          a[i] = t;          max_heapify(a, 0, i-1);      }  }  

7．歸併排序（MergeSort）

歸併排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素（認為直接有序）或者2個序列（1次比較和交換）,然後把各個有序的段序列合併成一個有序的長序列，不斷合併直到原序列全部排好序。可以發現，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也沒有人故意交換，這不會破壞穩定性。那麼，在短的有序序列合併的過程中，穩定是是否受到破壞？沒有，合併過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素保存在結果序列的前面，這樣就保證了穩定性。所以，歸併排序也是穩定的排序演算法。

歸併排序比堆排序稍微快一點，但是需要比堆排序多一倍的記憶體空間，因為它需要一個額外的數組。

void mergearray(int a[], int first, int mid, int last, int temp[])  //將有二個有序數列a[first...mid]和a[mid+1...last]合併。  {      int i=first, j=mid+1;      int m=mid, n=last;      int k=0;      while (i<=m && j<=n)      {          if (a[i]<a[j])              temp[k++]=a[i++];          else              temp[k++]=a[j++];      }      while (i<=m)          temp[k++]=a[i++];      while (j<=n)          temp[k++]=a[j++];      for (i=0;i<k;i++)          a[first+i]=temp[i];  }    void mergesort(int a[], int first, int last, int temp[])  {      if (first<last)      {          int mid=(first+last)/2;          mergesort(a, first, mid, temp);    //左邊有序          mergesort(a, mid+1, last, temp);  //右邊有序          mergearray(a, first, mid, last, temp);   //再將二個有序數列合併      }  }    void MergeSort(int a[], int n)  {      int *p=(int *)malloc(n*sizeof(int));      mergesort(a, 0, n - 1, p);      free(p);  }  

8．基數排序（RadixSort）

基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優先順序排序，最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前。基數排序基於分別排序，分別收集，所以其是穩定的排序演算法。

基數排序和通常的排序演算法並不走同樣的路線。它是一種比較新穎的演算法，但是它只能用於整數的排序，如果我們要把同樣的辦法運用到浮點數上，我們必須了解浮點數的存儲格式，並通過特殊的方式將浮點數映射到整數上，然後再映射回去，這是非常麻煩的事情，因此，它的使用同樣也不多。而且，最重要的是，這樣演算法也需要較多的存儲空間。

時間效率：設待排序列為n個記錄，d個關鍵碼，關鍵碼的取值範圍為radix，則基數排序的時間複雜度為O(d(n+radix))，其中，一趟分配時間複雜度為O(n)，一趟收集時間複雜度為O(radix)，共進行d趟分配和收集。

int maxbit(int a[],int n)    //求數組元素的最大位數  {      int d=1,i=0;  //保存最大的位數      int p=10;      for(i=0;i<n;i++)      {          while(a[i]>=p)          {              p*=10;              d++;          }      }      return d;  }    void radixsort(int a[],int n)    //基數排序  {      int d = maxbit(a,n);      long *tmp=(long *)malloc(n*sizeof(long));      long count[10];  //計數器,統計每位基數的個數      long i,j,k;      int radix=1;      for(i=1;i<=d;i++)  //進行d次排序      {          for(j=0;j<10;j++)    //每次分配前清空計數器              count[j]=0;          for(j=0;j<n;j++)   //統計基數出現的次數          {              k=(a[j]/radix)%10;              count[k]++;          }          for(j=1;j<10;j++)  //將tmp中的位置依次分配給每個計數器              count[j]=count[j-1]+count[j];          for(j=n-1;j>=0;j--)  //根據計數器，將記錄依次收集到tmp中          {              k=(a[j]/radix)%10;              count[k]--;              tmp[count[k]]=a[j];          }          for(j=0;j<n;j++)  //將臨時數組的內容複製到數組a中              a[j] = tmp[j];          radix = radix*10;      }      free(tmp);  }  

二、外排序

當待排序的文件比記憶體的可使用容量還大時，文件無法一次性放到記憶體中進行排序，需要藉助於外部存儲器（例如硬碟、U盤、光碟），這時就需要用外部排序演算法來解決。

外部排序演算法由兩個階段構成： 按照記憶體大小，將大文件分成若干長度為 l 的子文件（l 應小於記憶體的可使用容量），然後將各個子文件依次讀入記憶體，使用適當的內部排序演算法對其進行排序（排好序的子文件統稱為「歸併段」或者「順段」），將排好序的歸併段重新寫入外存，為下一個子文件排序騰出記憶體空間； 對得到的順段進行合併，直至得到整個有序的文件為止。

例如，有一個含有 10000 個記錄的文件，但是記憶體的可使用容量僅為 1000 個記錄，毫無疑問需要使用外部排序演算法，具體分為兩步： 1. 將整個文件其等分為 10 個臨時文件（每個文件中含有 1000 個記錄），然後將這 10 個文件依次進入記憶體，採取適當的記憶體排序演算法對其中的記錄進行排序，將得到的有序文件（初始歸併段）移至外存。 2. 對得到的 10 個初始歸併段進行如圖所示的兩路歸併，直至得到一個完整的有序文件。

有 10 個初始歸併段到一個有序文件，共進行了 4 次歸併，每次都由 m 個歸併段得到 ⌈m/2⌉ 個歸併段，這種歸併方式被稱為 2-路平衡歸併。

對於外部排序演算法來說，影響整體排序效率的因素主要取決於讀寫外存的次數，即訪問外存的次數越多，演算法花費的時間就越多，效率就越低。

對於同一個文件來說，對其進行外部排序時訪問外存的次數同歸併的次數成正比，即歸併操作的次數越多，訪問外存的次數就越多。使用2-路平衡歸併的方式，舉一反三，還可以使用 3-路歸併、4-路歸併甚至是 10-路歸併的方式，下圖為 5-路歸併的方式： 對於 k-路平衡歸併中 k 值得選擇，增加 k 可以減少歸併的次數，從而減少外存讀寫的次數，最終達到提高演算法效率的目的。除此之外，一般情況下對於具有 m 個初始歸併段進行 k-路平衡歸併時，歸併的次數為：s=」logk⁡m」（其中 s 表示歸併次數）。

從公式上可以判斷出，想要達到減少歸併次數從而提高演算法效率的目的，可以從兩個角度實現： 1. 增加 k-路平衡歸併中的 k 值； 2. 盡量減少初始歸併段的數量 m，即增加每個歸併段的容量。