题解 | #有序序列合并#

#include <stdio.h>
#include <string.h>
int main() {
    int n,m,i,j,k;
    scanf("%d %d",&n,&m);
    int arr1[n],arr2[m],arr[m+n];
    memset(arr1,0,n*sizeof(int));
    memset(arr2,0,m*sizeof(int));
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr1[i]);
    }
    for(i=0;i<m;i++)
    {
        scanf("%d",&arr2[i]);
    }
    i=0;
    j=0;
    k=0;
    while(i<n&&j<m)
    {
        if(arr1[i]<arr2[j])
        {
            arr[k++]=arr1[i++];
        }
        else
        arr[k++]=arr2[j++];
    }
    while(i<n)
    arr[k++]=arr1[i++];
    while(j<m)
    arr[k++]=arr2[j++];
    for(int k=0;k<n+m;k++)
    printf("%d ",arr[k]);
}

典型的二路归并排序。

本题考虑到val值为0~30000，但内存给了32M，所以也可以考虑计数排序。