歸併排序，咋歸併呢？

大家好，我是道哥，今天我們來聊歸併排序。

對於冒泡排序、插入排序和選擇排序而言，它們的平均時間複雜度都是 O(N*N)，那麼，有沒有時間複雜度更低的排序呢？

當然有啊，比如我們今天要聊的歸併排序，它的時間複雜度是 O(N*logN)，接下來，我們一起看看歸併排序的思路。

圖解歸併

有 5 個同學，他們的身高如下，需要按照身高進行排序：

步驟一：

先任意抓 2 個人出來比較，比如用 180cm 和 160cm 進行比較，得出的排序結果如下：

步驟二：

另外再抓 2 個進行比較，比如用 170cm 和 150cm 進行比較，得出的排序結果如下：

步驟三：

把剩下的 190cm 歸併到男生這一隊中，發現他比 150cm 高，所以要放在 150cm 的右邊，繼續比較發現他比 170cm 也高，所以繼續放到 170cm 的右邊，結果如下：

到此爲止，我們形成了如下兩個有序排序，即：

接下來的任務就是對這兩個有序的排隊進行歸併，也是歸併排序的核心，操作如下：

step1:

把 150cm 的同學放到女生的排隊中，發現 150cm 比 160cm 小，所以放到最左邊，結果如下：

step2:

把 170cm 的同學放到女生排隊中，從左到右逐個比較，最後發現他應該處在 160cm 和 180 之間，結果如下：

step3:

把 190cm 的同學放到女生排隊中，從左到右逐個比較，最後發現他應該放到 180cm 之後，也就是處在最右邊，結果如下：

到此爲止，所有的同學排成了一隊，身高從低到高。從如上過程中，很容易體會到歸併的思路，這種排序就是歸併排序，其最重要的思想是：針對兩個有序的排列進行合併。

代碼實現

接下來，我們用 C++ 代碼來實現歸併排序：

#include<iostream>
using namespace std;
//有序表a[first...mid]和a[mid + 1...last]的歸併
void merge(int a[], int first, int mid, int last)
{
  int length = last - first + 1;
  int i = first;
  int j = mid + 1;
  int k = 0;
  int *p = new int[length];
  while(i <= mid && j <= last)
  {
    if(a[i] <= a[j]) 
    {
      p[k++] = a[i++];
    }
    else
    {
      p[k++] = a[j++];
    }
  }
  while(i <= mid)
  {
    p[k++] = a[i++];
  }
  while(j <= last)
  {
    p[k++] = a[j++];
  }
  for(k = 0; k < length; k++)
  {
    a[k + first] = p[k];
  }
  delete [] p;
  p = NULL;
}
// 遞歸地進行歸併排序
void mergeSort(int a[], int first, int last)
{
  int mid = (first + last) / 2;
  if(first < last)
  {
    mergeSort(a, first, mid);
    mergeSort(a, mid + 1, last);
    merge(a, first, mid, last);
  }
}
int main()
{
  int a[] = {160, 150, 180, 190, 170};
  int n = sizeof(a) / sizeof(a[0]);
  mergeSort(a, 0, n - 1);
  int i;
  for(i = 0; i < n; i++)
  {
    cout << a[i] << " ";
  }
  cout << endl;
  return 0;
}

經測試程序 OK, 結果爲：

150 160 170 180 190

歸併排序是非常重要的算法，我們也會一步一個腳印，爭取每篇文章講清講透一件事，也希望大家閱讀後有所收穫，心情愉快。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/3bWP5NH695HX-ehy2Dkiqw

圖解歸併

代碼實現

猜你喜歡