递归与分治 / 排序 | 3：归并排序（递归与非递归两种实现）

你的名字 2023-07-09 04:23 42阅读 0赞

排序算法是算法领域十分经典的一类算法，它的名字通俗易懂：给数字排序，让一组无序的数据通过排序算法后，能增序或者降序地输出。

排序算法有很多种，本文来详细讲讲 **"归并排序法"**。

（本文均是增序排序，降序排序同理即略）

--------------------

**本文目录**

一、算法理解

二、算法实现

1、merge（合并）的实现

2、mergeSort的实现

Ⅰ、递归实现

Ⅱ、非递归实现

完整代码

--------------------

# 一、算法理解 #

归并排序的算法是分治算法的一个经典应用，它主要是将一个待排序序列平分成两个子序列，将两个子序列排好序后再进行合理地合并，此时所有的序列就有序了。它主要包括分解（divide）和 合并（conquer）两个过程，很好理解的分治法。

下面看看一个实例：

![format_png][]

# 二、算法实现 #

## 1、merge（合并）的实现  ##

归并排序最主要的就是将merge函数搞定，merge函数的功能就是将两个排好序的序列合并成一个有序的大序列。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

哈哈哈哈可以想象一个牌堆的例子来理解：假设桌上有两堆牌面朝上的牌（有序，顶端是最小的），现在我们通过摸牌来合并成一堆有序的牌。那么我们的步骤就是：在两堆牌的顶端中选取较小的那张，将选中的牌移入我们的输出堆（此时被移走的牌的那一堆的顶上将显露一张新的牌）。一直这样重复，到某一堆牌没有了，就将另外一堆牌全部移入我们的输出堆内，这样就完成了merge操作。

注意：

1.  在代码实现的时候**为了方便看是否有一堆牌已经被摸完，我们将最后一张牌的下一张设置成无穷大**。
2.  在实现的时候需要先将两组牌分别拷贝入新的序列，在逐步移动回原数组。

下面是具体代码：

/* 合并数组a的有序序列[l1,r1]与[l2,r2] 至 [l1, r2] */
    void merge(int a[], int l1, int r1, int l2, int r2) {
        int len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;  //两个序列的长度
        int x[MAX_N], y[MAX_N];   //临时分别储存两个序
        /* 分别将两个序列拷贝入数组x、y */
        int t = l1;
        for (int i = 0; i < len1; i++) {
            x[i] = a[t++];
        }
        t = l2;
        for (int i = 0; i < len2; i++) {
            y[i] = a[t++];
        }
        x[len1] = y[len2] = INT_MAX;  //将x、y数组的最后一个有效元素之后赋值无穷大
        /* 合并操作 */
        int i = 0, j = 0;
        for (int k = l1; k <= r2; k++) {
            //每次将较小的放入a数组
            if (x[i] <= y[j])
                a[k] = x[i++];
            else
                a[k] = y[j++];
        }
    }

## 2、mergeSort的实现 ##

mergeSort的实现有两种方法，看你是否使用递归：

### Ⅰ、递归实现  ###

merge实现了就很简单了，递归的思想也很容易理解，直接将待排序数组分治处理就好。递归的终点就是传入的排序数组只有一个元素时，不需要排序，直接返回即可。

代码如下:

/* 递归实现的归并排序：将数组a的[start, end]序列排序 */
    void mergeSort1(int a[], int start, int end) {
        if (start < end) {
            int center = (start + end) / 2;
            mergeSort1(a, start, center);    //分割问题
            mergeSort1(a, center + 1, end);
            merge(a, start, center, center + 1, end);    //合并问题
        }
    }

这种实现下的归并排序动图：

[![format_png 1][]][format_png 1 1]

### Ⅱ、非递归实现  ###

先两个两个一组，依次将每组分成两半进行merge操作，这样每一组就是有序的了；再继续四个四个一组，依次将每组分成两半进行merge操作，这样每一组就是有序的了；再继续八个八个一组...一直这样下去，最后整个序列都是有序的了。唯一要注意的就是，最后一组可能不能和前面组的元素个数一样，最多只能到完整序列的最后一个元素，要小心数组越界。

具体的分布步骤入下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1][]

代码实现如下：

/* 非递归实现的归并排序：将数组a的[start, end]序列排序 */
    void mergeSort2(int a[], int start, int end) {
        int num = end - start + 1;  //总共待排序的元素个数
        //从2开始依次扩大每组的规模，直到组的一半超过num
        for (int step = 2; step / 2 <= num; step *= 2) {
            //以step个元素一组，依次对每组处理
            for (int l = start; l <= end; l += step) {
                int r = min(l + step - 1, end);  //组的最后一个元素下标
                int mid = l + step / 2 - 1;  //组内的分界点，分界点（包含在左侧）的两侧均已经是有序序列
                merge(a, l, mid, mid + 1, r); //将分好的两侧序列合并
            }  //处理完的组 就是有序的了
        }
    }

--------------------

### 完整代码 ###

#include <cstdio>
    #include <algorithm>
    #include <climits>
    
    #define MAX_N 10
    using namespace std;
    
    /* 合并数组a的有序序列[l1,r1]与[l2,r2] 至 [l1, r2] */
    void merge(int a[], int l1, int r1, int l2, int r2) {
        int len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;  //两个序列的长度
        int x[MAX_N], y[MAX_N];   //临时分别储存两个序
        /* 分别将两个序列拷贝入数组x、y */
        int t = l1;
        for (int i = 0; i < len1; i++) {
            x[i] = a[t++];
        }
        t = l2;
        for (int i = 0; i < len2; i++) {
            y[i] = a[t++];
        }
        x[len1] = y[len2] = INT_MAX;  //将x、y数组的最后一个有效元素之后赋值无穷大
        /* 合并操作 */
        int i = 0, j = 0;
        for (int k = l1; k <= r2; k++) {
            //每次将较小的放入a数组
            if (x[i] <= y[j])
                a[k] = x[i++];
            else
                a[k] = y[j++];
        }
    }
    
    /* 递归实现的归并排序：将数组a的[start, end]序列排序 */
    void mergeSort1(int a[], int start, int end) {
        if (start < end) {
            int center = (start + end) / 2;
            mergeSort1(a, start, center);    //分割问题
            mergeSort1(a, center + 1, end);
            merge(a, start, center, center + 1, end);    //合并问题
        }
    }
    
    /* 非递归实现的归并排序：将数组a的[start, end]序列排序 */
    void mergeSort2(int a[], int start, int end) {
        int num = end - start + 1;  //总共待排序的元素个数
        //从2开始依次扩大每组的规模，直到组的一半超过num
        for (int step = 2; step / 2 <= num; step *= 2) {
            //以step个元素一组，依次对每组处理
            for (int l = start; l <= end; l += step) {
                int r = min(l + step - 1, end);  //组的最后一个元素下标
                int mid = l + step / 2 - 1;  //组内的分界点，分界点（包含在左侧）的两侧均已经是有序序列
                merge(a, l, mid, mid + 1, r); //将分好的两侧序列合并
            }  //处理完的组 就是有序的了
        }
    }
    
    int main() {
        int n[MAX_N + 1] = {0};
        printf("请输入10个待排序的数字：");
        for (int i = 0; i < MAX_N; i++)
            scanf("%d", &n[i]);
    
        mergeSort2(n, 0, MAX_N - 1);
        printf("排序后的结果：");
        for (int i = 0; i < MAX_N; i++)
            printf("%d ", n[i]);
        return 0;
    }

## ##

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly90aW1nc2EuYmFpZHUuY29tL3RpbWc_aW1hZ2UmcXVhbGl0eT04MCZzaXplPWI5OTk5XzEwMDAwJnNlYz0xNTgyODA1Mzg3NDQ0JmRpPTNhMzZhZTAxZjIzYjVkNjc2YTBjZDY2NTU0Y2VlZjYyJmltZ3R5cGU9MCZzcmM9aHR0cCUzQSUyRiUyRmltZzIwMTguY25ibG9ncy5jb20lMkZibG9nJTJGMjc3MzMwJTJGMjAxOTA3JTJGMjc3MzMwLTIwMTkwNzA1MTMxMzEyODIyLTIwODA2MTY3MDgucG5n?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200227175254447.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zczIuYmRzdGF0aWMuY29tLzcwY0Z2blNoX1ExWW54R2twb1dLMUhGNmhoeS9pdC91PTc0MzE0NjY5NSwzMDQyOTc4Mzg5JmZtPTI2JmdwPTAuanBn?x-oss-process=image/format,png
[format_png 1 1]: https://image.baidu.com/search/detail?ct=503316480&z=0&tn=baiduimagedetail&ipn=d&word=%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F&step_word=&ie=utf-8&in=&cl=2&lm=-1&st=-1&hd=undefined&latest=undefined&copyright=undefined&cs=743146695,3042978389&os=1202727324,649407319&simid=3116804937,3810582728&pn=2&rn=1&di=2420&ln=641&fr=&fmq=1582795215884_R_D&ic=undefined&s=undefined&se=&sme=&tab=0&width=undefined&height=undefined&face=undefined&is=0,0&istype=2&ist=&jit=&bdtype=0&spn=0&pi=0&gsm=0&objurl=http%3A%2F%2Flouiszhai.github.io%2FdocImages%2Fsort08.gif&rpstart=0&rpnum=0&adpicid=0&force=undefined
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200227184745157.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200111020715220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70