【数据结构与算法】:归并排序和计数排序

1. 归并排序

归并排序是一种效率仅次于快速排序的排序算法。它有非递归递归两种实现方式(本文只讲述递归实现,非递归实现以后有专门的文章)。

其实,归并排序也叫外排序。它不仅可以对内存中的数据进行排序,还能对文件里的数据排序。

比如:假设有10G的数据放在硬盘的文件中,要排序,如何排呢?
我们知道,内存里的空间远远没有10G,假设有1G内存可用。首先我们可以把10G的文件切分成10个1G的文件,再依次读文件,每次把1G的数据读入内存的数组中,接着利用快排对其进行排序,再把排好序的那1G的数据写到硬盘的一个文件,再继续读下一个1G的数据……当10个文件里的数据都分别有序时,再利用归并排序进行两两归并,最终使10G的数据有序。

1.算法思想:

归并排序采用分治法。首先假设一组数据的左半区间有序,右半区间有序,将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

若将两个有序表合并成一个有序表,称为二路归并

所谓 归并,就是将两组有序的数据合成为一组有序的数据。 例如有如下两个有序数组,将两个有序数组归并为一个有序数组,这就是一次归并操作。

在这里插入图片描述

2.归并操作的工作原理如下:

第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列。

第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置。

第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置。

重复步骤3直到某一指针超出序列尾,将另一序列剩下的所有元素直接复制到合并序列尾。

归并排序类似于二叉树的后序遍历即先将左右的区间都排为有序后,然后才开始进行归并操作,因为归并必须要满足两个数组是有序的。

例如有如下数组。需要先将该数组每次都分割为两个区间,直到最后每个区间都只有一个值,此时比较两个值大小,然后将该两个值归并到一个数组中,此时就得到一个有两个元素的有序数组,然后再与另一个有两个元素的有序数组进行归并,然后就得到了一个有四个元素的有序数组,然后再与另一个有四个元素的有序数组进行归并,就得到了一个有八个元素的有序数组。就这样依次递归归并,直到最后目标数组为有序数组。

在这里插入图片描述

3.归并排序的代码实现如下:


//把数组分成区间
void _MergrSort(int* arr,int left,int right,int* tmp)
{
    //当左右两个区间只有一个元素或是不存在区间时,递归结束
	if (left >= right)
		return ;
		
     //右移1位右除以2的效果,用来把数组分成两个区间
	int mid = (left + right) >> 1;

	//假设[left mid] [mid+1 right]有序,就可以归并
	_MergrSort(arr, left, mid, tmp);
	_MergrSort(arr, mid + 1, right, tmp);

     //每次归并的过程
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int index = left;
	
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];

		}
	}

	//当其中有一个区间结束时,另一个有序区间的数据直接拷贝进临时数组里
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}

	//最后把临时数组里面的数据拷贝回原数组
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}

void MergrSort(int* arr, int sz)
{
    //创建临时数组存放数据
	int* tmp = (int*)malloc(sizeof(int) * sz);
	if (tmp == NULL)
	{
		perror("malloc");
		return;
	}
	
	_MergrSort(arr, 0, sz - 1, tmp);

	free(tmp);
	tmp = NULL;
}

排序结果如下:
在这里插入图片描述

4.归并排序的时间复杂度和稳定性分析:

1.归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(N)
4. 稳定性:稳定

2. 计数排序

计数排序是一种非比较排序,即不需要直接比较数据之间的大小来进行排序。

1.算法思想:

计数排序,是通过统计每一个数字出现的次数,并把它映射到与它自己本身数值相同的下标处,再遍历映射的数组使原数组有序的一种排序方法

计数排序的本质是一种哈希算法,也就是通过建立映射关系来达到排序的目的。

2.映射过程的图解如下:

基本思路:

先开辟一个映射数组,然后遍历原数组,数组中的元素是几就在开辟的的映射数组下标为几的位置+1,得到的这个映射数组就包含了原数组中所有元素的映射关系,最后遍历一遍映射数组找出原数组中出现过的数即可

在这里插入图片描述
如图所示,原数组中有一个8,那么在映射数组的下标为8的位置记为1;原数组中有两个5,在映射数组的下标为5的位置记为2……以此类推。

但是这样映射也面临着一个问题,那就是我们开辟的数组到底要开多大的空间呢? 显然,我们在上述例子中开辟了10个整形空间的数组,但是可以看到,有5个位置都是空的,也就是说有五个位置的数都是没出现过的,这样子开辟空间显然是有些浪费了,我们上面的写法是一种绝对映射的写法,绝对映射就是这个数本身是多少就映射到下标为多少的位置,但是如果我给出以下这个数组让你排序呢?

在这里插入图片描述

显然,以上数字的最大值是109,也就是说如果用绝对映射的方法那我们至少需要开110个空间,因为109要映射到下标为109的位置,下标从0开始,0-109就是110个数。但是仔细观察你会发现,这些数都是在100-109之间的,换句话说如果你开辟110个空间,那么前100个位置都是0,没有数映射,所以就等于是白白浪费了100个整形的空间,这显然是不能接受的。

所以有人就想出来了一种相对映射的方法,把100映射到0的位置,把109映射到9的位置,其它的也以此类推,每个数在映射的时候都减去100,等到取出数据的时候在加上100就能得到原来的数了。这样一来,我们需要开10个整形的空间就可以了,大大减少了内存的消耗。

那么真正开辟的空间该如何计算呢?

开辟的空间的大小=最大元素-最小元素+1
例如上面的例子就是:开辟空间的大小=109-100+1=10
为什么要+1?因为数组下标是从0开始的,如果不+1,那就是开辟9个空间,那么109就没法映射到109-100=9的位置了。

3.计数排序的代码实现如下:

void CountSort(int* arr, int sz)
{
	int max = arr[0];
	int min = arr[0];

	//找出最大值和最小值
	for (int i = 0; i < sz; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}

		if (arr[i] < min)
		{
			min = arr[i];
		}
	}

	//求出范围,就是要开辟的空间的大小
	int range = max - min + 1; 

	int* count = (int *)calloc(range, sizeof(int)*range);
	if (count == NULL)
	{
		perror("calloc fail!\n");
		return;
	}

	//统计每个数字出现的次数,相对映射到开辟的数组中
	for (int i = 0; i < sz; i++)
	{
		count[arr[i] - min]++;
	}

	//把数据进行排序,放回原数组中
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
		    //后置++,先用后加
			arr[j++] = i + min;
		}
	}
	
	free(count);
	count = NULL;

}

排序结果如下:

在这里插入图片描述

4.归并排序的时间复杂度和稳定性分析:

1.计数排序的局限性在于它更加适用于范围集中的一组整型数据的排序,这时效率非常高,如果数据的范围较大(就是代码中的 range ),或是排序其他类型的数据,就可能不太适用。
2.时间复杂度:O(N+range)
3.空间复杂度:O(range)
4.稳定性:稳定

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/528449.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

网站压力测试和Locust

一、压力测试介绍 网站压力测试是一种评估网站性能、可靠性和稳定性的方法。它通过模拟大量用户同时访问网站,来测试网站的响应时间、吞吐量、资源利用率等指标,从而发现网站的潜在问题和瓶颈。下面我将从几个方面详细介绍网站压力测试: 1、压力测试的目的 评估网站在高并发…

路由器端口映射是什么意思?

路由器端口映射是一种网络配置技术&#xff0c;在私有网络中允许外部网络访问特定的服务或应用程序。通过将路由器的端口映射到内部客户端设备&#xff0c;可以实现从公共网络访问内部网络资源的目的。 天联组网介绍 天联是一款异地组网内网穿透产品&#xff0c;由北京金万维科…

【Qt】:常用控件(九:容器类控件)

常用控件 一.Group Box&#xff08;分组框&#xff09;二.Tab Widget&#xff08;标签页&#xff09; 一.Group Box&#xff08;分组框&#xff09; 使用QGroupBox实现一个带有标题的分组框.可以把其他的控件放到里面作为一组.这样看起来能更好看一点.&#xff08;换言之&…

复现bytetrack时,安装依赖项报错“: ERROR: Failed building wheel for lap

报错原因&#xff1a; lap 库的构建失败&#xff0c;因为缺少了 NumPy 库。 解决办法&#xff1a; 安装 NumPy 库&#xff1a;NumPy 是 Python 中用于科学计算的基础库&#xff0c;lap 依赖于它 pip install numpy 重新安装 lap 库&#xff1a; pip install lap

代码随想录|Day32|贪心算法 part02|● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

122.买卖股票的最佳时机II class Solution: def maxProfit(self, prices: List[int]) -> int: result 0 for i in range(len(prices) - 1): count prices[i1] - prices[i] if count > 0: result count return result 方法二&#xff1a;把if条件变成max class Solutio…

智能配电能效平台与照明系统在某地下污水处理厂中的应用

安科瑞薛瑶瑶18701709087 1、引言 随着互联网、芯片技术、通信传输的技术革新和成熟&#xff0c;智能照明已经广泛应用于居民生活和工业发展领域。传统的工业照明设计&#xff0c;常在门口附近设置集中控制箱&#xff0c;由控制箱内相应开关控制照明。当工厂面积较大&#xf…

ONERugged车载平板终端:提升港口运输水平

现代港口是国际贸易中至关重要的枢纽&#xff0c;而提高港口运输效率对于促进贸易流通和经济发展至关重要。近年来&#xff0c;车载平板技术的快速发展为港口运输行业带来了巨大的变革和机遇。车载平板的广泛应用不仅提高了港口的操作效率&#xff0c;还改善了货物跟踪、通信和…

Vue3中使用的富文本编辑器(详细实现流程)

文章目录 1. 前言2. 项目初始化3. 下载4. 使用富文本编辑器5. 注意点6. 效果图 1. 前言 有不少的前端需求都需要使用到富文本编辑器,但是富文本编辑器百花齐放,每次使用可能都会重新找一个编辑器,所以有了这篇文章. 当项目中需要使用到富文本编辑器时,可以直接按照这篇文章的步…

动态分区算法

一个不知名大学生&#xff0c;江湖人称菜狗 original author: Jacky Li Email : 3435673055qq.com Time of completion&#xff1a;2024.04.09 Last edited: 2024.04.09 目录 动态分区算法 第1关&#xff1a;首次适应算法 任务描述 相关知识 内存分配 内存回收 编程要求…

chronyd服务

一、介绍 chronyd服务是CentOS8系统之后提供时间服务的应用&#xff0c;和之前的ntp服务功能是一样的。 chronyd服务的配置文件默认存在在/etc/chrony.conf中。 chronyd服务的开启方式和关闭&#xff1a; systemctl start chronyd systemctl status chronyd systemctl st…

每天好好学习java第一天--复习巩固基础

1.浮点数数据特殊&#xff1a; float z 2.0e8F; float类型要在后面加f或者F。但是double类型可以省略。 2.强制转换数据类型&#xff1a; 格式&#xff1a; (类型名)变量名 例 float z 2.0f; int x(int)z; 3.逻辑运算符 注意异或 4.条件运算符 每天学习一会java&…

性能分析-数据库与磁盘知识

数据库 数据库&#xff0c;其实是数据库管理系统dbms。 数据库管理系统&#xff0c; 常见&#xff1a; 关系型数据库&#xff1a; mysql、pg、 库的表&#xff0c;表与表之间有关联关系&#xff1b; 表二维表统一标准的SQL&#xff08;不局限于CRUD&#xff09;非关系型数据…

配置VM开机自启动

1. 在此电脑-右键选择“管理”-服务和应用程序-服务中找到VMware Workstation Server服务&#xff08;新版名称也可能是VMware自启动服务&#xff0c;自己找一下&#xff0c;服务属性里有描述信息的&#xff09;&#xff0c;将其启用并选择开机自动启动 新版参考官方文档&…

C语言 函数——函数原型

目录 如何合并成一个完整的程序&#xff1f; 函数原型与函数定义的区别 函数原型的作用 如何合并成一个完整的程序&#xff1f; 问题&#xff1a;在一个函数中调用另一个函数&#xff0c;需要具备哪些条件呢&#xff1f; 若函数的定义出现在函数调用之前 若函数的定义出现…

跨云迁移实操:AWS RDS for mysql 迁移至腾讯云mysql --DTS方式

实操场景&#xff1a;从AWS RDS for mysql 迁移至腾讯云云数据库Mysql&#xff0c;通过腾讯云数据传输服务DTS,进行实时全量增量迁移. 下面九河云给大家带来具体实践介绍 购买迁移数据库--目的端机器&#xff08;腾讯云MYSQL&#xff09; 可以源端为5.7所以新建一个参数模版 其…

4 万字 102 道Java经典面试题总结(2024修订版)- 多线程篇

&#x1f345; 作者简介&#xff1a;哪吒&#xff0c;CSDN2021博客之星亚军&#x1f3c6;、新星计划导师✌、博客专家&#x1f4aa; &#x1f345; 哪吒多年工作总结&#xff1a;Java学习路线总结&#xff0c;搬砖工逆袭Java架构师 &#x1f345; 技术交流&#xff1a;定期更新…

全新AI天空任意生成解决方案,颠覆传统换天效果

在数字化时代&#xff0c;影像创作已经成为企业展示品牌形象、传递信息的重要手段。特别是在汽车拍摄和旅行拍摄等场景中&#xff0c;天空作为画面中不可或缺的元素&#xff0c;其表现往往直接关系到作品的质感和吸引力。然而&#xff0c;传统的天空替换技术往往操作繁琐、效果…

中小初创企业如何做好媒体宣传?

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 中小初创企业在做媒体宣传时&#xff0c;由于通常资源有限&#xff0c;需要更加精明地使用外部资源来提升品牌知名度和业务成长。利用专业的媒体服务商可以是一个非常有效的方法。 明确…

可视化大屏的应用(9):设备运行监控的应用案例

通过可视化大屏&#xff0c;监控人员可以更加直观地了解设备的运行情况&#xff0c;及时发现问题并进行处理&#xff0c;提高设备的稳定性和可靠性&#xff0c;大千UI工场本期带来相关利用的案例&#xff0c;欢迎友友们品鉴。 可视化大屏在设备运行监控领域有以下作用&#xf…

并发编程之AtomicInteger,AtomicLong,LongAdder

系列文章目录 文章目录 系列文章目录前言前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。 AtomicInteger类是系统底层保护的int类型,通过提供执行方法的控制进行值…