1 题目
功能：归并排序
描述：利用归并排序进行将数组序列从小到大排序
2 思路
归并排序两个或多个有序记录序列合并成一个有序序列一次对两个有序记录序的归并称为二路归并排序，也有三路归并排序及多路归并排序下面代码给出的是二路归并排序，基本方法 (1)将n个记录看成是n介长度为1的有序子表 (2)将两两相邻的有序壬莓4行归并 (3)垂复轨行步骤(2)直至归并成一个长度为 L 的有序表
3 代码
#include <stdio.h>
#include <stdlib.h>
/**
功能：归并排序
描述：利用归并排序进行将数组序列从小到大排序
**/
voidmerge(intr[],ints[],intx1,intx2,intx3) {// 实现一次归并排序函数
inti,j,k;
i=x1; // 第一部分的开始位置
j=x2+1; // 第二部分的开始位置
k=x1;
while((i<=x2)&&(j<=x3)) // 当i和j都在两个要合并的部分中
if(r[i]<=r[j]){ // 筛选两部分中较小的元素放到数组s中
s[k]=r[i];
i++;
k++;
}else{
s[k]=r[j];
j++;
k++;
}
while(i<=x2) // 将x1~x2范围内的未比较的数顺次加到数组r中
s[k++]=r[i++];
while(j<=x3) // 将x2+1~x3范围内的未比较的数顺次加到数组r中
s[k++]=r[j++];
}
voidmerge_sort(intr[],ints[],intm,intn) {
intp;
intt[20];
if(m==n)
s[m]=r[m];
else
{
p=(m+n)/2;
merge_sort(r,t,m,p);
// 递归调用merge_sort函数将r[m]~r[p]归并成有序的t[m]~t[p]
merge_sort(r,t,p+1,n); // 递归调用merge_sort函数将r[n+1]~r[n]归并成有序的t[p+1]~t[n]*/
merge(t,s,m,p,n); // 调用函数将前两部分归并到s[m]~s[n]
}
}
intmain(intargc,charconst*argv[]) {
inta[11];
inti;
printf("请输入10个数:\n");
for(i=1;i<=10;i++)
scanf("%d",&a[i]);
merge_sort(a,a,1,10); // 调用merge_sort函数进行归并排序
printf("排序后的顺序是:\n");
for(i=1;i<=10;i++)
printf("%5d",a[i]);
printf("\n");
}
示例结果：
$ gccex063.c-odemo
$ ./demo
请输入10个数:
34
12
64
23
98
45
18
52
1
7
排序后的顺序是:
171218233445526498
