当前位置：首页 > news >正文

C语言学习笔记20260615-有序升序序列合并

news 2026/6/23 23:03:01

C语言学习笔记20260615-有序升序序列合并

要求

输入两个升序排列的整数序列，元素个数分别为m、n；将两个序列合并为一个新的升序序列，并完整输出。

方法一：双指针合并法（推荐，高效）

算法思路

两个原始数组本身已经升序，使用双指针同时遍历两个数组：

分别用指针指向两个数组起始位置；
依次对比两个指针指向的元素，将较小值存入结果数组，并移动对应指针；
其中一个数组遍历完成后，直接把另一个数组剩余元素全部追加到结果末尾；
优势：利用原有有序特性，无需二次排序，执行效率最高。

完整代码

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#defineMAX_LEN100// 定义数组最大容量intmain(){intarr1[MAX_LEN],arr2[MAX_LEN];intres[MAX_LEN*2];// 存储合并后的结果数组intm,n;// m、n 分别为两个序列的元素个数inti=0,j=0,k=0;// i遍历arr1，j遍历arr2，k遍历结果数组// 输入第一个升序序列printf("请输入第一个序列元素个数 m：");scanf("%d",&m);printf("请输入 %d 个升序整数：",m);for(i=0;i<m;i++){scanf("%d",&arr1[i]);}// 输入第二个升序序列printf("请输入第二个序列元素个数 n：");scanf("%d",&n);printf("请输入 %d 个升序整数：",n);for(j=0;j<n;j++){scanf("%d",&arr2[j]);}// 重置指针，开始合并i=0;j=0;// 同时遍历两个数组，取较小元素放入结果数组while(i<m&&j<n){if(arr1[i]<arr2[j]){res[k++]=arr1[i++];}else{res[k++]=arr2[j++];}}// 处理arr1中剩余元素while(i<m){res[k++]=arr1[i++];}// 处理arr2中剩余元素while(j<n){res[k++]=arr2[j++];}// 输出合并后的升序序列printf("合并后的升序序列：");for(intt=0;t<m+n;t++){printf("%d ",res[t]);}printf("\n");return0;}

方法二：数组拼接 + 冒泡排序法（入门易懂）

算法思路

1.先将两个数组完整拼接到同一个新数组中；

2.对拼接完成的整体数组执行冒泡排序，得到升序结果；

3.无需理解双指针逻辑，纯基础循环实现，适合新手学习。

完整代码

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#defineMAX_LEN100intmain(){intarr1[MAX_LEN],arr2[MAX_LEN],res[MAX_LEN*2];intm,n;inti,j;// 输入第一个序列并存入结果数组前半段printf("请输入第一个序列元素个数 m：");scanf("%d",&m);printf("请输入 %d 个升序整数：",m);for(i=0;i<m;i++){scanf("%d",&arr1[i]);res[i]=arr1[i];}// 输入第二个序列，拼接到结果数组后半段printf("请输入第二个序列元素个数 n：");scanf("%d",&n);printf("请输入 %d 个升序整数：",n);for(i=0;i<n;i++){scanf("%d",&arr2[i]);res[m+i]=arr2[i];}inttotal=m+n;// 合并后总元素数量// 冒泡排序：对整体数组升序排序for(i=0;i<total-1;i++){for(j=0;j<total-1-i;j++){// 前大于后则交换位置if(res[j]>res[j+1]){inttemp=res[j];res[j]=res[j+1];res[j+1]=temp;}}}// 输出结果printf("合并后的升序序列：");for(i=0;i<total;i++){printf("%d ",res[i]);}printf("\n");return0;}

方法三：原地拼接排序（节省额外数组空间）

算法思路

1.假设第一个数组空间充足，可容纳两组所有数据；

2.将第二个数组直接拼接到第一个数组尾部；

3.对拼接完成的原数组做冒泡排序，实现升序；

4.不新建独立结果数组，最大化节省内存空间。

完整代码

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#defineMAX_LEN200// 数组长度预留足够空间，存放两组数据intmain(){intarr1[MAX_LEN],arr2[MAX_LEN];intm,n;inti,j;// 输入第一个升序序列printf("请输入第一个序列元素个数 m：");scanf("%d",&m);printf("请输入 %d 个升序整数：",m);for(i=0;i<m;i++){scanf("%d",&arr1[i]);}// 输入第二个序列，并拼接到 arr1 尾部printf("请输入第二个序列元素个数 n：");scanf("%d",&n);printf("请输入 %d 个升序整数：",n);for(i=0;i<n;i++){scanf("%d",&arr2[i]);arr1[m+i]=arr2[i];}inttotal=m+n;// 冒泡排序整体数组for(i=0;i<total-1;i++){for(j=0;j<total-1-i;j++){if(arr1[j]>arr1[j+1]){inttemp=arr1[j];arr1[j]=arr1[j+1];arr1[j+1]=temp;}}}// 输出最终合并结果printf("合并后的升序序列：");for(i=0;i<total;i++){printf("%d ",arr1[i]);}printf("\n");return0;}