【归并排序】两个有序序列的合并

2023-12-27 23:24:44

目录

归并排序的介绍

问题描述

算法思想

思路分析

完整代码

结果测试


归并排序的介绍

归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(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;
 }

结果测试

文章来源:https://blog.csdn.net/2302_78391795/article/details/135232741
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。