两个有序数组的合并

         

       这道题目是让两个有序数组合并，题中有三点需要注意，第一点是题目描述中的输入的两个数组的排列顺序，数组a是升序输入，数组b是降序输入，而要求是将数组a,b中元素存到数组c中并按降序输出；第二点是输入一行最后说的m，n的值小于等于1000000，数组有点大，类似于之前做过的一道简单求和问题，这个大数组是不能在主函数main中直接定义的，那样编译器无法运行，必须定义到主函数外面的全局数组，全局数组的定义范围可以有这么大。第三点是提示说的排序，也就是说，有的测试数据数会很多，要用冒泡排序，会时间超限。

下面过程如果还不是很清楚的话，最下面还有个样例。

看程序：

#include<stdio.h>

int a[1000000],b[1000000];    定义了2个全局数组。

int main()

{

    int i,j,m,n;

    scanf("%d",&n);

    for(i=n-1;i>=0;i--)  因为题中说数组a是升序输入的，和要输出的降序，顺序相反，这里有个小技巧，让i先等于最大的下标，也就是让输入的第一个数存到最后面，以此靠前，这样就能让按升序输入的数，在数组中以降序的方式排列。

        scanf("%d",&a[i]);

    scanf("%d",&m);

    for(j=0;j<m;j++)

        scanf("%d",&b[j]);

    i=0;

    j=0;

    int c[n+m],k=0;    再定义一个m+n个数大小的数组；

   while(i<n&&j<m)   这里的条件可以理解为当数组a或者b哪个里面 的数先往数组c中存放完。

    {

        if(a[i]>=b[j])

            c[k++]=a[i++];   将数组a中数存放到数组c中，并将各自下标加1.

        else

            c[k++]=b[j++];    同上吧。

    }

   while(i<n)       这个判断可以理解为数组a中的数没有存放完。这个while跟下面的while必定只有一个需要执行。

    {

        c[k++]=a[i++];      再依次把数组a中的数存放到数组c中。

    }

    while(j<m)             这里理解为数组b中的数没有存放完。

    {

        c[k++]=b[j++];      再依次把数组b中的数存放到数组c中。

    }

    for(i=0;i<m+n-1;i++)  

        printf("%d ",c[i]);   除去最后一个数，把前面的数输出后面带个空格。

    printf("%d",c[m+n-1]);   输出最后一个数，后面没有空格。

   return 0;

}

样例：

输入n：4

输入n个数：1 3 5 7

然后按程序中那样写的话，这4个数在数组a中是以7 5 3 1存放的

输入m：3

输入m个数：6 4 2

这样数组a和数组b中的数的存放顺序就一样了，并且跟最后要求输出的降序(从大到小)一样

让i=0来做数组a的下标，让j=0来做数组b的下标，让k=0来做数组c的下标。

//数组a：7 5 3 1

//数组b：6 4 2

然后开始第一个while循环：第一次：7>6;c[0]=7;  i+1=1; k+1=1;

                         第二次：6>5;c[1]=6;  j+1=1; k+1=2;

                         第三次：5>4;c[2]=5;  i+1=2; k+1=3;

                         第四次：4>3;c[3]=4;  j+1=2; k+1=4;

                         第五次：3>2;c[4]=3;  i+1=3; k+1=5;

                         第六次：2>1;c[5]=2;  j+1=3; k+1=6;

当第六次时候，数组b中的数排完了，此时j=m=3；跳出while循环。

然后进行下面的while循环判断。i=3<n=4;则进行while(i<n)中的语句。

这时候，a中剩下的数，肯定都比之前存到数组c的数都要小了。这里还剩一个1，那么让c[6]=1;i+1=4=n,结束。

而j=m=3;则不进行while(j<m)中的循环。

最后输出。

7 6 5 4 3 2 1