归并排序和基数排序是两种重要的排序算法，各自基于不同的思想实现高效、稳定的排序。
一、归并排序（Merge Sort）
核心逻辑：分治法
- 分解：将待排序数组从中间分割为两个子数组，递归地对左右两部分进行排序。
- 合并：使用
Merge函数将两个已排序的子数组合并成一个有序数组。
关键函数说明：
voidMSort(intdata[],ints,intt){if(s<t){intm=(s+t)/2;MSort(data,s,m);// 排序左半部分MSort(data,m+1,t);// 排序右半部分Merge(data,s,m,t);// 合并两个有序段}}Merge(data, s, m, t)实现：- 创建临时数组暂存原数组片段
- 使用双指针分别遍历左半
[s, m]和右半[m+1, t] - 按升序将较小元素复制到结果中
- 复制剩余元素
- 将临时数组内容拷贝回原数组
入口函数：
voidMergeSort(intdata[],intn){MSort(data,0,n-1);}- 时间复杂度：O(n log n)，无论最好、最坏、平均情况
- 空间复杂度：O(n) —— 需要额外的临时数组用于合并
- 稳定性：稳定（相等元素相对位置不变）
- 适用场景：要求稳定排序或链表排序时表现优异
二、基数排序（Radix Sort）
基本思想：按位排序 + 分配收集
将整数视为由多个“位”组成的数字串（如十进制下个、十、百位），从最低位开始逐位排序。
排序步骤：
- 设定 r 个队列（例如 r=10 对应数字 0~9）
- 从最低有效位（LSD）开始处理每一位：
- 分配：根据当前位上的数值，把每个数放入对应编号的队列中
- 收集：按队列 0→r-1 的顺序取出所有元素，形成新的序列
- 重复上述过程直到最高位处理完毕
示例：排序 [170, 45, 75, 90, 2, 802, 24]
第一次（个位）后：[170, 90, 2, 802, 24, 45, 75]
第二次（十位）后：[2, 802, 24, 45, 75, 170, 90]
第三次（百位）后：[2, 24, 45, 75, 90, 170, 802]
特性分析：
- 稳定性：稳定 —— 队列先进先出保证相同关键字顺序不乱
- 时间复杂度：O(d(n + r))
- d：最大数的位数（如最大为999，则d=3）
- n：元素个数
- r：基数（如十进制r=10）
- 空间复杂度：O(r + n)
- 需要 r 个队列头尾指针（链式队列）
- 每个元素需存储指针（若用链表结构）
应用场景：
- 整数排序（尤其是固定位宽的键值，如电话号码、身份证号）
- 外部排序中的辅助手段
- 当 d 较小且 r 不大时效率很高，可达到线性时间趋势
总结对比：
| 特性 | 归并排序 | 基数排序 |
|---|---|---|
| 排序依据 | 比较元素大小 | 按位分配 |
| 是否比较排序 | 是 | 否 |
| 时间复杂度 | O(n log n) | O(d(n + r)) |
| 空间复杂度 | O(n) | O(n + r) |
| 稳定性 | 稳定 | 稳定 |
| 适用数据类型 | 可比较任意对象 | 数字、字符串等可分解关键字 |
| 最佳应用场景 | 要求稳定、通用性强 | 数据范围集中、位数少 |
归并排序中的Merge函数是核心操作，用于将两个已排序的子数组合并为一个有序数组。以下是完整的 C 语言代码实现，包含详细注释：
#include<stdio.h>#include<stdlib.h>// 合并函数：将 data[s..m] 和 data[m+1..t] 两个有序子数组合并为有序数组voidMerge(intdata[],ints,intm,intt){intn1=m-s+1;// 左半部分长度intn2=t-m;// 右半部分长度// 动态分配临时数组存储左右两部分int*left=(int*)malloc(n1*sizeof(int));int*right=(int*)malloc(n2*sizeof(int));if(!left||!right){printf("内存分配失败\n");exit(1);}// 复制数据到临时数组for(inti=0;i<n1;i++)left[i]=data[s+i];for(intj=0;j<n2;j++)right[j]=data[m+1+j];// 归并过程：双指针法合并inti=0,j=0,k=s;while(i<n1&&j<n2){if(left[i]<=right[j]){// 使用 <= 保证稳定性data[k++]=left[i++];}else{data[k++]=right[j++];}}// 复制剩余元素while(i<n1)data[k++]=left[i++];while(j<n2)data[k++]=right[j++];// 释放临时内存free(left);free(right);}// 递归分治排序voidMSort(intdata[],ints,intt){if(s<t){intm=s+(t-s)/2;// 防止整数溢出MSort(data,s,m);MSort(data,m+1,t);Merge(data,s,m,t);}}// 入口函数：对长度为 n 的数组进行归并排序voidMergeSort(intdata[],intn){MSort(data,0,n-1);}// 示例测试程序intmain(){intarr[]={38,27,43,3,9,82,10};intn=sizeof(arr)/sizeof(arr[0]);printf("排序前: ");for(inti=0;i<n;i++)printf("%d ",arr[i]);printf("\n");MergeSort(arr,n);printf("排序后: ");for(inti=0;i<n;i++)printf("%d ",arr[i]);printf("\n");return0;}输出结果：
排序前: 38 27 43 3 9 82 10 排序后: 3 9 10 27 38 43 82关键点说明：
- 临时数组：使用
malloc分配空间暂存左右子数组，避免覆盖。 - 稳定性保障：合并时使用
<=判断，确保相等元素保持原有顺序。 - 边界处理：正确计算索引范围
[s..m]和[m+1..t]。 - 资源管理：及时释放动态分配的内存。
