题解 | #有序序列合并#

#include <stdio.h>
#include <stdlib.h>



int cmp_int(const void* e1,const void* e2)
{
    return (*(int*)e1)-(*(int*)e2);
}
// void Insert(int* p1,int x,int k)
// {
//     int i=0;
//     for(i=n1-k;i>0;i--)
//     {
//         *(p1+k+1)=*(p1+k);
//     }
//     *(p1+1)=x;
// }
int main() 
{
    int n1=0;
    int n2=0;
    scanf("%d %d",&n1,&n2);
    int i=0;
    int arr1[2000]={0};
    int arr2[1000]={0};
    for(i=0;i<n1;i++)
    {
        scanf("%d",&arr1[i]);
    }
    for(i=0;i<n2;i++)
    {
        scanf("%d",&arr2[i]);
    }

    // 方法一：先插入，在排序
    // for(i=n1;i<n1+n2;i++)
    // {
    //     arr1[i]=arr2[i-n1];
    // }
    // qsort(arr1,n1+n2,sizeof(int),cmp_int);
    // for(i=0;i<n1+n2;i++)
    // {
    //     printf("%d ",arr1[i]);
    // }
    // printf("\n");


    //方法二：从后往前大的插入，最简算法
    int end1=n1-1;
    int end2=n2-1;
    int end=n1+n2-1;
    while(end1>=0 && end2>=0)
    {
        if(arr1[end1]<arr2[end2])
        {
            arr1[end]=arr2[end2];
            end2--;
            end--;
        }
        else
        {
            arr1[end]=arr1[end1];
            end1--;
            end--;
        }
    }
    
    //如果是arr2[]中的全部插入之后，end2会小于0，这时arr1[]则不用动了，合并完毕，如果是end1小于0，arr2[]还需插入arr1[]中
    while(end2>=0)
    {
        arr1[end]=arr2[end2];
        end--;
        end2--;
    }
    for(i=0;i<n1+n2;i++)
    {
        printf("%d ",arr1[i]);
    }
    printf("\n");
    return 0;
}