文章目录
- 算法步骤
- 递归实现代码
- 优缺点分析
- 优点
- 缺点
- 适用场景
- 迭代法 vs 递归法
- 学习视频推荐
归并排序（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 递归法
| 特性 | 迭代法 | 递归法 |
|---|---|---|
| 实现方式 | 通过循环逐步合并子数组 | 通过递归分解问题 |
| 空间开销 | 仅需临时数组空间 | 递归栈空间（可能栈溢出） |
| 代码复杂度 | 稍复杂（需手动管理边界） | 更简洁（分治逻辑直观） |
学习视频推荐
数据结构合集 - 归并排序(非递归与递归算法过程, 效率分析, 稳定性分析)
