有序序列合并

#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;
}

#include <stdio.h>
#include <stdlib.h>
void sort_merge(int *a,int *b,int n,int m)
{   
    int i,j,tem;
    for(i=0;i<m;i++)//合并两个数组
    *(a+i+n)=*(b+i);

    for(i=0;i<(m+n-1);i++)//冒泡排序
    {
        for(j=0;j<(m+n-i-1);j++)
        {
            if(*(a+j)>*(a+1+j))
            {
                tem = *(a+j);
                *(a+j) = *(a+1+j);
                *(a+1+j) = tem;
            }
        }
    }
}

int main() {
    int i,n,m;
    scanf("%d",&n);
    scanf("%d",&m);
   int *a = (int *)malloc((n+m)*sizeof(int));
   int *b = (int *)malloc(m*sizeof(int));

   for(i=0;i<n;i++)
        scanf("%d",a+i);
  
  for(i=0;i<m;i++)
    scanf("%d",b+i);

   sort_merge(a, b, n, m);

   for(i=0;i<(n+m);i++)
    printf("%d ",*(a+i));

    return 0;
}

#include <stdio.h>
int main()
{
	//arr1内的数据
	int n = 0;
	//arr2内的数据
	int m = 0;
	scanf("%d %d", &n, &m);
	int arr1[1000] = { 0 };
	int arr2[1000] = { 0 };
	int arr3[2000] = { 0 };
	//输入arr1的值
	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr1[i]);
	}

	//输入arr2的值
	int j = 0;
	for (j = 0; j < m; j++)
	{
		scanf("%d", &arr2[j]);
	}
	//使下标都为0
	i = 0;
	j = 0;
	int k = 0;//arr3下标
	//开始比较
	while (i < n && j < m)
	{
		if (arr1[i] < arr2[j])
		{
			arr3[k] = arr1[i];
			i++;
			k++;
		}
		else
		{
			arr3[k] = arr2[j];
			j++;
			k++;
		}
	}
	//arr1遍历结束,需要将arr2中剩余的元素全部放入arr3中
	if (i == n)
	{
		while (j < m)
		{
			arr3[k] = arr2[j];
			j++;
			k++;
		}
	}
	else//arr2遍历结束,需要将arr1中剩余的元素全部放入arr3中
	{
		while (i < n)
		{
			arr3[k] = arr1[i];
			i++;
			k++;
		}
	}
	//打印arr3的数据
	i = 0;
	for (i = 0; i < n + m; i++)
	{
		printf("%d ", arr3[i]);
	}
	return 0;
}

/*
思路是利用动态分配，建立3个数组
前2个数组    -> 存放用户输入的数据
最后1个数组  -> 存放合并后的数列

为了方便对内存进行操作，我选择了3指针的方式
*/

#include <stdio.h>
#include <malloc.h>

int main()
{
	int n = 0;
	int m = 0;
	int i = 0;//操作指针arrOne
	int j = 0;//操作指针arrTwo
	int k = 0;//操作指针arrCombine
	int flag = 0;
	int* arrOne = NULL;
	int* arrTwo = NULL;
	int* arrCombine = NULL;

	scanf("%d%d", &n, &m);

	//为数列开辟空间
	arrOne = (int*)malloc(sizeof(int) * n);
	if (!arrOne)
	{
		perror("malloc:arrOne");
		return 1;
	}
	arrTwo = (int*)malloc(sizeof(int) * m);
	if (!arrTwo)
	{
		perror("malloc:arrTow");
		return 1;
	}
	arrCombine = (int*)malloc(sizeof(int) * (n + m));
	if (!arrCombine)
	{
		perror("malloc:arrCombine");
		return 1;
	}

	//录入数列n、m
	for (i = 0; i < n; i++)
	{
		scanf("%d", arrOne + i);
	}
	for (j = 0; j < m; j++)
	{
		scanf("%d", arrTwo + j);
	}

	//合并至第3个数列中
	i = 0;
	j = 0;
	for (k = 0; k < n + m; k++)
	{
		//指示 arrOne 已经放完
		if (i == n)
		{
			flag = 1;
			break;
		}
		//指示 arrTow 已经放完
		else if (j == m)
		{
			flag = 2;
			break;
		}

		//把较小的元素放入第3个数列中
		if (*(arrOne + i) < *(arrTwo + j))
		{
			*(arrCombine + k) = *(arrOne + i);
			i++;
		}
		else
		{
			*(arrCombine + k) = *(arrTwo + j);
			j++;
		}
	}

	//处理 arrTwo 中剩余的元素
	if (flag == 1)
	{
		for (; k < n + m; j++, k++)
		{
			*(arrCombine + k) = *(arrTwo + j);
		}
	}
	//处理 arrOne 中剩余的元素
	else if (flag == 2)
	{
		for (; k < n + m; i++, k++)
		{
			*(arrCombine + k) = *(arrOne + i);
		}
	}

	//输出
	for (k = 0; k < n + m; k++)
	{
		printf("%d ", *(arrCombine + k));
	}

	//释放内存
	free(arrOne);
	free(arrTwo);
	free(arrCombine);
	arrOne = NULL;
	arrTwo = NULL;
	arrCombine = NULL;

	return 0;
}