C语言---排序算法6---递归归并排序法

归并排序（Merge Sort）是经典的分治算法，采用递归+合并的思路实现高效排序。其核心思想是将数组不断二分至最小单元（单个元素），然后逐步合并有序子序列，最终得到全局有序数组。

算法步骤

1、分解：将当前数组分为左右两个子数组。
2、递归：对左右子数组递归执行归并排序。
3、合并：将两个已排序的子数组合并为一个有序数组。

递归实现代码

代码实现1：

#include <stdio.h>#include <stdlib.h>// 合并两个有序数组 void merge(int arr[], int left, int mid, int right){int i, j, k;int n1=mid - left +1;int n2=right - mid;// 创建临时数组 int *L=(int*)malloc(n1 * sizeof(int));int *R=(int*)malloc(n2 * sizeof(int));// 复制数据到临时数组for(i=0;i<n1;i++)L[i]=arr[left + i];for(j=0;j<n2;j++)R[j]=arr[mid +1+ j];// 合并临时数组到原数组 i=0;j=0;k=left;while(i<n1&&j<n2){if(L[i]<=R[j]){arr[k]=L[i];i++;}else{arr[k]=R[j];j++;}k++;}// 复制剩余元素while(i<n1){arr[k]=L[i];i++;k++;}while(j<n2){arr[k]=R[j];j++;k++;}free(L);free(R);}// 归并排序递归函数 void mergeSort(int arr[], int left, int right){if(left<right){int mid=left +(right - left)/2;// 递归排序左右子数组 mergeSort(arr, left, mid);mergeSort(arr, mid +1, right);// 合并已排序的子数组 merge(arr, left, mid, right);}}// 测试用例 intmain(){int arr[]={12,11,13,5,6,7};int n=sizeof(arr)/ sizeof(arr[0]);printf("原始数组: ");for(int i=0;i<n;i++)printf("%d ", arr[i]);mergeSort(arr,0, n -1);printf("\n排序后数组: ");for(int i=0;i<n;i++)printf("%d ", arr[i]);return0;}

代码实现2（摘抄自菜鸟教程）：

#include<stdio.h>#include<stdlib.h>#include<string.h>// 函数声明voidmerge_sort_recursive(intarr[],intreg[],intstart,intend);voidmerge_sort(intarr[],constintlen);intmain(){intarr[]={22,34,3,32,82,55,89,50,37,5,64,35,9,70};intlen=sizeof(arr)/sizeof(arr[0]);// 计算数组长度merge_sort(arr,len);// 调用归并排序函数// 打印排序后的数组for(inti=0;i<len;i++){printf("%d ",arr[i]);}return0;}// 递归实现归并排序voidmerge_sort_recursive(intarr[],intreg[],intstart,intend){if(start>=end)return;intmid=start+(end-start)/2;intstart1=start,end1=mid;intstart2=mid+1,end2=end;merge_sort_recursive(arr,reg,start1,end1);merge_sort_recursive(arr,reg,start2,end2);intk=start;while(start1<=end1&&start2<=end2){reg[k++]=arr[start1]<arr[start2]?arr[start1++]:arr[start2++];}while(start1<=end1){reg[k++]=arr[start1++];}while(start2<=end2){reg[k++]=arr[start2++];}// 使用memcpy进行数组复制，提高效率memcpy(arr+start,reg+start,(end-start+1)*sizeof(int));}// 归并排序入口函数voidmerge_sort(intarr[],constintlen){int*reg=(int*)malloc(len*sizeof(int));if(reg==NULL){// 检查内存分配是否成功fprintf(stderr,"Memory allocation failed\n");exit(EXIT_FAILURE);}merge_sort_recursive(arr,reg,0,len-1);free(reg);// 释放内存}

优缺点分析

优点

1、时间复杂度稳定在O(n log n)
2、适合链表排序（不需要额外空间）
3、多线程环境下容易并行化

缺点

1、需要O(n)额外空间
2、递归调用有栈空间开销
3、小规模数组时常数因子较大

适用场景

1、数据量较大（通常n>1000）
2、需要稳定排序的场景
3、外部排序（磁盘数据排序）
4、链表排序实现

迭代法 vs 递归法

特性	迭代法	递归法
实现方式	通过循环逐步合并子数组	通过递归分解问题
空间开销	仅需临时数组空间	递归栈空间（可能栈溢出）
代码复杂度	稍复杂（需手动管理边界）	更简洁（分治逻辑直观）

学习视频推荐

数据结构合集 - 归并排序(非递归与递归算法过程, 效率分析, 稳定性分析)