【数据结构】深入浅出讲解计数排序【图文详解,搞懂计数排序这一篇就够了】
计数排序
- 前言
- 一、计数排序算法核心思路
- 映射 概念补充
- 绝对映射
- 相对映射
- 二、计数排序算法核心实现步骤
- 三、码源详解
- 四、效率分析
- (1)时间复杂度 — O(Max(N,range))
- (2)空间复杂度 — O(range)
前言
计数排序是一种 非比较排序。计数排序又称为 鸽巢原理 ,是对哈希直接定址法的变形应用。
一、计数排序算法核心思路

映射 概念补充
每个值跟其位置建立出一个关系
绝对映射
数值是几就映射出下标是几。如上图
若数组中数据的大小范围并不是乖乖的从0-1,那么这是再采用绝对映射,则会产生很大的空间浪费。

那么就有了相对映射的概念
相对映射

通过遍历原数组,找出min值,将 a[i] 的值 - min值 【即 a[ i ] - min 】就是对应 数组count[ ]的下标了,遍历到一个就令该下标( 对应a[i]的值 )下的 count [ ] 值++计数。
二、计数排序算法核心实现步骤
-
遍历一遍数组 => 得出min和max值 => 确定数的范围
-
确定范围 => 确定需要开辟的数组的大小
-
开辟大小为range的空间count [ ] (避免了 绝对映射 那样的空间的浪费) 。用作统计 需排序的数组a[i] 中每个数据出现的次数。
【注意:要进行初始化!!否则待会遍历计数数组中,那些并没有统计到有这个数出现的次数的位置,将以该内存原来的值(随机数)进行填入】 -
遍历待排序的数组 => 统计数组中每个数据出现的次数 => 通过 a[i]-min 找到对应下标在 count 中的对应下标 => 对该下标的值对应++进行计数
-
遍历计数数组,根据统计到的每个数的次数count[i],就拷贝回去原数组count[i]次,i+min:对应回原数组中的值,while()循环覆盖原数组
三、码源详解
//计数排序——非比较排序
void CountSort(DataType* a,int n) {//遍历一遍数组 => 得出min和max值 => 确定数的范围int min = a[0]; int max = a[0];for (int i = 0; i < n; i++) {if (a[i] < min) {min = a[i];}if (max < a[i]) {max = a[i];}//确定范围 => 确定需要开辟的数组的大小int range = max - min + 1; //[min,max]左闭右闭,所以+1//开辟大小为range的空间,避免了 绝对映射 那样的空间的浪费DataType* count = (DataType*)malloc(sizeof(DataType)*range);if (count == NULL) {perror("malloc fail");exit(-1);}//内存重置 将count数组中的值都初始化为0,重置数组大小为sizeof(DataType) * range//要进行初始化,否则待会遍历计数数组中,那些并没有统计到有这个数出现的次数的位置,将以该内存原来的值(随机数)进行填入memset(count, 0, sizeof(DataType) * range);//数组中的值//遍历数组 => 统计数组中各数据出现的次数 => 通过 a[i]-min 找到对应下标在 count 中的对应下标 => 对该下标的值对应++进行计数for (i = 0; i < n; i++) {count[a[i] - min]++;}//排序//遍历计数数组,根据统计到的每个数的次数count[i],就拷贝回去原数组count[i]次,覆盖原数组//遍历数组int j = 0; //放外面,遍历a[] j记录的数值 不会别被清for (i = 0; i < range; i++) {while (count[i]--){ //count[i]=0的进不了循环a[j++] = i + min; //i+min:对应回原数组中的值}}}
}
四、效率分析
总体特点:比较小众
- 适用于数据范围相对集中。
- 只适合整形
- 基数排序
(1)时间复杂度 — O(Max(N,range))
(2)空间复杂度 — O(range)
相关文章:
【数据结构】深入浅出讲解计数排序【图文详解,搞懂计数排序这一篇就够了】
计数排序 前言一、计数排序算法核心思路映射 概念补充绝对映射相对映射 二、计数排序算法核心实现步骤三、码源详解四、效率分析(1)时间复杂度 — O(Max(N,range))(2)空间…...
Canvas制作喷泉效果示例
Canvas能制作出很多动画效果,下面是一个制作喷泉效果的示例 效果图 源代码 <!DOCTYPE html> <html> <head> <meta charset"utf-8"> <meta name"viewport" content"widthdevice-width, initial-scale1 ,user-…...
什么是NPM(Node Package Manager)?它的作用是什么?
聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 欢迎来到前端入门之旅!感兴趣的可以订阅本专栏哦!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…...
oracle如果不适用toad或者plsql工具如何获取索引建表语句
select dbms_lob.substr(dbms_metadata.get_ddl(INDEX,INDEX_NAME,DIXON))||; from dba_indexes where ownerDIXON这个语句可以获取dixon用户的所有索引创建语句,sql脚本形式呈现 点开一个语句查看 如果不使用dbms_lob.substr这个函数最后得到是一个clob selec…...
某大厂伺服驱动器量产方案
本文介一款大厂量产伺服驱动器方案!带2500线省线式编码器,17位增量编码器,20位绝对值编码器!标配CANopen、高精度运动控制,高速总线通讯,主芯片28335FPGA,已验证过,带can和485通讯&a…...
【计算机网络】网络层:数据平面
一.网络层概述 每台路由器的数据平面的主要功能时从其输入链路向其输出链路转发数据报,控制平面的主要功能是协调这些本地的每路由转发动作,使得数据报沿着源和目的地主机之间的路由器路径最终进行端到端传送。 网络层不运行运输层和应用层协议。 转发是…...
Path with “WEB-INF“ or “META-INF“: [webapp/WEB-INF/NewFile.html]
2023-11-04 01:03:14.523 WARN 10896 --- [nio-8072-exec-6] o.s.w.s.r.ResourceHttpRequestHandler : Path with "WEB-INF" or "META-INF": [webapp/WEB-INFNewFile.html] spring.mvc.view.prefix:/webapp/WEB-INF/...
百度OCR 接口调用 提示 216101:param image not exist 问题解决
百度提供的文档并没有描述如何解决,例子也是,用工具请求可以通 axios 请求 需要用FormData 传参 let token await getAccessToken() //官网案例那个 请求token// console.log(token, "token");var formData new FormData();// imageBase64 :Base64 图片数据formD…...
1-10 HTML中input属性
HTML中input属性 text:用于接受单行文本输入password:用于密码输入,输入字符会被掩盖radio:用于单选按钮,用户可以在一组选项中选择一个checkbox:用于复选框,用户可以选择多个选项number&#…...
共焦显微镜使用
x.1 细胞培养 x.2 样品制备 以细菌为例,我们使用荧光染色细菌,静置15分钟。 15分钟后我们使用实验室的专用培养皿,选择吸收100uL的溶液滴在在培养皿中心。 x.3 显微镜使用 我们按照1, 2, 3, 4的顺序打开显微镜, 打开电脑&…...
windows + Mingw32-make 编译 PoDoFo库,openssl, libjpeg, Msys2工具的使用
参考: https://blog.csdn.net/sspdfn/article/details/104244306 https://blog.csdn.net/yaoyuanyylyy/article/details/17436303 https://blog.csdn.net/wxlfreewind/article/details/106492253 前期进行了各种摸索,由于Podofo依赖库比较多,…...
C++中图的存储
文章目录 0. 实例图1. 邻接矩阵2. 邻接矩阵2.1 链表数组2.2 链式前向星 3. 参考 0. 实例图 考虑下面这样一个图 1. 邻接矩阵 vis[i][j] 表示从i 到j有一条边。直接用二维数组就可以了。 using namespace std; int vertex_num 5; vector<vector<int>> graph(v…...
西瓜书读书笔记整理(七)—— 第七章 贝叶斯分类器
第七章 贝叶斯分类器 7.1 贝叶斯决策论(Bayesian Decision Theory)7.1.1 先验概率(Prior Probability)7.1.2 后验概率(Posterior Probability)7.1.3 似然度(Likelihood)7.1.4 决策规…...
C#WPF嵌套布局实例
本文演示C#WPF嵌套布局实例。演示了不同布局的简单用法,便于快速应用和掌握。 <Windowx:Class="LayoutDemo.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/x…...
Spring和SpringMVC总结
一、Spring IoC(Inversion of Control)中文名称:控制反转(对象的创建交给Spring管理)。DI(dependency injection )依赖注入。容器(Container):放置所有被管理的对象。beans:容器中所有被管理的对…...
C++标准模板(STL)- 类型支持 (类型属性,is_abstract,is_signed,is_unsigned)
类型特性 类型特性定义一个编译时基于模板的结构,以查询或修改类型的属性。 试图特化定义于 <type_traits> 头文件的模板导致未定义行为,除了 std::common_type 可依照其所描述特化。 定义于<type_traits>头文件的模板可以用不完整类型实例…...
前端复制带上版权信息
前端复制带上版权信息 当用户复制内容时,自动添加版权信息。 HTML内容 <body><h1 inputmode"text">复制我</h1> </body>Js内容 document.addEventListener("copy", (event) > {event.preventDefault(); // 阻止…...
【ArcGIS微课1000例】0077:ArcGIS生成经纬网(shp格式)
使用ArcGIS制图的时候,可以很方便的生成经纬网、方里网及参考格网,但是在需要shp格式的经纬网,进一步在南方cass中使用经纬网的时候,就需要单独生成了。 如下图所示为全球大陆矢量数据,我们基于该数据来生成全球指定间距的经纬网数据。 在ArcGIS中,生成经纬网和方里网均…...
读程序员的制胜技笔记04_有用的反模式(下)
1. 重新发明轮子 1.1. 发明家的特质就是要用质疑的心态对待所有事物,你从未停下质疑,那你将不可避免地成为一个发明家 1.2. 并非所有的事情都有现成的轮子可以拿来用 1.3. 自己重新写一个新的API,最终调用你使用的库 1.3.1. 你的API应该是…...
linux驱动开发环境搭建
使用的是parallel 创建的ubuntu 16.04 ubuntu20.04虚拟机 源码准备 # 先查看本机版本 $ uname -r 5.15.0-86-generic# 搜索相关源码 $ sudo apt-cache search linux-source [sudo] password for showme: linux-source - Linux kernel source with Ubuntu patches linux-sourc…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解
文章目录 一、开启慢查询日志,定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...
Angular中Webpack与ngx-build-plus 浅学
Webpack 在 Angular 中的概念 Webpack 是一个模块打包工具,用于将多个模块和资源打包成一个或多个文件。在 Angular 项目中,Webpack 负责将 TypeScript、HTML、CSS 等文件打包成浏览器可以理解的 JavaScript 文件。Angular CLI 默认使用 Webpack 进行项目…...
Qt 按钮类控件(Push Button 与 Radio Button)(1)
文章目录 Push Button前提概要API接口给按钮添加图标给按钮添加快捷键 Radio ButtonAPI接口性别选择 Push Button(鼠标点击不放连续移动快捷键) Radio Button Push Button 前提概要 1. 之前文章中所提到的各种跟QWidget有关的各种属性/函数/方法&#…...
Modbus转Ethernet IP深度解析:磨粉设备效率跃升的底层技术密码
在建材矿粉磨系统中,开疆智能Modbus转Ethernet IP网关KJ-EIP-101的应用案例是一个重要的技术革新。这个转换过程涉及到两种主要的通信协议:Modbus和Ethernet IP。Modbus是一种串行通信协议,广泛应用于工业控制系统中。它简单、易于部署和维护…...
ubuntu2404 gpu 没接显示器,如何保证远程显示的分辨率
1. 使用 xserver-xorg-video-dummy 创建虚拟显示器 如果系统在无物理显示器连接时无法识别显示输出,可以使用 xserver-xorg-video-dummy 驱动程序创建虚拟显示器。以下是设置步骤: 安装虚拟显示器驱动程序: sudo apt install xserver-xorg-v…...
