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

合并排序基本思想

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

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

第一种实现

假设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.

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版）》（清华大学出版社）