#include<stdio.h>
#include<time.h>
//数组大小
#define N 100
//随机数的最大值
#define max 100
void merge(int a[],int p,int x,int q,int b[]){
int i = p, r = x + 1, k=p;
//保证还有数组的元素没有放入临时数组B[];
while(i<=x || r <= q){
//如果r>q成立就说明i<=x一定成立
//就说明前面那一段数组还有元素没有比较到那时后面那一段数组已经没有元素了
//如果是r>q不成立就说明r<=q成立如果 if里面的i<=x也成立
//就说明两段数组都还有元素所以就需要在IF里面比较元素的大小
if((r > q)||(i <= x &&a[i] <= a[r])){
b[k++] = a[i++];
}else{
b[k++] = a[r++];
}
}
int j;
//将B数组重新放入A数组
for(j = p;j <=q;j++)
a[j] = b[j];
}
void mergeSort(int a[],int p,int q,int b[]){
if(p<q){
//将数组平均分为两段
int x=(q + p)/2;
//递归
mergeSort(a,p,x,b);
mergeSort(a,x+1,q,b);
merge(a,p,x,q,b);
}
}
int main(){
srand((unsigned int)time(NULL));
int i;
int a[N],b[N];
printf("随机产生的N个随机数为:\n");
for(i = 0; i< N; i++){
a[i] = rand()%max+1;
printf("%d ",a[i]);
}
mergeSort(a,0,N,b);
printf("\n排好序的N个数为:\n");
for(i = 0; i< N; i++){
printf("%d ",a[i]);
}
return 0;
}