有序序列合并

#include<stdio.h>
void My_scanf(int arr[], int x) //输入
{
    int i = 0;
    for(i=0;i<x;i++)
    {
        scanf("%d ",&arr[i]);
    }
}
void Sort(int arr3[],int n) //冒泡排序
{
    int i = 0;
    int j = 0;
    int g = 0;
    int temp = 0;
    for(i = 0; i< n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
           if(arr3[i]> arr3[j])
           {
              temp = arr3[i];
              arr3[i] = arr3[j];
              arr3[j] = temp;
           }
        }
    }

}
void combine(int arr1[],int arr2[],int arr3[],int n,int m)//合并两个数组
{
   int i = 0;
   int j = 0;
   for(i=0;i<n;i++)
   {
    arr3[i]=arr1[i];
   }
   for(j=0;j<m;j++)
   {
    arr3[j+n]=arr2[j];
   }
}
void My_printf(int arr3[],int k)//输出
{
    int i = 0;
    for(i=0;i<k;i++)
    {
        printf("%d ",arr3[i]);
    }
}
int main()
{
    int n =0;
    int m = 0;
    scanf("%d %d",&n,&m);
    int arr1[n];
    int arr2[m];
    int arr3[n+m];
    My_scanf(arr1,n);
    My_scanf(arr2,m);
    combine(arr1,arr2,arr3,n,m);
    Sort(arr3,n+m);
    My_printf(arr3,n+m);
    return 0;
}

#include <stdio.h>

int main() {
    int n=0, m=0;
    int i=0,j=0;
    scanf("%d %d",&n,&m);
    int arr[30000]={0};
    for(int i=0;i<n+m;i++){
        scanf("%d",&arr[i]);
    }
    //排序，排成升序
   for(i=0;i<n+m-1;i++){//比较的趟数
    for(j=0;j<n+m-1-i;j++){//每一趟比较的对数
        int tmp=0;
        if(arr[j]>arr[j+1]){//前一个数和后一个数比较
            tmp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=tmp;
        }
    }
   }
   //输出
   for( i = 0;i<n+m;i++){
    printf("%d",arr[i]);
    if(i<n+m-1){//如果不是最后一个元素，打印空格
        printf(" ");
    }
   }
    return 0;
}

#include<stdio.h>
int main()
{
	int n = 0;
	int m = 0;
	scanf("%d %d", &n, &m);
	int arr1[1001] = { 0 };
	int arr2[1001] = { 0 };
	int merged[2002] = { 0 };
	for (int i = 0; i < n; i++)//输入第一行的n个元素
	{
		scanf("%d", &arr1[i]);
	}
	for (int i = 0; i < m; i++)//输入第二行的m个元素
	{
		scanf("%d", &arr2[i]);
	}

    int i = 0;
    int j = 0;
    int k = 0;
    while (i < n && j < m)//由于题目中的两个数组是升序排列，右值一定大于左值，所以该循环最终的结果会以遇到某数组中一个巨大的值为上限，将另一数组遍历排序完
    {
        if (arr1[i] < arr2[j]) //升序排列两数组中的元素，当一组数据被彻底遍历完之后，另一组剩下的只有一些更大的值
        {
            merged[k++] = arr1[i++];
        }
        else 
        {
            merged[k++] = arr2[j++];
        }
    }

    //补漏，将上限值及其升序排列的所有右值添加到merged中  
    while (i < n) //当arr1里面还有值，陆续放到merged中
    {
        merged[k++] = arr1[i++];
    }
    while (j < m) //当arr2里面还有值，陆续放到merged中
    {
        merged[k++] = arr2[j++];
    }

    //如果题目改成无序数组，另加一个冒泡排序即可

    // 输出合并后的序列  
    for (int l = 0; l < k; l++)
    { 
        printf("%d ", merged[l]);
    }
    printf("\n"); 

	return 0;
}

#include <stdio.h>

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int arr1[n], arr2[m], arr3[n + m];

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr1[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &arr2[i]);
    }

    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (arr1[i] < arr2[j]) {
            arr3[k++] = arr1[i++];
        } else {
            arr3[k++] = arr2[j++];
        }
    }

    while (i < n) {
        arr3[k++] = arr1[i++];
    }
    while (j < m) {
        arr3[k++] = arr2[j++];
    }

    for (int i = 0; i < k; i++) {
        printf("%d ", arr3[i]);
    }

    return 0;
}

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

int main() {
    int m, n;
    scanf("%d %d",&n, &m);

    //方法一，对于很大的数就效率比较低
    //时间复杂度为O((N+M)^2) 空间复杂度O(1)
    // int sum = m + n;
    // //申请m+n个大小的数组
    // int* a = (int*)malloc(sizeof(int)* (m + n));
    // for(int i = 0; i < sum; i++)
    // {
    //     scanf("%d", &a[i]);
    // }

    // //冒泡排序
    // for(int i = 0; i < sum - 1; i++)  //冒泡排序的趟数
    // {
    //     for(int j = 0; j < sum - 1 - i; j++)//一趟的交换次数
    //     {
    //         //升序
    //         if(a[j + 1] < a[j])
    //         {
    //             int tmp = a[j];
    //             a[j] = a[j + 1];
    //             a[j+1] = tmp;
    //         }
    //     }
    // }

    // //打印前五个数
    // for(int i = 0; i < m + n; i++)
    // {
    //     printf("%d ", a[i]);
    // }
    

    //方法二
    //以下代码vs能跑通过，这种是牺牲空间换时间的写法
    //时间复杂度为O(M + N),空间复杂度O(M+N)
    //申请三个数组
    int* a = (int*)malloc(sizeof(int) * (m+n));
    int* arr1 = (int*)malloc(sizeof(int) * n);
    int* arr2 = (int*)malloc(sizeof(int) * m);
    //输入数据
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &arr1[i]);
    }
    for(int i = 0; i < m; i++)
    {
        scanf("%d", &arr2[i]);
    }

    int p1, p2, p;
    p = p1 = p2 =0;
    //当有一个走完就得跳出来
    while (p1 < n && p2 <m) 
    {
        if(arr1[p1]  < arr2[p2])
        {
            // a[i] = arr1[p1];
            // p1++;
            a[p++] = arr1[p1++];
        }
        else
        {
            a[p++] = arr2[p2++];
        }
    }

    //还没走完的数组需要插入到数组a
    if(p1 == n) //数组arr1走完，说明数组arr2没走完
    {
        while (p2 < m)
        {
            a[p++] = arr2[p2++];
        } 
    }
    if(p2 == m)
    {
        while (p1 < n)
        {
            a[p++] = arr1[p1++];
        } 
    }

    //打印数组
    for(int i = 0; i < m+n; i++)
    {
        printf("%d ",a[i]);
    }
    //释放申请的空间
    free(a);
    free(arr1);
    free(arr2);
    a = arr1 = arr2 = NULL;
    return 0;
}