AcWing 787. 归并排序

归并排序介绍

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（\(Divide~and~Conquer\)）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序思想

它的基本思想：归并排序，首先把一个数组中的元素，按照某一方法，先拆分了之后，按照一定的顺序各自排列，然后再归并到一起，使得归并后依然是有一定顺序的 。归并排序算法可以利用递归的思想或者迭代的思想去实现。首先我们先把一个无序的数组去拆分，然后利用一定的规则，去合并。类似于二叉树的结构。

归并排序流程

  • 把长度为n的输入序列分成两个长度为 \(n/2\) 的子序列；
  • 对这两个子序列分别采用归并排序；
  • 将两个排序好的子序列合并成一个最终的排序序列。

具体实现？

第一步，划分子区间：每次递归的从中间把数据划分为左区间和右区间。原始区间为 \([start,end]\)，\(start=0\)，\(end=len-1\)，减一是因为数组的下标从 \(0\) 开始。然后从中间元素划分，划分之后的左右区间分别为 \([start,(end-start+1)/2+start]\)，右区间为 \([(end-start+1)/2+start+1,end]\)。重复过程，直到每个子区间只有一个或者两个元素。

第二步，合并子区间：子区间划分好以后，分别对左右子区间进行排序，排好序之后，在递归的把左右子区间进行合并。

  • 开辟一个数组 \(a\)，存放 \(l\) 到 \(q\) 之间（也就是需要归并的左边数组）的元素；
  • 开辟一个数组 \(b\)，存放 \(q\) 到 \(r\) 之间（也就是需要归并的右边数组）的元素；
  • \(a\) 与 \(b\) 中的数字逐个比较，把较小的先放在数组 \(A\) 中（从数组 \(a_0\) 开始存放，依次往后覆盖原来的数），然后较小的数组指针往后移动，指向下一位再和另外一个数组比较。

动图演示

算法稳定性与时间复杂度

归并排序稳定性

算法稳定性：假设在数列中存在 \(a_i = a_j\)，若在排序之前，\(a_i\) 在 \(a_j\) 前面；并且排序之后，\(a_i\) 仍然在 \(a_j\) 前面,则这个排序算法是稳定的。

归并排序是 稳定 的算法。

归并排序时间复杂度

了解归并排序的应该都知道，归并排序的时间复杂度是 \(O(nlogn)\)，且这个时间复杂度是稳定的，不随需要排序的序列不同而产生波动。那这个时间复杂度是如何得来的呢？我们可以这样分析，假设我们需要对一个包含n个数的序列使用归并排序，并且使用的是递归的实现方式，那么过程如下：

  • 递归的第一层，将 \(n\) 个数划分为 \(2\) 个子区间，每个子区间的数字个数为 \(n/2\)；
  • 递归的第二层，将 \(n\) 个数划分为 \(4\) 个子区间，每个子区间的数字个数为 \(n/4\)；
  • 递归的第三层，将 \(n\) 个数划分为 \(8\) 个子区间，每个子区间的数字个数为 \(n/8\);
    ……
  • 递归的第 \(logn\) 层，将 \(n\) 个数划分为 \(n\) 个子区间，每个子区间的数字个数为 \(1\)；

而归并排序的合并操作，则是从最底层开始（子区间为 \(1\) 的层），对相邻的两个子区间进行合并，过程如下：

  • 在第 \(logn\) 层，每个子区间的长度为 \(1\)，共 \(n\) 个子区间，每相邻两个子区间进行合并，总共合并 \(n/2\) 次。\(n\) 个数字都会被遍历一次，所有这一层的总时间复杂度为 \(O(n)\)；
    ……
  • 在第二层，每个子区间长度为 \(n/4\)，总共有 \(4\) 个子区间，每相邻两个子区间进行合并，总共合并 \(2\) 次。\(n\) 个数字都会被遍历一次，所以这一层的总时间复杂度为 \(O(n)\)；
  • 在第一层，每个子区间长度为 \(n/2\)，总共有 \(2\) 个子区间，只需要合并一次。\(n\) 个数字都会被遍历一次，所以这一层的总时间复杂度为 \(O(n)\)；

我们可以发现，对于每一层来说，在合并所有子区间的过程中，\(n\) 个元素都会被操作一次，所以每一层的时间复杂度都是 \(O(n)\)。而之前我们说过，归并排序划分子区间，将子区间划分为只剩 \(1\) 个元素，需要划分 \(logn\) 次，共有 \(logn\) 层，所以归并排序的时间复杂度就是 \(O(nlogn)\)。

归并序实现

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 100010;

int a[N], tmp[N]; //a是需要排序的数组，tmp是辅助数组

void merge_sort(int q[], int l, int r)
{
    if (l >= r)
    {
        return;
    }
    int mid = (l + r) >> 1;
    //递归划分子区间
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int i = l, j = mid + 1, cnt = 0;
    //合并子区间
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) //q[i]更小存q[i]
        {
            tmp[cnt ++ ] = q[i ++ ]; //注意cnt和i要+1
        }
        else //存q[j]
        {
            tmp[cnt ++ ] = q[j ++ ]; //记得+1
        }
    }
    while (i <= mid) //左边数组有剩余
    {
        tmp[cnt ++ ] = q[i ++ ];
    }
    while (j <= r) //右边数组有剩余
    {
        tmp[cnt ++ ] = q[j ++ ];
    }
    for (int i = l, j = 0; i <= r; i ++ , j ++ ) //更新q数组
    {
        q[i] = tmp[j];
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; i ++ )
    {
        printf("%d ", a[i]);
    }
    return 0;
}
C++算法ACWING基础课

相关

标签