程序员面试系列——合并排序（递归实现）

秒速五厘米 2022-06-10 01:59 153阅读 0赞

# 合并排序基本思想 #

合并排序，或者叫归并排序，在算法思想中属于分治法。对于一个需要排序的数组，合并排序把它一分为二，并对每个子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组。

本文要介绍两种实现，都是基于递归（自顶向下）。这两种实现没有本质的差别，第二种只是为了节省内存，提高效率。

# 第一种实现 #

假设`A`数组是要排序的数组。  
1. 把`A`数组的前半部分复制到`B`数组，把`A`数组的后半部分复制到`C`数组  
2. 对`B`数组和`C`数组分别排序（递归）；之后，`B`数组和`C`数组已经有序  
3. 把数组`B`和`C`合并，成为有序数组`A`（见函数`__merge`）

C语言代码如下。

/* * 将两个有序数组b和c合并为一个有序数组a * b是第一个非降序数组的首地址，长度是len_b * c是第二个非降序数组的首地址，长度是len_c * a指向输出数组的首地址 * 注意：a数组需要调用者分配空间,且a数组不能与b或者c重叠 */
    
    void __merge(int *a, int *b, int len_b, int *c, int len_c)
    {
        int i = 0; // b的下标
        int j = 0; // c的下标
        int k = 0; // a的下标
        int len = len_b + len_c; //计算出a数组的长度
    
        while(i < len_b && j < len_c) //&&的优先级更低 
        {
            if(b[i] <= c[j])
                a[k++] = b[i++];
            else
                a[k++] = c[j++];
        }
    
        if(i == len_b) //说明b已经处理完
            memcpy(a+k, c+j, (len-k)*sizeof(int));
        else         //说明c已经处理完
            memcpy(a+k, b+i, (len-k)*sizeof(int));
    }

上面的这个函数完成“合二为一”的工作，即把非降序的`B`和`C`合并为非降序的`A`.

/* * a是数组首地址，数组长度为len * 将数组a按照非降序排列 */
    void merge_sort(int *a, int len)
    {
        if(len==1) //递归出口
            return;
    
        int len_b = len/2;
        int len_c = len - len_b;
    
        int *temp = (int *)malloc(sizeof(int)*len);//为数组b和c分配空间
        if(temp == NULL)
        {
            printf("malloc failed\n");
            return;
        }
    
        memcpy(temp, a, len*sizeof(int));
        int *b = temp;
        int *c = temp+len_b; //以上三行完成了复制和拆分
    
        merge_sort(b,len_b); //递归调用，对数组b排序
        merge_sort(c,len_c); //递归调用，对数组c排序
    
        __merge(a, b, len_b, c, len_c); //合并b和c
    
        free(temp);
    
    }

`merge_sort`这个函数才是归并排序的主函数。

为了更好地理解，我画了一幅示意图。此图体现出递归出口（即递归结束条件）是数组长度等于`1`.

![这里写图片描述][SouthEast]

`merge_sort`函数在设计上的不足之处是内存开销大，也费时间（`malloc`函数用多了会影响性能）。

因为要为数组`B`和数组`C`分配空间，然后分别排序（因为是递归，所以又要分配与释放），排序完毕后再把二者合并到`A`数组，此时数组`B`和数组`C`的空间才可以释放。

可否改进一下呢？可以看看第二种实现。

# 第二种实现 #

假设`A`数组是要排序的数组。  
1. 先分配一段内存（这里叫`temp`），其大小和数组`A`一样大  
2. 把`A`数组一分为二，前半部分称为`B`数组，后半部分称为`C`数组  
3. 对`B`数组和`C`数组分别排序（递归）；排序时，借助`temp`（借助的原因请看4和5）  
4. 把数组`B`和`C`合并为有序数组，合并的结果在`temp`中。（利用函数`__merge`）  
5. 把`temp`的内容拷贝到数组`A`  
6. 释放`temp`

这样做的特点是一次分配，反复利用，最后释放。优点是省内存，效率高。

C语言代码如下。

/* *内部函数 *temp是一段内存的首地址，由调用者分配和释放 */
    void __merge_sort(int *a, int len, int *temp)
    {
        if(len==1) //递归出口
            return;
    
        int len_b = len/2;
        int len_c = len - len_b;
    
        int *b = a;
        int *c = a+len_b; //把数组a原地拆分为b和c
    
        __merge_sort(b,len_b,temp); //对数组b排序，借助内存temp
        __merge_sort(c,len_c,temp); //对数组c排序，借助内存temp
    
        __merge(temp, b, len_b, c, len_c); //合并b和c到temp
    
        memcpy(a,temp,len*sizeof(int)); //复制temp到数组a
    }
    
    /* *这种写法只需要申请一次空间，节省内存，效率更高 */
    void merge_sort(int *a, int len)
    {
        int *temp = (int *)malloc(sizeof(int)*len);
        if(temp == NULL)
        {
            printf("malloc failed\n");
            return;
        }
    
        __merge_sort(a,len,temp); //此函数实现见上文
    
        free(temp); 
    }

# 测试 #

注意，以上代码需要包含的头文件是

#include <string.h> //memcpy函数用这个头文件
    #include <stdlib.h> //malloc和free函数用这个头文件

测试代码如下。

#include <stdio.h>
    
    /* *此函数为了测试用，功能是打印数组 *a是数组首地址 *len是数组长度 */
    void print_array(int *a, int len)
    {
        int i=0;
        for(i=0; i<len; ++i)
            printf("%d ",a[i]);
        printf("\n");
    }
    
    
    //测试函数
    int main(void)
    {
        int a[10]={
       9,8,5,3,2,9,-1,-1,7,1,};   //10个数
    
        merge_sort(a,10);  //按照非降序排列
    
        print_array(a,10);  //打印排序后的数组
        return 0;
    }

运行结果是：

> \-1 -1 1 2 3 5 7 8 9 9

—–欢迎斧正—–

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

【参考资料】  
《算法设计与分析基础（第3版）》（清华大学出版社）

[SouthEast]: /images/20220610/0dfcc4ff5a594d358770f28673dae858.png