牛客网刷题 | BC121 有序序列合并

目前主要分为三个专栏，后续还会添加：

专栏如下： C语言刷题解析 C语言系列文章我的成长经历

感谢阅读！

初来乍到，如有错误请指出，感谢！

描述

输入两个升序排列的序列，将两个序列合并为一个有序序列并输出。

数据范围： 1≤n,m≤1000 1≤n,m≤1000 ，序列中的值满足 0≤val≤30000 0≤val≤30000

输入描述：

输入包含三行，

第一行包含两个正整数n, m，用空格分隔。n表示第二行第一个升序序列中数字的个数，m表示第三行第二个升序序列中数字的个数。

第二行包含n个整数，用空格分隔。

第三行包含m个整数，用空格分隔。

输出描述：

输出为一行，输出长度为n+m的升序序列，即长度为n的升序序列和长度为m的升序序列中的元素重新进行升序序列排列合并。

示例1

输入：5 61 3 7 9 22
2 8 10 17 33 44输出：1 2 3 7 8 9 10 17 22 33 44

思路：

1. 输入处理

读取数组长度：首先需要从用户输入中读取两个整数 n 和 m，分别表示两个数组的长度。
读取数组元素：
- 使用一个循环读取第一个数组的 n 个元素，并存储在数组 arr 的前 n 个位置。
- 使用另一个循环读取第二个数组的 m 个元素，并存储在数组 arr 的接下来的 m 个位置。

2. 合并数组

在上面的步骤中，我们实际上已经完成了两个数组的合并。通过连续读取元素到同一个数组 arr 中，我们将两个数组合并成了一个数组。

3. 排序算法

选择排序算法：这里选择了冒泡排序算法来对合并后的数组进行排序。冒泡排序是一种简单的排序算法，其基本思想是重复地遍历要排序的列表，一次比较两个元素，如果它们的顺序错误就交换它们的位置。
实现冒泡排序：
- 外层循环控制遍历的次数，总共需要遍历 n + m - 1 次。
- 内层循环负责比较相邻的元素，并在必要时交换它们的位置。
- 通过多次遍历和交换，最终整个数组会被按升序排列。

4. 输出结果

最后，使用一个循环逐个输出排序后的数组元素。

详细细节

初始化变量
- 声明变量 n 和 m 来存储两个数组的长度。
- 声明一个大小为2000的数组 arr 来存储合并后的数组元素。
- 声明临时变量 tmp 用于交换数组中的元素。
读取输入
- 使用 scanf 函数读取两个整数 n 和 m。
- 使用一个 for 循环读取第一个数组的 n 个元素，并存储在 arr 数组的前 n 个位置。
- 使用另一个 for 循环读取第二个数组的 m 个元素，并存储在 arr 数组的接下来的 m 个位置。
排序数组
- 使用嵌套的 for 循环实现冒泡排序算法：
  - 外层循环控制遍历的次数，总共需要遍历 n + m - 1 次。
  - 内层循环比较相邻的元素，如果前一个元素大于后一个元素，则交换它们的位置。
输出结果
- 使用一个 for 循环逐个输出排序后的数组元素，用空格分隔。

代码详细步骤

包含头文件
```
#include <stdio.h>
```
这行代码包含了标准输入输出库 stdio.h，使得我们可以使用 scanf 和 printf 函数来处理输入和输出。
主函数声明
```
int main() 
{// 主函数体
}
```
main 函数是程序的入口点。每个C程序都必须有一个 main 函数，它是程序开始执行的地方。
变量声明
```
int n, m;
scanf("%d %d", &n, &m); // 读取两个整数n和m
int i, j, arr[2000];
int tmp;
```
- int n, m; 声明了两个整数变量 n 和 m，用于存储两个数组的长度。
- scanf("%d %d", &n, &m); 使用 scanf 函数从标准输入读取两个整数，并将它们存储在 n 和 m 中。
- int i, j, arr[2000]; 声明了两个循环计数器 i 和 j，以及一个大小为2000的整数数组 arr，用于存储合并后的数组元素。
- int tmp; 声明了一个临时变量 tmp，用于交换数组中的元素。
读取第一个数组的元素
```
for (i = 0; i < n; i++) {scanf("%d", &arr[i]);
}
```
这个 for 循环用于读取第一个数组的 n 个元素，并将它们依次存储在 arr 数组的前 n 个位置中。
读取第二个数组的元素
```
for (i = n; i < n + m; i++) {scanf("%d", &arr[i]);
}
```
这个 for 循环用于读取第二个数组的 m 个元素，并将它们依次存储在 arr 数组的接下来的 m 个位置中。
冒泡排序算法
```
for (i = 0; i < n + m - 1; i++) 
{for (j = 0; j < n + m - i - 1; j++){if (arr[j] > arr[j + 1]){tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}
}
```
这段嵌套的 for 循环实现了冒泡排序算法，用于对合并后的数组进行排序：
- 外层循环控制遍历的次数，总共需要遍历 n + m - 1 次。
- 内层循环比较相邻的元素，如果前一个元素大于后一个元素，则交换它们的位置。
- 通过多次遍历和交换，最终整个数组会被按升序排列。
输出排序后的数组
```
for (i = 0; i < n + m; i++) {printf("%d ", arr[i]);}
```
这个 for 循环用于输出排序后的数组元素。printf 函数逐个打印出数组中的每个元素，用空格分隔。
返回值
```
return 0;
```
return 0; 表示程序成功结束并返回操作系统一个状态码 0，通常表示程序正常退出。

附上代码：

#include <stdio.h>int main() 
{int n, m;scanf("%d %d", &n, &m); // 读取两个整数n和mint i, j, arr[2000];int tmp;// 读取第一个数组的元素for (i = 0; i < n; i++) {scanf("%d", &arr[i]);}// 读取第二个数组的元素for (i = n; i < n + m; i++) {scanf("%d", &arr[i]);}// 使用冒泡排序算法对整个数组进行排序for (i = 0; i < n + m - 1; i++) {for (j = 0; j < n + m - i - 1; j++) {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]);}return 0;
}

#include <stdio.h>int main() 
{int n, m;// 读取两个整数n和m，分别表示两个数组的长度scanf("%d %d", &n, &m); int i, j, arr[2000];int tmp;// 读取第一个数组的元素，并存储在arr数组的前n个位置for (i = 0; i < n; i++) {scanf("%d", &arr[i]);}// 读取第二个数组的元素，并存储在arr数组的接下来的m个位置for (i = n; i < n + m; i++) {scanf("%d", &arr[i]);}// 使用冒泡排序算法对整个数组进行排序for (i = 0; i < n + m - 1; i++) { // 外层循环控制遍历次数for (j = 0; j < n + m - i - 1; j++) { // 内层循环比较相邻元素if (arr[j] > arr[j + 1]) { // 如果前一个元素大于后一个元素tmp = arr[j]; // 将前一个元素存入临时变量tmparr[j] = arr[j + 1]; // 将后一个元素移动到前一个位置arr[j + 1] = tmp; // 将临时变量tmp中的值赋给后一个位置}}}// 输出排序后的数组for (i = 0; i < n + m; i++) {printf("%d ", arr[i]); // 打印每个元素，用空格分隔}return 0; // 返回0，表示程序成功结束
}