Question

C语言求助~！！！

试写出算法：将数组a和b合并为递增有序数组c[1..m+n]。
有m个整数的递增有序数组a[1..m]
有n个整数的递减有序数组b[1..n].
要求算法的时间复杂度为O(m+n).

Answer 1

#include <stdlib.h>//malloc,free
#include <stdio.h>//printf

void merge(int* a, int m, int*b, int n, int*rt)
{
int* pa = a;
int* pb = b+n-1;
while(pa<a+m && pb>b-1)
{
if(*pa < *pb)
{
*rt = *pa;
pa++;
rt++;
}
else
{
*rt = *pb;
pb--;
rt++;
}
}
while(pa<a+m)
{
*rt = *pa;
pa++;
rt++;
}
while(pb>b-1)
{
*rt = *pb;
pb--;
rt++;
}
}

void dump(int* arr, int n, char* name)
{
int i;
printf("%s:\n",name);
for(i=0; i<n; i++)
{
printf("[%d]=%d,",i,*(arr+i));
}
printf("\n");
}

int main(int argc, char** argv)
{
int a[]={0,2,5,6,7,10,12,15,20};
//int a[]={10,12,15,20};
int m=sizeof(a)/sizeof(int);
//int b[]={10,8,5,4,4,2,1};
int b[]={30,29,21};
int n=sizeof(b)/sizeof(int);
int* c=malloc(sizeof(int)*(m+n));
if(NULL==c) return -1;
dump(a,m,"a");
dump(b,n,"b");
merge(a,m,b,n,c);
dump(c,m+n,"c");
free(c);
return 0;
}

和你的要求有一点不同的是，下标是从0开始的。
程序在GCC 4.1.2下编译运行通过。

Answer 2

#define m 5
#define n 3
main()
{
int i,j,t,z=0;
int a[m]={1,2,3,4,5},b[n]={9,8,7},c[8];
for (i=0;i<m;i++)
c[z++]=a[i];
for (j=0;j<n;j++)
c[z++]=a[j];
for (i=0;i<z-1;i++)
for (j=i+1;j<z;j++)
if (c[i]>c[j])
{
t=c[j];
c[j]=c[i];
c[i]=t;
}
for (i=0;i<z;i++)
printf("%3d",c[i]);
}

Answer 3