C语言必学的12个排序算法：归并排序（第8篇）

灰太狼 2023-03-04 10:30 6阅读 0赞

\#\#\#\#题外话很多童鞋感受算法比较难度，的确，算法其实和C语言本身关系不大，算法是计算机科学家利用丰富的数学和算法设计知识研究出来，如今我们只需拿来主义，学习使用即可，当然这需要一定的努力过程。

\[C语言必学的12个排序算法：基础知识 (第0篇）\]

# 基本思想 #

核心是归并思想，将两个或两个以上的有序数据记录序列合并成一个完整的有序数据记录序列，其时间复杂度O(n+m)，其中m,n表示两个有序序列的长度。

例如：对于A(1,3,5)和B(2,4,6)两个有序序列A和B归并成有序序列C。

第1步：1和2比较，1被归并到有序序列C(1)，A序列下标移动到下一个位置；

第2步：3和2比较，2被归并到有序序列C(1,2)，B序列下标移动下一个位置；

第3步：3和4比较，3被归并到有序序列C(1,2,3)，A序列下标移动下一个位置；

第4步：5和4比较，4被归并到有序序列C(1,2,3,4)，B序列下标移动下一个位置；

第5步：5和6比较，5被归并到有序序列C(1,2,3,4,5)，A序列下标移动下一个位置；

第6步：A序列为空，B序列剩余6，6被归并到有序序列C(1,2,3,4,5,6)。

经过6次操作，最终排序完成，得到完整的有序序列。

# 2-路归并排序 #

归并排序前提是子序列需要有序，但是初始序列是随机的，乱序的，如何有序？

2-路归并排序将具有n个数据记录的初始序列看成n个子序列，因此n个子序列每个里面只有1个数据记录，因此必然也是有序子序列。这n个有序子序列，两两归并，得到n/2个有序子序列；再两两归并，得到n/4个有序子序列…直到最终形成1个有序子序列为止。两两归并，因此是2-路归并排序。

2-路归并排序时间复杂度O(nlogn)，与快速排序、堆排序相比，它是一种稳定的内部排序算法。同时实现归并排序需要O(n)数据记录辅助空间。

# 代码实现 #

采用递归实现，比较简单和容易理解，实现过程需要申请辅助空间，主要有两个函数，一个是对两个有序子序列归并，一个是对无序的序列拆分成两个序列递归调用归并排序。

*/
    #include <stdio.h>
    #include <stdlib.h>
    // 将a[s...m]和a[m+1...e]两个有序子序列归并为有序
    // 归并后的序列存放数组b中 
    void merge(int a[], int s, int m, int e)
    {
      int i,j,k;
      // 申请临时空间存放有序序列 
      int *b = (int *)malloc(sizeof(int)*(e-s+1));
      
      for(i=m+1,k=0,j=s; j<=m && i<=e; ++k)
      {
        if(a[j] <= a[i])
          b[k] = a[j++];
        else
          b[k] = a[i++];
      }
      while(j<=m) 
      {
        b[k] = a[j];
        k++;
        j++;
      }
      while(i<=e)
      {
        b[k] = a[i];
        k++;
        i++;
      }
      // 排序完成后，复制到原数组a
      for(i=s,k=0; i<=e; i++,k++) 
        a[i] = b[k];
      free(b);
    }
    // 对a[s...e]序列进行归并排序 
    void msort(int a[], int s, int e)
    {
      if (s<e)
      {
        // 将整个序列一分为二 
        int m = (s+e)/2;
        msort(a,s,m);
        msort(a,m+1,e);
        merge(a,s,m,e);
      }
    }
    void merge_sort(int a[], int length)
    {
      msort(a,0,length-1);
    }
    int main(void)
    {
        int a[10] = {4,3,1,2,6,5,0,9,8,7};
        merge_sort(a,10);
        int i;
        for(i=0; i<10; i++)
          printf("%d ", a[i]);
        return 0;
    }

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。  
![format_png][]  
![format_png 1][]

[format_png]: /images/20230208/fa805e20c7594e74983950e878886587.png
[format_png 1]: /images/20230208/08ee727f44dc4fa8b66581f6ca2c57b1.png