合并两个有序序列

  • 前言
  • 1、方法1——先合并再冒泡排序
  • 2、方法2——数组元素一一比较
  • 3、方法3——动态内存空间版
  • 总结

前言

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

输出描述：

  • 输出为一行，输出长度为n+m的升序序列
  • 即长度为n的升序序列和长度为m的升序序列中的元素重新进行升序序列排列合并
输入：5 61 3 5 7 9 0 2 4 6 8 10输出：0 1 2 3 4 5 6 7 8 9 10

1、方法1——先合并再冒泡排序

方法1 显示利用数组开辟空间，再将两个数组合并后，通过冒泡排序算法进行排序：

  • 在C语言基础阶段中 【C语言基础5——数组（1）】4、数组作为函数参数 已经详细学过冒泡排序算法了

  • 在C语言进阶阶段中【C语言进阶11——字符和字符串函数及其模拟实现（2））7、内存操作函数】 已经详细学过库函数了

方法1的思路见下图：

void bubble_sort(int* arr, int sz){//排序坐外面的大循环次数int i = 0;for (i = 0; i < sz - 1; i++){int flag = 1;//状态机标志位，代表数组本身元素就是从小到大排序的int j = 0;for (j = 0; j < sz - 1 - i; j++){if (arr[j] > arr[j + 1]){flag = 0;//只要有一个地方需要排序，就置零int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}if (1 == flag){//第一轮排序结果都是1，说明没有地方需要排序break;//直接跳出后面的循环，不需要再排序了}}}int main(){int m = 0;//数组a的个数int n = 0;//数组b的个数int i = 0;int j = 0;scanf("%d%d", &m, &n);int a[1000];int b[1000];//输入第一个数组for (i = 0; i < m; i++){scanf("%d", &a[i]);}//输入第二个数组for (j = 0; j < n; j++){scanf("%d", &b[j]);}memcpy(a+m, b, n*4);//利用了库函数//可以将合并后的数组打印出来看看//for (int i = 0; i < m+n; i++)//{//printf("%d ", a[i]);//}bubble_sort(a, m+n);//冒泡排序的函数，i = 0;for (i = 0; i < m + n; i++){printf("%d ", a[i]);}return 0;}

结果见下图所示：


在【初阶数据结构与算法 1】时间复杂度与空间复杂度（1）2.3.5 练习5 中，已经详细学习过冒泡算法的时间复杂度为 O(N^2)。

因此将在方法1 的基础上进行优化。

2、方法2——数组元素一一比较

将两个序列的元素一一比较，按顺序直接打印出来。方法2 的思路见下图：

int main(){int m = 0;//数组a的元素个数int n = 0;//数组b的元素个数int i = 0;int j = 0;scanf("%d%d", &m, &n);int a[1000];//定义数组aint b[1000];//定义数组a//输入第一个数组for (i = 0; i < m; i++){scanf("%d", &a[i]);}//输入第二个数组for (j = 0; j < n; j++){scanf("%d", &b[j]);}i = 0;//再次初始化j = 0;while (i < m && j < n){if (a[i]<b[j]){printf("%d ", a[i]);i++;}else{printf("%d ", b[j]);j++;}}if (i==m)//此时数组a的值都已经打印出来了{for(;j< n; j++)//数组b剩下的元素想直接打印出来就行了{printf("%d ", b[j]);}}if (j == n)//此时数组b的值都已经打印出来了{for (; i < m; i++)//数组a剩下的元素想直接打印出来就行了{printf("%d ", a[i]);}}return 0;}

结果见下图所示：


方法2的时间复杂度为 O(m+n).

3、方法3——动态内存空间版

在C语言进阶阶段 【C语言进阶13——动态内存管理】 已经学习了动态内存开辟空间相比数组的优势了，方法3 利用动态内存空间和库函数，开辟所需空间大小，不浪费空间：

方法3的思路见下图：

//动态内存版int main(){int m = 0;//数组a的个数int n = 0;//shuzub的个数int i = 0;int j = 0;scanf("%d%d", &m, &n);int *pa = (int*)malloc((m + 1) * sizeof(int));//开辟有序序列合并的数组空间int *pb = (int*)malloc((n + 1) * sizeof(int));//开辟有序序列合并的数组空间if (pa == NULL){perror("malloc: ");return;}if (pb == NULL){perror("malloc: ");return;}//输入第一个数组for (i = 0; i < m; i++){scanf("%d", pa+i);}//输入第二个数组for (j = 0; j < n; j++){scanf("%d", pb+j);}i = 0;//再次初始化j = 0;while (i<m && j<n){if (*(pa + i) < *(pb + j)){printf("%d ", *(pa + i));i++;}else{printf("%d ", *(pb + j));j++;}}if (i == m)//此时数组a的值都已经打印出来了{for (; j < n; j++)//数组b剩下的元素想直接打印出来就行了{printf("%d ", *(pb + j));}}if (j == n)//此时数组b的值都已经打印出来了{for (; i < m; i++)//数组a剩下的元素想直接打印出来就行了{printf("%d ", *(pa + i));}}free(pa);free(pb);pa = NULL;pb = NULL;return 0;}

结果见下图所示：

总结

C语言还需要多练习，不管自己写的代码是罗嗦了，还是太烂了，也必须要写完，大胆实现自己的想法，实现题目要求，这是最重要的一步。

第二步就是多看看别人写的代码，学习别人的思路，记录下来写成博客，方便自己复习。

熟能生巧！