C++归并排序

1 算法核心思想

归并排序是一种高效的排序方式，需要用到递归来实现，我们先来看一下动图演示：

算法核心思想如下：

1.将数组尽量平均分成两段。

2.将这两段都变得有序（使用递归实现）。

3.将两段合并。

2 代码实现

首先，我们先定义一个归并排序的函数，里面接受三个参数：

void MergeSort(int arr[], int left, int right) {
    
}

arr代表需要进行排序的数组，left表示数组arr的最左端点，right表示数组arr的最右端点。

首先我们需要把数组分成两段，我们可以用二分的方法：

int mid = (left + right) >> 1;

这里右移（>>为右移运算符）1为和除以2含义相同。

也可以用防溢出，因为left+right的值可能会爆int，导致结果错误：

int mid = left + (right - left) >> 1;

然后对两段分别进行递归，第一段是[1, mid]，第二段是[mid+1, right]：

MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);

由于我们需要对数组进行操作，但是直接在arr操作可能会导致原始数据丢失，但是如果再创建一个数组会占用内存，所以我们可以向电脑“租借”right-left+1个空间，用关键字new来完成：

int* tmp = new int[right - left + 1];

注意要以指针的形式定义。

由于我们要把数组变得有序，而我们归并排序的思想就是分而治之，然后再依次变得有序，需要用到分治的思想。那么我们先定义一些变量：

int cur = 0, cur1 = left, cur2 = mid + 1;

cur为tmp数组的元素下标，cur1为第一段的最左端点，cur2为第二段的最左端点。

然后我们对tmp数组和arr数组进行循环操作，这里可以用while循环，循环条件是cur1<=mid&&cur2<=right。

如果arr[cur1]比arr[cur2]更大，那么就先把arr[cur2]放回tmp，否则放arr[cur1]。

代码：

while(cur1 <= mid && cur2 <= right)
{
    if(arr[cur1] < arr[cur2])
        tmp[cur++] = arr[cur1++];
    else
        tmp[cur++] = arr[cur2++];
}

然后处理可能有的数组残余未处理的部分：

while(cur1 <= mid)
    tmp[cur++] = arr[cur1++];
while(cur2 <= right)
    tmp[cur++] = arr[cur2++];

然后合并数组，方法跟处理时差不多的：

for(int i = 0; i < right - left + 1; i++)
    arr[left + i] = tmp[i];

就是把tmp的元素依次赋值给arr。

最有我们需要把tmp的空间还给内存，所以我们delete一下：

delete[] tmp;

然后我们的arr就变的有序了。

但是，如果这样写，程序就成功被我们干崩了，因为我们忘记写递归出口了，补一个递归出口：

if(left == right)
    return;

我们合并一下整段代码：

void MergeSort(int arr[], int left, int right) {
    if(left == right)
        return;
    int mid = (left + right) >> 1;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    int* tmp = new int[right - left + 1];
    int cur = 0, cur1 = left, cur2 = mid + 1;
    while(cur1 <= mid && cur2 <= right)
    {
        if(arr[cur1] < arr[cur2])
            tmp[cur++] = arr[cur1++];
        else
            tmp[cur++] = arr[cur2++];
    }
    while(cur1 <= mid)
        tmp[cur++] = arr[cur1++];
    while(cur2 <= right)
        tmp[cur++] = arr[cur2++];
    for(int i = 0; i < right - left + 1; i++)
        arr[left + i] = tmp[i];
    delete[] tmp;
}

3 算法时间复杂度

正常情况下，归并排序时间复杂度为：

O(NLogN)

再见！