《排序算法篇》归并排序的递归与非递归写法解析

一、本章重点💤

• 归并的排序思想
• 归并排序递归实现
• 归并排序非递归实现
• 归并排序复杂度计算

二、归并💤

💦2.1归并的排序思想

归并：就是指合并的意思

归并排序：简单来说就是不断合并两个有序的数组，达到排序的目的。

如：数组一：1 3 5 7 9 数组二：2 4 6 8 10

合并后：1 2 3 4 5 6 7 9 10

给定一个数组 1 7 5 10 9 8 2 4 6 3，怎么通过归并的思想进行排序？

先将该数组分成两半，左半部分是：1 7 5 10 9 右半部分是：8 2 4 6 3

但左右两边都不是有序的，因此我们需要让左半部分有序、右半部分有序之后再将这两个有序数组合并。

再将左半部分看成要排序的新数组，将左半部分分成两半

它的左半部分是：1 7 它的右半部分是：5 10 9

它的左右都不一定是有序的

再将左半部分看成要排序的新数组，将左半部分分成两半

它的左半部分是：1 它的右半部分是：7

此时左半部分只有一个数，那么可以认为左半部分是有序的。

右半部分也是一个数，也有序。然后归并一下，那么 1 7就是有序的，然后将 5 10 9再分

直到分成一个数，再归并让 5 10 9 也有序：5 9 10.

再归并1 7和 5 9 10：1 5 7 9 10

8 2 4 6 3也是如此。。。。。。

图解：

本质上就是分分合合的过程

💦2.2递归实现

合并两个有序数组时，需要一个临时的数组空间，这里用temp做这个临时的数组。

注意：二分时，不能end1=mid-1、begin2=mid

参考代码：

void _merge(int* a, int* temp, int begin ,int end)//递归
{
    if (begin >= end)
    {
        return;
    }
    int mid = begin + ((end - begin) >> 1);
    int begin1 = begin;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = end;
    _merge(a, temp, begin1, end1);
    _merge(a, temp, begin2, end2);
    //合并两个有序数组
    int index = begin;//记录begin
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            temp[begin++] = a[begin1++];
        }
        else
        {
            temp[begin++] = a[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        temp[begin++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        temp[begin++] = a[begin2++];
    }
    //这里一定要拷贝回去，否则递归返回的时候左右两边不是有序的
    memmove(a + index, temp + index, sizeof(int) * (end - index + 1));
}

💦2.3非递归实现

非递归实现的思路是：11归并、22归并、44归并.....

以下面数组为例：

这种非递归实现的思路和递归差不多，只不过它们归并的顺序是不一样的

递归实现的顺序：

参考代码：

void _merge(int* a, int* temp, int n)//非递归
{
    int gap = 1;
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            int j = i;
            int begin1 = i;
            int end1 = i + gap - 1;
            int begin2 = end1 + 1;
            int end2 = begin2 + gap - 1;
            //越界调整
            if (end1 >= n)
            {
                end1 = n - 1;
            }
            if (begin2 >= n)
            {
                begin2 = n;
                end2 = n - 1;
            }
            if (begin2 < n && end2 >= n)
            {
                end2 = n - 1;
            }
            //当gap==1时就是11归、等于2就是22归
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                {
                    temp[j++] = a[begin1++];
                }
                else
                {
                    temp[j++] = a[begin2++];
                }
            }
            while (begin1 <= end1)
            {
                temp[j++] = a[begin1++];
            }
            while (begin2 <= end2)
            {
                temp[j++] = a[begin2++];
            }
        }
        //注意这里可以11归并之后再拷贝上去。
        memmove(a, temp, sizeof(int) * n);
        gap *= 2;
    }
    free(temp);
}

越界调整补充说明：

end1、begin2、end2都有可能会越界

begin2越界：

end2越界：

end1越界：

💦2.4归并排序复杂度计算

高度是logN，每层遍历是O（N），时间复杂度是O（N*logN）。

空间复杂度是O（N）