8

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

 3 years ago
source link: https://blog.popkx.com/introduction-to-c-language-17-what-kind-of-algorithm-should-an-excellent-programmer-design-introduction-of-merge-sort-algorithm/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

发表于 2018-11-14 07:11:33   |   已被 访问: 254 次   |   分类于:   C语言   |   暂无评论

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

7a2bf99b7184ff647c37d2f5dfe965b8.png

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

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

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

781b25194d3348a0e4a0af40be4293e3.png

那，什么是归并排序呢？

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

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

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

bf1dacd59daa40d9141221a6ff4283d7.png

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

好了，现在知道归并排序的算法了，那怎样使用 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;
}
8ecc94f0c93712f28a0de735a4a9fa85.png

拆分过程会在 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 函数把数组拆分完毕后，就可以按照从小到大的顺序把各个元素合并到原来的数组了。

48e1b32ecdf6a714812b4a49a5c82d44.png
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 函数实现的功能很简单，每次循环取两个子序列中最小的元素进行比较，将较小的元素取出放到最终的排序序列中，如果其中一个子序列的元素已取完，就把另一个子序列剩下的元素都放到最终的排序序列中。

f8e35dcd4845e552a44a11ba0490cb59.png

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

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

3fb8d0c67d74dd3f32a9cdfb2c41f174.png

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

9dfdb5ffc6dec19f674a199b4acabc5d.png

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK