c语言入门17，优秀的程序员应该设计什么样的算法？归并排序算法介绍

让编程具有魅力的是算法，拿到问题，能够设计出解决方案并且完成代码的是程序员，只会按照步骤编码的是码农。这是上一节的主题，有朋友看到也有感而发：@昔阝緣在评论区说，“程序是骨架，算法才是灵魂”。的确，程序只是指令，计算机只会冷冰冰的按照指令办事，它并不能解决问题，真正解决问题的还是人。

上一节的最后，我们介绍了对数组的插入排序法，这种排序法逻辑比较简单，容易设计。假设计算机是无限快的，并且存储器是免费的，那最好的算法就是最容易实现的算法。然而，计算机也许是快的，但它们不是无限快。存储器也许是廉价的，但不是免费的。所以计算时间是一种有限资源，存储器的空间也一样。优秀的程序员应该尽力设计出开销更小的算法。

本节，我们介绍对数组排序的另一种主流算法——归并排序，在数组元素非常多的情况下，它的效率远远高于插入排序法。

这几节的内容对初学者可能有些难度，但是我的目的是想让大家知道，程序员的能力，往往体现在算法设计上，而不是纯粹的编码上。这几节暂时不太清楚也没有关系，跟着我一起继续学习，总有一天会觉得这些是小儿科。

那，什么是归并排序呢？

归并排序的定义，这里就不写了，反正都是一些“一本正经” 的定义，对不了解它的人来说太难懂。我打算用一些容易理解的例子来解释它，读者自行去查找它的严谨定义吧。

假设有一个数组需要排序，那数组长度为多长最简单呢？显然是长度为 1 时，排序最简单，什么都不需要做，就能够排好序。归并排序的基本思路就是这样：把长数组一直拆分下去，直到最后不能拆分为止，这时长数组被拆分为若干个长度为 1 的数组，长度为 1 的数组显然是排好序的了。

下图是一个长度为 5 的数组，为了排序，先把它拆分到不能继续拆为止。

接着，只要把这些排好序的子数组按照从小到大的顺序合并，就可以得到最终排好序的数组了。

好了，现在知道归并排序的算法了，那怎样使用 C 语言编程完成这个算法呢？

C 语言编程实现归并排序算法

归并排序算法总体可以分为两步：拆分数组，合并数组。先来看看怎样使用 C 语言实现数组的拆分。

使用 C 语言拆分数组

对数组拆分有多种方法，我们这里选择平分法。如果使用 start 表示数组头，end 表示数组尾，每次平均拆分，都会将数组分为 start 到 mid，和 mid+1 到 end 两部分，其中 mid 表示中间点，所以 mid = (start+end)/2。就这样一直拆分下去，直到不能继续拆分为止。不能拆分时，start 应该不再小于 end。

好了，拆分数组，上面用数学描述完毕了，容易看出，递归非常适合解决这样的问题。我们现在用 C 语言来实现这样的拆分，先确定递归的基础条件：

void divide(int start, int end)
{
    if(start >= end)
        return;
}

拆分过程会在 start 不再小于 end 时停下。其他情况时，拆分会继续下去：

void divide(int start, int end)
{
    int mid = 0;
    if(start >= end)
        return;
    mid = (start+end)/2;
    divide(start, mid);
    divide(mid+1, end);
}

divide(start, mid); 负责拆分前半段，divide(mid+1, end); 负责拆分后半段。这样的 divide 函数可以把数组拆分到不可拆分为止。

使用 C 语言合并数组

使用 divide 函数把数组拆分完毕后，就可以按照从小到大的顺序把各个元素合并到原来的数组了。

void merge(int start, int mid, int end)
{
    int n1 = mid - start + 1;
    int n2 = end - mid;
    int left[n1], right[n2];
    int i, j, k;

    for (i = 0; i < n1; i++)
        left[i] = arr[start+i];
    for (j = 0; j < n2; ++j)
        right[j] = arr[mid+1+j];

    i = j = 0;
    for (k = start; i < n1 && j < n2; ++k) {
        if (left[i] < right[j]) {
            arr[k] = left[i];
            ++i;
        } else {
            arr[k] = right[j];
            ++j;
        }
    }
    if (i < n1)
        for (; i < n1; i++) {
            arr[k] = left[i];
            ++k;
        }
    if (j < n2)
        for (; j < n2; ++j) {
            arr[k] = right[j];
            ++k;
        }
}

由于两个子序列都已经排好序了，所以 merge 函数实现的功能很简单，每次循环取两个子序列中最小的元素进行比较，将较小的元素取出放到最终的排序序列中，如果其中一个子序列的元素已取完，就把另一个子序列剩下的元素都放到最终的排序序列中。

使用 C 语言实现数组的归并排序

数组的拆分和合并函数都写好了，可以把它俩结合起来，实现数组的排序了。

void divide(int start, int end)
{
    int mid = 0;
    if(start >= end)
        return;
    mid = (start+end)/2;
    divide(start, mid);
    divide(mid+1, end);
    merge(start, mid, end);
}

测试 C 语言实现的归并排序

这里使用 8 个元素的数组做测试：

#include <stdio.h>

int arr[8] = {1, 3, 2, 5, 8, 7, 6, 4};
void divide(int start, int end);
void merge(int start, int mid, int end);
int main()
{
    int i = 0;
    divide(0, 7);
    for(i=0; i<8; i++){
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

编译执行，发现成功排序了。