归并排序，咋归并呢？

作者丨飘渺Jam

来源丨JAVA日知录（ID：javadaily）

大家好，我是道哥，今天我们来聊归并排序。

对于冒泡排序、插入排序和选择排序而言，它们的平均时间复杂度都是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 

归并排序是非常重要的算法，我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。

你好，我是道哥，CSDN前30名，曾混迹于BAT大厂。公众号讲解计算机基础、网络、数据结构、算法、C++、Java、Golang等多方面的编程知识。

点分享

点点赞

点在看