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;
}

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

好了,到这里,如何使用 C 语言实现数组的归并排序算法就介绍完了。它和上一节的插入排序算法都属于排序算法,但是二者的效率差异性却很大,程序员一般如何衡量算法的效率呢?数组的插入排序法和归并排序法的效率差异性到底有多大呢?下一节再说吧。

再次说明下,这几节的内容对初学者可能有些难度,但是我的目的是想让大家知道,程序员的能力,往往体现在算法设计上,而不是纯粹的编码上。这几节暂时不太清楚也没有关系,跟着我一起继续学习,总有一天会觉得这些是小儿科,千万不要被吓退了啊。
阅读更多:   C语言
添加新评论

icon_redface.gificon_idea.gificon_cool.gif2016kuk.gificon_mrgreen.gif2016shuai.gif2016tp.gif2016db.gif2016ch.gificon_razz.gif2016zj.gificon_sad.gificon_cry.gif2016zhh.gificon_question.gif2016jk.gif2016bs.gificon_lol.gif2016qiao.gificon_surprised.gif2016fendou.gif2016ll.gif