#include
#include
#include
#include
#define random(i) (rand()%i)
#define N 12
#define INFINITY 99999999
//要排序的数存放在a数组汇总，p,q,r是数组下标
void Merge(int *a,int p,int q,int r)
{
int n1=q-p+1;
int n2=r-q;
int *L=(int *)malloc(sizeof(int)*n1);
int *R=(int *)malloc(sizeof(int)*n2);
int i,j,k;
int m=0;
if(L==NULL)
{
printf("申请空间失败\\n");
}
if(R==NULL)
{
printf("申请空间失败\\n");
}
for(i=0;i
{
L[i++]=a[p+i];
i--;
}
for(j=0;j
{
R[j++]=a[q+j+1];
j--;
}
L[n1]=INFINITY; //设置哨兵
R[n2]=INFINITY;
i=0;
j=0;
for(k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
a[k]=L[i];
i++;
}
else
{
a[k]=R[j];
j++;
}
}
}
void merge_sort(int *A,int p,int r)
{
int q;
if(p
{
q=(p+r)/2;
merge_sort(A,p,q);
merge_sort(A,q+1,r);
Merge(A,p,q,r);
}
}
void main()
{
int rand_no=0;
int i=0;
int j=0;
int a[N]; //n表示数组长度
srand((int)time(0)); //设置随机数种子
printf("==================排序前==========================");
printf("\\n");
for(rand_no=0;rand_no
{
a[rand_no]=random(100);
printf("%5d",a[rand_no]);
}
printf("\\n");
merge_sort(a,0,N);
printf("==================排序后==========================");
printf("\\n");
for(i=1;i<=N;i++)
printf("%5d",a[i]);
printf("\\n");
}
