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

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

简单合并，时间复杂度为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;
}

归并算法:
public void merge(int[] nums1, int m, int[] nums2, int n) {
int temp[] = new int[m + n];
int index = 0;
int i = 0;
int j = 0;
while (i < m && j < n) {
if (nums1[i] <= nums2[j])
temp[index++] = nums1[i++];
else
temp[index++] = nums2[j++];
}
for (; i < m; ) {
temp[index++] = nums1[i++];
}
for (; j < n; ) {
temp[index++] = nums2[j++];
}
//再把数组temp中的值赋给nums1
for (int k = 0; k < m + n; k++) {
nums1[k] = temp[k];
}
}