急寻一个用分治法实现合并排序的源程序,要求为C语言的.TRUBO2.0

Question

急寻一个用分治法实现合并排序的源程序,要求为C语言的.TRUBO2.0

Answer 1

#include<stdio.h>
#include<string.h>
#define N 100 //宏定义数组长度

void merge(int arrayc[],int arrayd[],int l,int m,int r){ //定义合并函数，合并arrayc[1:m]和arrayc[m+1:r]到arrayd[l:r]
int i=l;
int j=m+1;
int k=l;
while((i<=m)&&(j<=r))
if(arrayc[i]<=arrayc[j])
arrayd[k++]=arrayc[i++];
else
arrayd[k++]=arrayc[j++];
if(i>m)
for(int q=j;q<=r;q++)
arrayd[k++]=arrayc[q];
else
for(int q=i;q<=m;q++)
arrayd[k++]=arrayc[q];
}

void mergepass(int arrayx[],int arrayy[],int s){ //合并大小为s的相邻子数组
int i=0;
while(i<=N-2*s){
merge(arrayx,arrayy,i,i+s-1,i+2*s-1);
i=i+2*s; //合并大小为s的相邻2段子数组
}
if((i+s)<N)
merge(arrayx,arrayy,i,i+s-1,N-1);
else
for(int j=i;j<N;j++)
arrayy[j]=arrayx[j]; //else复制到arrayy数组中

}
void mergesort(int array1[]){
int array2[N];
int s=1;
while(s<N){
mergepass(array1,array2,s);//合并到数组array2中
s+=s;
mergepass(array2,array1,s);//合并到数组array1中
s+=s;
}
}

int main(){ //定义main()主函数
int a;
printf("请输入要合并排序的数组大小：(数组最大上限100)\n");
scanf("%d",&a);
int array[N];
printf("Please input shorted array:\n");
for(int i=0;i<a;i++) //a控制数组大小
scanf("%d",&array[i]);
mergesort(array);
printf("合并排序后的数组为:\n");
for( i=N-a;i<N;i++)
printf(" %d",array[i]);
return 0;

}