【归并排序】两个有序序列的合并
【摘要】 比较各个子序列的第一个记录的键值， 最小的一个就是排序后序列的第一个记录。取出 这个记录，继续比较各子序列现有的第一个记录 的键值，便可找出排序后的第二个记录。如此继 续下去，最终可以得到排序结果。
目录
归并排序的介绍
归并排序是建立在归并操作上的一种有效，稳定的，该算法是采用（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为。
问题描述
给出两个有序数组（数组大小不一定不相等），要求合并成一个有序数组并输出
int main()
{
int arr1[] = { 1,3,5,7,9,11,13,15,17 };
int arr2[] = { 2,4,6,8,10,12,14 };
return 0;
}
算法思想
比较各个子序列的第一个记录的键值， 最小的一个就是排序后序列的第一个记录。
取出 这个记录，继续比较各子序列现有的第一个记录 的键值，便可找出排序后的第二个记录。
如此继 续下去，最终可以得到排序结果。
思路分析
首先求出两个有序序列的大小并分别存入两个整型变量
int main()
{
int arr1[] = { 1,3,5,7,9,11,13,15,17 };
int arr2[] = { 2,4,6,8,10,12,14 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
return 0;
}
创建一个数组用来存放排好序合并后的数组
——我这里因为使用的编译器是VS2022，不支持变长数组，所以直接申请了100大小的数组来存放合并后的序列。如果在其他编译器上可以直接申请一个m+n大小的数组
int main()
{
int arr1[] = { 1,3,5,7,9,11,13,15,17 };
int arr2[] = { 2,4,6,8,10,12,14 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
int arr3[100] = { 0 };
return 0;
}
创建一个while循环，在其内部实现两个序列的合并，循环执行的条件是两个数组元素都未比较完成
实现的逻辑：
当数组arr1中的当前比较元素较小时，将数组arr1中的元素放入数组arr3，数组arr1的下标+1
当数组arr2中的当前比较元素较小时，将数组arr2中的元素放入数组arr3，数组arr2的下标+1
完成一轮比较之后，数组arr3下标+1
while (i < m && j < n)
{
if (arr1[i] < arr2[j])
{
arr3[k] = arr1[i];
i++;
}
else
{
arr3[k] = arr2[j];
j++;
}
k++;
}
当上面这个循环结束时，说明至少其中一个数组的元素已经输出完毕
接下来再进行判断
如果是数组arr1的元素未输出完毕，将数组arr1中元素依次输入到数组arr3中
如果是数组arr2的元素未输出完毕，将数组arr2中元素依次输入到数组arr3中
while (i < m)
{
arr3[k] = arr1[i];
i++;
k++;
}
while (j < n)
{
arr3[k] = arr2[j];
j++;
k++;
}
接下来打印合并后的数组arr3
printf("合并后的数组为\n");
for (int i = 0; i < k; i++)
{
printf("%d ", arr3[i]);
}
完整代码
#include<stdio.h>
int main()
{
int arr1[] = { 1,3,5,7,9,11,13,15,17 };
int arr2[] = { 2,4,6,8,10,12,14,16 };
int m = sizeof(arr1) / sizeof(arr1[0]);//第一个数组的大小
int n = sizeof(arr2) / sizeof(arr2[0]);//第二个数组的大小
int arr3[100] = { 0 };//存放合并后的数组
int i = 0, j = 0, k = 0;//分别作为数组arr1，arr2，arr3的下标使用
while (i < m && j < n)
{
if (arr1[i] < arr2[j])
{
arr3[k] = arr1[i];
i++;
}
else
{
arr3[k] = arr2[j];
j++;
}
k++;
}
while (i < m)
{
arr3[k] = arr1[i];
i++;
k++;
}
while (j < n)
{
arr3[k] = arr2[j];
j++;
k++;
}
printf("合并后的数组为\n");
for (int i = 0; i < k; i++)
{
printf("%d ", arr3[i]);
}
return 0;
}
结果测试
【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）