Question

c语言的归并排序的完整程序

Answer 1

这个不难:

#include<stdio.h>

// 一个递归函数
void mergesort(int *num,int start,int end);
// 这个函数用来将两个排好序的数组进行合并
void merge(int *num,int start,int middle,int end);

int main()
{
// 测试数组
int num[10]= {12,54,23,67,86,45,97,32,14,65};
int i;
// 排序之前
printf("Before sorting:\n");
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
// 进行合并排序
mergesort(num,0,9);
printf("After sorting:\n");
// 排序之后
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
return 0;
}

//这个函数用来将问题细分

void mergesort(int *num,int start,int end)
{
int middle;
if(start<end)
{
middle=(start+end)/2;
// 归并的基本思想
// 排左边
mergesort(num,start,middle);
// 排右边
mergesort(num,middle+1,end);
// 合并
merge(num,start,middle,end);
}
}

//这个函数用于将两个已排好序的子序列合并

void merge(int *num,int start,int middle,int end)
{

int n1=middle-start+1;
int n2=end-middle;
// 动态分配内存，声明两个数组容纳左右两边的数组
int *L=new int[n1+1];
int *R=new int[n2+1];
int i,j=0,k;

//将新建的两个数组赋值
for (i=0; i<n1; i++)
{
*(L+i)=*(num+start+i);
}
// 哨兵元素
*(L+n1)=1000000;
for (i=0; i<n2; i++)
{
*(R+i)=*(num+middle+i+1);
}
*(R+n2)=1000000;
i=0;
// 进行合并
for (k=start; k<=end; k++)
{
if(L[i]<=R[j])
{
num[k]=L[i];
i++;
}
else
{
num[k]=R[j];
j++;
}
}
delete [] L;
delete [] R;
}

Answer 2

#include <stdio.h>
void main()
{
int i,j,k,n=4,a[9]={1,3,5,7,9},b[]={2,4,6,8};
for(i=0;i<4;i++)
for(j=0;j<n+1;j++)
{
if(b[i]<a[j])
{
for(k=++n;k>j;k--)
a[k]=a[k-1];
a[j]=b[i];
break;
}
}
for(i=0;i<9;i++)
printf("%d ",a[i]);
}

Answer 3

#include <stdio.h> 

int main()

{int a[]={1,3,5,7,9},b[]={2,4,6,8},c[10];

int i,j,k,n1,n2,n3;

i=j=k=0;

n1=5;

n2=4;

n3=n1+n2;

for(;i<n1&&j<n2;)

if(a[i]<b[j])c[k++]=a[i++];

else c[k++]=b[j++];

for(;i<n1;)c[k++]=a[i++];

for(;j<n2;)c[k++]=b[j++];

for(k=0;k<n3;k++)

printf("%d ",c[k]);

printf("\n");  

return 0;

} 

Answer 4

设A、B是两个已按降序排列好的数组，试编制程序将A、B数组中的数归并到C数组中，归并后的数组C仍按降序排序。要求在主函数中输入数组A、B，个数不得少于5个，最后输出C数组；编一个函数用于数组的排序，另一个函数用于数组的归并。
归并排序算法的基本思想是：首先考虑每个数组的第一个元素，其中较大者作为结果数组的第一个元素；然后将包含结果数据的那个数组的下一个元素取出，与另一个数组的第一个元素比较，并得到结果数组的第二个元素。如此继续下去，每当获得一个结果元素时，就将包含该结果元素的下一个元素取出，以实现下次比较，最后当两个数组之一的所有元素都取完时，就将另一个数组的剩余元素顺序抄录到结果数组中，从而完成整个归并排序过程。