归并排序和基数排序是两种重要的排序算法，各自基于不同的思想实现高效、稳定的排序

归并排序和基数排序是两种重要的排序算法，各自基于不同的思想实现高效、稳定的排序。

---

一、归并排序（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）

基本思想：按位排序 + 分配收集

将整数视为由多个“位”组成的数字串（如十进制下个、十、百位），从最低位开始逐位排序。

排序步骤：

1. 设定 r 个队列（例如 r=10 对应数字 0~9）
2. 从最低有效位（LSD）开始处理每一位：
   • 分配：根据当前位上的数值，把每个数放入对应编号的队列中
   • 收集：按队列 0→r-1 的顺序取出所有元素，形成新的序列
3. 重复上述过程直到最高位处理完毕

示例：排序 [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]。
• 资源管理：及时释放动态分配的内存。

---