设计一个算法，将给定的两个降（升）序序列归并为一个降（升）序序列， 并分析算法时间复杂度。（设两个序列分别用数组 A[n]和 B[m]表示，合并后的序 列用数组 C[n+m]表示）

Question

设计一个算法，将给定的两个降（升）序序列归并为一个降（升）序序列，
并分析算法时间复杂度。（设两个序列分别用数组 A[n]和 B[m]表示，合并后的序
列用数组 C[n+m]表示）

Answer 1

简单合并，时间复杂度为O(n+m)

#include<stdio.h>
void merge(int a[],int n,int b[],int m,int c[])
{
    int ap=0,bp=0,cp=0;
    for(int j=0; j<n+m; j++)
    {
        if(ap==n) {
            c[cp++]=b[bp++];
            continue;
        }
        if(bp==m) {
            c[cp++]=a[ap++];
            continue;
        }
        if(a[ap]<b[bp]) c[cp++]=a[ap++];
        else c[cp++]=b[bp++];
    }
}
int main()
{
    int n=12,m=9;
    int a[]= {1,2,5,9,11,12,16,20,55,59,60,66};
    int b[]= {2,3,6,8,15,16,17,25,28};
    int c[n+m];
    /*int n=5,m=6;
    int a[]={15,12,11,9,6};
    int b[]={16,14,10,8,7,6};
    int c[n+m];*/
    merge(a,n,b,m,c);
    for(int j=0; j<n+m; j++)
        printf("%d ",c[j]);
    return 0;
}