【数据结构】-计数排序

news/2024/3/29 6:34:10/文章来源:https://blog.csdn.net/qq_69369227/article/details/130136852

🎇作者:小树苗渴望变成参天大树
🎉 作者宣言:认真写好每一篇博客
🎊作者gitee:link
在这里插入图片描述
如 果 你 喜 欢 作 者 的 文 章 ,就 给 作 者 点 点 关 注 吧!

文章目录

  • 前言
  • 一、计数排序
  • 二、排序算法复杂度及稳定性分析
  • 三、总结


前言

答应大家的计数排序今天它来了,这也是一个非常巧妙的方法,不通过比较元素的大小就可以排序出来,通过用另一个人数组的下标来表示原数组里面的元素的值,然后通过此数出现的个数进行排序


一、计数排序

我们来看图解:
在这里插入图片描述

目前我们要解决的问题就是计数数组的大小怎么确定,既然计数数组的下标是原数组里面的值,那开的数组的大小最小为原数组中最大元素大小加一,例如上面实例,最大值为5,我们就要开6个大小的空间。

我们来看计数排序的代码:

void CountSort2(int* a, int n)
{int max = 0;for (int i = 0; i < n; i++)//找出最大值和最小值{if (a[i] >= a[max]){max = i;}}int count = a[max] + 1;int* tmp = (int*)malloc(sizeof(int) * count);//开辟范围差数组memset(tmp, 0, sizeof(int) * count);//将开辟的计数数组赋值为0for (int i = 0; i < n; i++)//计数,{tmp[a[i]]++;}int j = 0;for (int i = 0; i < count; i++)//排序{while (tmp[i]--){a[j++] = i;}}
}

我们来看运行结果:
在这里插入图片描述

但是这个代码有一个不好的地方,但数据出现最大数和最小数都很大很大的时候,例如:90,93,100,1001
那这个时候我们开辟的计数数组就太大的,浪费了,所以我们就要想一个办法,我们可以开辟一个范围大小,下标就表示原数组的元素减最小数的大小
我们再来看改进的计数排序:

void CountSort1(int* a, int n)
{int min = 0;int max = 0;for (int i = 0; i < n; i++)//找出最大值和最小值{if (a[i] <= a[min]){min = i;}if (a[i] >= a[max]){max = i;}}int count = a[max] - a[min] + 1;int* tmp = (int*)malloc(sizeof(int) * count);//开辟范围差数组memset(tmp, 0, sizeof(int) * count);for (int i = 0; i < n; i++)//计数,{tmp[a[i] - min]++;}int j = 0;for (int i = 0; i < count; i++)//排序{while (tmp[i]--){a[j++] = i + min;}}
}

看运行结果:
在这里插入图片描述
但是还是有不好的地方,当最大数和最小数差距很大,并且中间数据很少的时候,例如1,3,5,1000
这个时候计数排序就不是很友好,这个没有办法解决,这也是计数排序的缺点,所以计数排序适合数比较集中的排序。

计数排序的特性总结:

  1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
  2. 时间复杂度:O(MAX(N,范围))
  3. 空间复杂度:O(范围)
  4. 稳定性:稳定

二、排序算法复杂度及稳定性分析

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
在这里插入图片描述
在这里插入图片描述
大家可以看看我之前排序的博客,来看看是否稳定。这里我就不在一一分析了。大家记住结论就行了。

三、总结

到这篇博客结束后,我们关于排序的讲解就到此结束,数据结构初阶的内容就现分享到这里了,博主接下来徽更新关于c++初阶和linux相关的知识,倒是希望大家可以来支持一下博主,我们下一个专栏见
在这里插入图片描述

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

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

相关文章

《花雕学AI》18:AI绘画尝鲜Prompt Hunt,使用人工智能模型来创造、探索和分享艺术作品

引言&#xff1a; 人工智能是当今科技领域的热门话题&#xff0c;它不仅可以帮助人类解决各种实际问题&#xff0c;也可以激发人类的创造力和艺术感。Prompt Hunt就是一个利用人工智能模型来创造、探索和分享艺术作品的AI绘画网站。它提供了三种不同的模型&#xff0c;分别是S…

Java垃圾收集原理

程序计数器、虚拟机栈、本地方法栈这三个区域随线程而灭&#xff0c;栈中栈帧的内存大小也是在确定的。这几个区域的内存分配和回收都具有确定性&#xff0c;因此不需要过多考虑如何回收。 Java堆和方法区这两个区域有着很显著的不确定性 一个接口的实现类需要的内存可能不一…

用Flutter开发一款音乐App(从0到1开发一款音乐App)

Flutter Music_Listener(flutter音乐播放器) Flutter version 3.9 项目介绍 1、项目整体基于getxretrofitdiojsonserialize开发 2、封装通用控制器BaseController&#xff0c;类似jetpack mvvm框架中的BaseViemodel 3、封装基础无状态基类BaseStatelessWidget&#xff0c;结合…

十三、市场活动:全部导出

功能需求&#xff1a;批量导出市场活动 用户在市场活动主页面,点击"批量导出"按钮,把所有市场活动生成一个excel文件,弹出文件下载的对话框; 用户选择要保存的目录,完成导出市场活动的功能. *导出成功之后,页面不刷新 功能分析&#xff1a;导出市场活动 1.给批量…

Vue组件化编程【Vue】

2.Vue 组件化编程 2.1 模块与组件、模块化与组件化 2.1.1 模块 理解&#xff1a;向外提供特定功能的js程序&#xff0c;一般就是一个js文件为什么&#xff1a;js文件很多很复杂作用&#xff1a;复用js、简化js的编写、提高js运行效率。 2.1.2 组件 理解&#xff1a;用来实…

接口自动化【一】(抓取后台登录接口+postman请求通过+requests请求通过+json字典区别)

文章目录 前言一、requests库的使用二、json和字典的区别三、后端登录接口-请求数据生成四、接口自动化-对应电商项目中的功能五、来自postman的代码-后端登录总结前言 记录&#xff1a;json和字典的区别&#xff0c;json和字段的相互转化&#xff1b;postman发送请求与Python…

source insight4.0使用技巧总结

一、技巧1&#xff1a;查看函数调用关系 步骤 1&#xff1a;在主菜单中点击下图中的按钮 图 1 打开relation界面 步骤 2&#xff1a;在弹出的relation界面点击“设置”按钮&#xff0c; 图2 点击“设置”按钮 步骤3&#xff1a; 在“设置”界面中&#xff0c;“Levels”选择…

AC7811-FOC无感控制代码详解

目录 矢量控制原理 矢量控制框图 电流采样方式 电流在整个控制过程中的传递 采样关键点 三电阻 双电阻 单电阻 三者对比 坐标变换 dq轴电流的PI控制 启动方式 启动波形 脉冲注入 高频注入 Startup 预定位到指定角度 PulseInject_api hfi_api Speed loop s…

前端学习:HTML块、类、Id

目录 快 一、块元素、内联元素 二、HTML 元素 三、HTML元素 类 一、分类块级元素 二、分类行内元素 Id 一、使用 id 属性 二、 class与ID的差异 三、总结 快 一、块元素、内联元素 大多数HTML元素被定义为块级元素或内联元素。 块级元素在浏览器显示时&#xff0c;通常会…

FTP-----局域网内部传输文件(1)

在日常工作中&#xff0c;如果需要跨设备的传输文件&#xff0c;您需要借助USB数据线或者借助应用实现无线互联&#xff0c;将所需文件传输到对应设备&#xff0c;这一来一去&#xff0c;花费的时间与精力变多了&#xff0c;那么&#xff0c;怎么实现不使用第三方软件来实现跨设…

3-5年以上的功能测试如何进阶自动化?【附学习路线】

做为功能测试人员来讲&#xff0c;从发展方向上可分两个方面&#xff1a; 1、业务流程方向 2、专业技能方向。 当确定好方向后&#xff0c;接下来就是如何达到了。(文末自动化测试学习资料分享) 一、业务流程方向 1、熟悉底层的业务 作为功能测试工程师来讲&#xff0c;了解…

【C++高级】手写线程池项目-经典死锁问题分析-简历项目输出指导

作为五大池之一&#xff0c; 线程池的应用非常广 泛&#xff0c;不管是客户端程序&#xff0c;还是后台服务程序&#xff0c;掌握线程池&#xff0c;是提高业务处理能力的必备模块 本课程将带你从零开始&#xff0c;设计一个支持fixed和cached模式的线程池&#xff0c;玩转C11、…

IGA_PLSM3D的理解1

文章目录前言一、IgaTop3D_FAST.m给的参数二、Material properties 材料特性对Geom_Mod3D的理解对Pre_IGA3D的理解 输出1-----CtrPts&#xff1a; 输出2-----Ele&#xff1a; 输出3-----GauPts&#xff1a;前言 只是为方便学习&#xff0c;不做其他用途 一、IgaTop3D_FAST.m给的…

Python爬虫-某跨境电商(AM)搜索热词

前言 本文是该专栏的第42篇,后面会持续分享python爬虫干货知识,记得关注。 关于某跨境电商(AM),本专栏前面有单独详细介绍过,获取配送地的cookie信息以及商品库存数据,感兴趣的同学可往前翻阅。 1. python爬虫|爬取某跨境电商AM的商品库存数据(Selenium实战) 2. Seleni…

5.39 综合案例2.0 - STM32蓝牙遥控小车1(手机APP遥控)

综合案例2.0 - 蓝牙遥控小车1- 手机APP遥控成品展示案例说明器件说明连线小车源码手机遥控APPAPP使用说明成品展示 案例说明 用STM32单片机做了一辆蓝牙控制的麦轮小车&#xff0c;分享一下小车的原理和制作过程。 控制部分分为手机APP&#xff0c;语音模块控制&#xff0c;Ha…

15-721 chapter2 内存数据库

Background 随着时代的发展&#xff0c;DRAM可以容纳足够的便宜&#xff0c;容量也变大了。对于数据库来说&#xff0c;数据完全可以fit in memory&#xff0c;但同时面向disk的数据库架构不能很好的发挥这个特性 这张图是disk database的cpu instruction cost 想buffer pool…

第5章 继承-Java核心技术·卷1

文章目录Java与C不同基本概念继承&#xff1a;基于已有的类创建新的类。构造器多态定义超类变量可以引用所有的子类对象&#xff0c;但子类变量不能引用超类对象。子类引用的数组可以转换成超类引用的数组覆写返回子类型强制类型转换阻止继承&#xff1a;final类和方法多态 vs …

ROS学习-ROS简介

文章目录1.ROS1.1 ROS概念1.2 ROS特征1.3 ROS特点1.4 ROS版本1.5 ROS程序其他名词介绍1. 元操作系统2. IDL 接口定义语言一些网站1.ROS 1.1 ROS概念 ROS(Robot Operating System&#xff0c;机器人操作系统) ROS 是一个适用于机器人的开源的元操作系统&#xff0c;提供一系列…

linux驱动开发 - 04_Linux 设备树学习 - DTS语法

文章目录Linux 设备树学习 - DTS语法1 什么是设备树&#xff1f;2 DTS、DTB和DTC3 DTS 语法3.1 dtsi 头文件3.2 设备节点3.3 标准属性1、compatible 属性2、model 属性3、status 属性4、#address-cells 和#size-cells 属性5、reg 属性6、ranges 属性7、name 属性8、device_type…

人工智能专题-知识表示

文章目录人工智能专题-知识表示大纲2.1 知识表示的概念2.1.1 知识表示观点2.1.2 知识表示的要求2.2 一阶谓词逻辑表示法2.2.1 一阶谓词概念2.2.2 谓词逻辑表示方法2.3 产生式表示法2.4 语义网络表示法2.5 框架表示法人工智能专题-知识表示 大纲 大纲&#xff1a;掌握知识表示方…