C语言归并排序

归并排序

1. 归并排序——最常见的分治排序算法；
2. 把两个已经有序的数组合并成一个有序数组

一、归并排序思路

1. 分：递归地把当前区间 [left, right] 一分为二，直到区间长度 ≤1。
2. 治：把两个已经有序的子区间合并成一个有序区间。
3. 合并时需要额外 O(n) 的辅助空间；时间复杂度稳定 O(n log n)，是稳定排序。

二、核心过程：

功能：把两个有序子数组 a[low…mid] 和 a[mid+1…high] 原地归并到临时数组 tmp，最后再拷回去。

关键点

• 用双指针 i、j 分别扫描左右两段；
• 每次把较小的元素放到 tmp[k]，指针后移；
• 某一段耗尽后，把另一段剩余元素全部追加；
• 最后把 tmp[low…high] 复制回原数组对应位置。

三、完整代码

#include<stdio.h>#include<stdlib.h>#include<string.h>/* 合并两个有序区间 a[low..mid] 与 a[mid+1..high] */staticvoidmerge(int*a,intlow,intmid,inthigh){inti=low,j=mid+1,k=0;int*tmp=malloc((high-low+1)*sizeof(int));if(!tmp){perror("malloc");exit(EXIT_FAILURE);}/* 二路归并 */while(i<=mid&&j<=high)tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];while(i<=mid)tmp[k++]=a[i++];while(j<=high)tmp[k++]=a[j++];/* 拷回原数组 */memcpy(a+low,tmp,(high-low+1)*sizeof(int));free(tmp);}/* 归并排序递归主体 */staticvoidmerge_sort(int*a,intlow,inthigh){if(low<high){intmid=low+(high-low)/2;/* 防溢出 */merge_sort(a,low,mid);merge_sort(a,mid+1,high);merge(a,low,mid,high);}}/* 对外接口：排序长度为 n 的整型数组 */voidmerge_sort_int(int*a,size_tn){if(n>1)merge_sort(a,0,(int)n-1);}/* ---- 测试 ---- */intmain(void){intarr[]={8,3,6,7,1,5,2,4};size_tn=sizeof(arr)/sizeof(arr[0]);merge_sort_int(arr,n);for(size_ti=0;i<n;++i)printf("%d%c",arr[i],i+1==n?'\n':' ');return0;}

四、常见变形与考点

1. 链表归并排序
   链表无法随机拆分，用快慢指针找中点，然后递归归并，空间可做到 O(log n)（递归栈）。

2. 外排序
   文件太大内存放不下，先分段生成有序临时文件，再做多路归并。

3. 逆序对
   在 merge 过程中，若左边元素 > 右边元素，则左边剩余元素都与该右边元素构成逆序对，可顺手统计。

4. 原地归并
   经典算法有 “旋转法” 或 “缓冲法”，但实现复杂且常数大，实际工程里仍用辅助数组。

五、复杂度小结

• 时间：每次合并 O(n)，共 log₂n 层 ⇒ O(n log n)
• 空间：辅助数组 O(n) + 递归栈 O(log n)
• 稳定性：稳定（相等元素相对顺序不变）