计数排序及优化

 

🎉个人名片:

🐼作者简介:一名乐于分享在学习道路上收获的大二在校生
🐻‍❄个人主页🎉:GOTXX

🐼个人WeChat:ILXOXVJE
🐼本文由GOTXX原创,首发CSDN🎉🎉🎉
🕊系列专栏:零基础学习C语言----- 数据结构的学习之路
🐓每日一句:如果没有特别幸运,那就请特别努力!🎉🎉🎉
————————————————

 

🎉文章简介:

本篇文章对   计数排序   的相关知识详细讲解!

如果您觉得文章不错,期待你的一键三连哦,你的鼓励是我创作动力的源泉,让我们一起加油,一起奔跑,让我们顶峰相见!!!🎉🎉🎉


目录

计数排序

基本思想:

图解:

 优化:

实现代码:

性能分析:


计数排序

基本思想:

计数排序与其他排序不同,它没有数据的比较;

基本思想是:计数+排序

计数:

先开一个大小为range(大小后面有讲)的数组tmp,遍历一遍待排序的数据,遍历到某个数据(如5)时,就在tmp数组中下标为5的位置上+1,遍历完待排数据,就计数完成;

排序:

计数完,只需要根据tmp数组,数据就是tmp组的下标,有多少个就是对应下标上的数据,例如

tmp[5]=3;即数据为5的有3个

图解:

 

 优化

为了避免空间的浪费,range的大小为待排数据打最大值减去最小值加1;

range=max-min+1;

例如:如果数据最小值为100,最大值为199,如果用上面的思想,就需要开辟空间为200个int数组,但是前面100个数组位置没有存储数据,就造成了空间浪费,这种情况就需要开100个int空间的数组,数组下标0的位置计数100的出现的次数,当排序时只需要相应的加上100(min)即可;

实现代码:

void CountSort(int* a,int n )
{
    //找出最大最小值
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];

		if (a[i] < min)
			min = a[i];
	}
    //确定要开辟空间的大小
	int range = max - min+1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail");
		return;
	}
    //将开辟数组初始化为0
	memset(count, 0, sizeof(int) * range);
	//计数
	for (int i = 0; i < n; i++)
	{
		count[a[i]-min]++;
	}
	//排序
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
}

性能分析:

时间复杂度:O(N+range)

空间复杂度:O(range)

稳定性:不稳定

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

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

相关文章

汽车一键启动智能系统功能作用

在现代科技的推动下&#xff0c;我们的生活每天都在发生着变化。其中&#xff0c;汽车智能一键启动系统就是科技改变生活的最好例子之一。 首先&#xff0c;我们来简单了解一下汽车智能一键启动系统。它是一种利用先进的电子技术和无线通信技术&#xff0c;实现无需钥匙即可启…

基于单片机智能输液器监控系统的设计

**单片机设计介绍&#xff0c; 基于单片机智能输液器监控系统的设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的智能输液器监控系统可以实现对输液过程的实时监测和控制&#xff0c;以下是一个基本的设计介绍&am…

【数据结构——队列的实现(单链表)】

数据结构——队列的实现&#xff08;单链表&#xff09; 一.队列1.1队列的概念及结构 二.队列的实现2.1 头文件的实现——&#xff08;Queue.h&#xff09;2.2 源文件的实现—— &#xff08;Queue.c&#xff09;2.3 源文件的实现—— &#xff08;test.c&#xff09; 三.队列的…

拼多多API接口,打造智能化电商平台

近年来&#xff0c;电商行业的崛起给人们的购物带来了极大的方便。随着电商行业的发展&#xff0c;拼多多作为新兴电商平台已经成为市场焦点。 同时&#xff0c;随着技术的发展&#xff0c;API&#xff08;Application Programming Interface&#xff0c;应用程序编程接口&…

pta 6翻了 Python3

“666”是一种网络用语&#xff0c;大概是表示某人很厉害、我们很佩服的意思。最近又衍生出另一个数字“9”&#xff0c;意思是“6翻了”&#xff0c;实在太厉害的意思。如果你以为这就是厉害的最高境界&#xff0c;那就错啦 —— 目前的最高境界是数字“27”&#xff0c;因为这…

云课五分钟的一些想法

起源 自中学起&#xff0c;就积极学习和掌握互联网相关知识&#xff0c;到如今已经快30年了。 个人也全程经历了从信息时代的互联网&#xff08;硬&#xff09;到智能时代的大模型&#xff08;软&#xff09;。 整体信息到智能的基础设施&#xff0c;由硬到软&#xff0c;机…

CRM系统:除了销售管理,还能做些什么?

企业的健康发展&#xff0c;离不开业绩的提升。在企业数字化转型的背景下&#xff0c;采用数字化应用进行管理已成为共识。许多企业认识到了应该使用CRM客户管理系统来进行销售管理&#xff0c;但CRM能做的还有很多。下面说说除了销售管理&#xff0c;CRM系统还能做些什么&…

继承和多态_Java零基础手把手保姆级教程(超详细)

文章目录 Java零基础手把手保姆级教程_继承和多态&#xff08;超详细&#xff09;1. 继承1.1 继承的实现&#xff08;掌握&#xff09;1.2 继承的好处和弊端&#xff08;理解&#xff09; 2. 继承中的成员访问特点2.1 继承中变量的访问特点&#xff08;掌握&#xff09;2.2 sup…

石英增强光声光谱气体传感技术中的高精密压力控制解决方案

摘要&#xff1a;光声池内气体压力的可调节控制以及稳定性是保证光声法高精度测量的关键&#xff0c;但在目前的光声和光谱研究中&#xff0c;对气体样品池内压力控制技术的报道极为简单&#xff0c;甚至很多都是错误的&#xff0c;根本无法实现高精度调节和控制&#xff0c;为…

Autosar模块介绍:Memory_3(MemIf-内存接口抽象)

上一篇 | 返回主目录 | 下一篇 Autosar模块介绍&#xff1a;Memory_3(MemIf-内存接口抽象 1 基本术语解释2 MemIf组成结构图 1 基本术语解释 编号缩写原文解释1(Logical) Block——可单独寻址的连续内存区域&#xff08;即&#xff0c;用于读、写、擦除、比较等操作&#xff…

眼科动态图像处理系统使用说明(2023-8-11 ccc)

眼科动态图像处理系统使用说明 2023-8-11 ccc 动态眼科图像捕捉存贮分析与传输系统&#xff0c;是由计算机软件工程师和医学专家组结合&#xff0c;为满足医院临床工作的需要&#xff0c;在2000年开发的专门用于各类眼科图像自动化分析、处理和传输的软件系统。该系统可以和各…

【NLP】大型语言模型,ALBERT — 用于自监督学习的 Lite BERT

&#x1f50e;大家好&#xff0c;我是Sonhhxg_柒&#xff0c;希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流&#x1f50e; &#x1f4dd;个人主页&#xff0d;Sonhhxg_柒的博客_CSDN博客 &#x1f4c3; &#x1f381;欢迎各位→点赞…

基于正余弦算法优化概率神经网络PNN的分类预测 - 附代码

基于正余弦算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于正余弦算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于正余弦优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神经网络…

【Linux】第十五站:环境变量

文章目录 一、进程相关的一些概念1.一些常见的概念2.对于并发3.**进程切换** 二、环境变量1.PATH环境变量2.HOME环境变量3.SHELL环境变量4.env5.系统调用接口与环境变量6.什么是环境变量&#xff1f;7.命令行参数8.main函数的第三个命令行参数9.如何验证环境变量是可以被继承的…

2、工厂模式的实现

工厂模式概念 工厂模式是一种常用的设计模式&#xff0c;它主要用于实例化对象。这种模式的主要思想是在不暴露具体的实现细节的情况下&#xff0c;让客户端能够创建具有特定接口的对象。它可以让我们在运行时决定实例化哪个类。 在C语言中&#xff0c;实例化对象意味着创建一…

使用LLM-Tuning实现百川和清华ChatGLM的Lora微调

LLM-Tuning项目源码&#xff1a; GitHub - beyondguo/LLM-Tuning: Tuning LLMs with no tears&#x1f4a6;, sharing LLM-tools with love❤️.Tuning LLMs with no tears&#x1f4a6;, sharing LLM-tools with love❤️. - GitHub - beyondguo/LLM-Tuning: Tuning LLMs wit…

eNSP毕业设计系列-《大型企业网》-BGP网络无nat

客户主要需求&#xff1a;需要有三栋楼&#xff0c;每栋楼有三个业务。 又新增了要求&#xff0c;要双核心、双防火墙。 所以我根据客户的需求&#xff0c;完成了如下组网设计。 主要技术&#xff0c;MSTPVRRP链路聚合OSPF传统纵网&#xff0c;&#xff08;万金油组合&#…

企业计算机中了eking勒索病毒如何解毒,eking勒索病毒文件恢复

网络技术的不断发展&#xff0c;为企业的生产生活提供了极大便利&#xff0c;但随之而来的网络安全威胁也不断增加&#xff0c;近期&#xff0c;很多企业的计算机服务器遭到了eking勒索病毒攻击&#xff0c;导致企业的计算机服务器所有数据被加密&#xff0c;无法正常使用&…

Swagger3 GET请求,使用对象接收 Query 参数,注解怎么写?

简中互联网上就没一个靠谱的答案&#xff0c;最终翻到了 Github Issue 上才解决&#xff0c;真 TMD…… CSDN 就一坨 shit mountain 解决方案 原文&#xff1a;https://github.com/swagger-api/swagger-core/issues/4177 太长不看&#xff1a; 请求方法参数上加 ParameterObj…

RabbitMQ实战

文章目录 1、简介2、MQ优点缺点MQ的应用场景AMQP工作原理市面上常见的MQ 3、Linux安装RabbitMQ3.1 版本对应3.2 安装socat3.3 下载 Erlang/OTP、安装、验证 erlang方法一&#xff1a;1. 下载2. 将下载的Erlang服务上传到服务器上面3. 解压4. 编译erlang的依赖环境5. 安装Erlang…