归并排序(递归代码)
#include<stdio.h>
#include<stdlib.h>
// 归并排序：非原地排序、稳定排序
// 时间复杂度 O(nlogn)
void merge_sort(int a[],int l,int r)
{
// 对数组 a 的 [l,r] 区间进行归并排序
// 递归终止条件
// 当区间内只有一个元素或没有元素时，无需排序
if(l>=r)return;
// 求中点
int mid=(l+r)/2; // l~~~mid mid+1~~r
// 递归排序左半部分
merge_sort(a,l,mid);
// 递归排序右半部分
merge_sort(a,mid+1,r);
// 将两个有序区间合并
int i=l; // 指向左区间起点
int j=mid+1; // 指向右区间起点
int t[105]; // 临时数组，存放合并结果
int k=0; // t数组下标
// 同时扫描两个区间
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])
{
// 左边元素较小，放入临时数组
t[k++]=a[i];
i++;
}
else
{
// 右边元素较小，放入临时数组
t[k++]=a[j];
j++;
}
}
// 左区间剩余元素直接复制
while(i<=mid)
{
t[k++]=a[i];
i++;
}
// 右区间剩余元素直接复制
while(j<=r)
{
t[k++]=a[j];
j++;
}
// 此时两个有序区间已经全部合并到 t 中
// 将 t 中的数据复制回原数组对应位置
for(i=0;i<k;i++)
{
a[l+i]=t[i];
}
}
int main()
{
int n,a[105];
// 输入元素个数
scanf("%d",&n);
// 输入数组元素
// 本程序采用 1~n 下标存储
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
// 调用归并排序
merge_sort(a,1,n);
// 输出排序结果
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}