当前位置: 首页 > news >正文

【数据结构】深入浅出讲解计数排序【图文详解,搞懂计数排序这一篇就够了】

计数排序

  • 前言
  • 一、计数排序算法核心思路
    • 映射 概念补充
    • 绝对映射
    • 相对映射
  • 二、计数排序算法核心实现步骤
  • 三、码源详解
  • 四、效率分析
    • (1)时间复杂度 — O(Max(N,range))
    • (2)空间复杂度 — O(range)



前言

计数排序是一种 非比较排序。计数排序又称为 鸽巢原理 ,是对哈希直接定址法的变形应用


一、计数排序算法核心思路

在这里插入图片描述


映射 概念补充

每个值跟其位置建立出一个关系

绝对映射

数值是几就映射出下标是几。如上图

若数组中数据的大小范围并不是乖乖的从0-1,那么这是再采用绝对映射,则会产生很大的空间浪费。
在这里插入图片描述
那么就有了相对映射的概念

相对映射

在这里插入图片描述
通过遍历原数组,找出min值,将 a[i] 的值 - min值 【即 a[ i ] - min 】就是对应 数组count[ ]的下标了,遍历到一个就令该下标( 对应a[i]的值 )下的 count [ ] 值++计数



二、计数排序算法核心实现步骤

  1. 遍历一遍数组 => 得出min和max值 => 确定数的范围

  2. 确定范围 => 确定需要开辟的数组的大小

  3. 开辟大小为range的空间count [ ] (避免了 绝对映射 那样的空间的浪费) 。用作统计 需排序的数组a[i] 中每个数据出现的次数
    【注意:要进行初始化!!否则待会遍历计数数组中,那些并没有统计到有这个数出现的次数的位置,将以该内存原来的值(随机数)进行填入】

  4. 遍历待排序的数组 => 统计数组中每个数据出现的次数 => 通过 a[i]-min 找到对应下标在 count 中的对应下标 => 对该下标的值对应++进行计数

  5. 遍历计数数组,根据统计到的每个数的次数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. 适用于数据范围相对集中。
  2. 只适合整形
  3. 基数排序

(1)时间复杂度 — O(Max(N,range))

(2)空间复杂度 — O(range)

相关文章:

【数据结构】深入浅出讲解计数排序【图文详解,搞懂计数排序这一篇就够了】

计数排序 前言一、计数排序算法核心思路映射 概念补充绝对映射相对映射 二、计数排序算法核心实现步骤三、码源详解四、效率分析&#xff08;1&#xff09;时间复杂度 — O&#xff08;Max&#xff08;N&#xff0c;range&#xff09;&#xff09;&#xff08;2&#xff09;空间…...

Canvas制作喷泉效果示例

Canvas能制作出很多动画效果&#xff0c;下面是一个制作喷泉效果的示例 效果图 源代码 <!DOCTYPE html> <html> <head> <meta charset"utf-8"> <meta name"viewport" content"widthdevice-width, initial-scale1 ,user-…...

什么是NPM(Node Package Manager)?它的作用是什么?

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…...

oracle如果不适用toad或者plsql工具如何获取索引建表语句

select dbms_lob.substr(dbms_metadata.get_ddl(INDEX,INDEX_NAME,DIXON))||; from dba_indexes where ownerDIXON这个语句可以获取dixon用户的所有索引创建语句&#xff0c;sql脚本形式呈现 点开一个语句查看 如果不使用dbms_lob.substr这个函数最后得到是一个clob selec…...

某大厂伺服驱动器量产方案

本文介一款大厂量产伺服驱动器方案&#xff01;带2500线省线式编码器&#xff0c;17位增量编码器&#xff0c;20位绝对值编码器&#xff01;标配CANopen、高精度运动控制&#xff0c;高速总线通讯&#xff0c;主芯片28335FPGA&#xff0c;已验证过&#xff0c;带can和485通讯&a…...

【计算机网络】网络层:数据平面

一.网络层概述 每台路由器的数据平面的主要功能时从其输入链路向其输出链路转发数据报&#xff0c;控制平面的主要功能是协调这些本地的每路由转发动作&#xff0c;使得数据报沿着源和目的地主机之间的路由器路径最终进行端到端传送。 网络层不运行运输层和应用层协议。 转发是…...

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&#xff1a;用于接受单行文本输入password&#xff1a;用于密码输入&#xff0c;输入字符会被掩盖radio&#xff1a;用于单选按钮&#xff0c;用户可以在一组选项中选择一个checkbox&#xff1a;用于复选框&#xff0c;用户可以选择多个选项number&#…...

共焦显微镜使用

x.1 细胞培养 x.2 样品制备 以细菌为例&#xff0c;我们使用荧光染色细菌&#xff0c;静置15分钟。 15分钟后我们使用实验室的专用培养皿&#xff0c;选择吸收100uL的溶液滴在在培养皿中心。 x.3 显微镜使用 我们按照1, 2, 3, 4的顺序打开显微镜&#xff0c; 打开电脑&…...

windows + Mingw32-make 编译 PoDoFo库,openssl, libjpeg, Msys2工具的使用

参考&#xff1a; https://blog.csdn.net/sspdfn/article/details/104244306 https://blog.csdn.net/yaoyuanyylyy/article/details/17436303 https://blog.csdn.net/wxlfreewind/article/details/106492253 前期进行了各种摸索&#xff0c;由于Podofo依赖库比较多&#xff0c…...

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 贝叶斯决策论&#xff08;Bayesian Decision Theory&#xff09;7.1.1 先验概率&#xff08;Prior Probability&#xff09;7.1.2 后验概率&#xff08;Posterior Probability&#xff09;7.1.3 似然度&#xff08;Likelihood&#xff09;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)中文名称&#xff1a;控制反转&#xff08;对象的创建交给Spring管理&#xff09;。DI(dependency injection )依赖注入。容器&#xff08;Container&#xff09;&#xff1a;放置所有被管理的对象。beans&#xff1a;容器中所有被管理的对…...

C++标准模板(STL)- 类型支持 (类型属性,is_abstract,is_signed,is_unsigned)

类型特性 类型特性定义一个编译时基于模板的结构&#xff0c;以查询或修改类型的属性。 试图特化定义于 <type_traits> 头文件的模板导致未定义行为&#xff0c;除了 std::common_type 可依照其所描述特化。 定义于<type_traits>头文件的模板可以用不完整类型实例…...

前端复制带上版权信息

前端复制带上版权信息 当用户复制内容时&#xff0c;自动添加版权信息。 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. 发明家的特质就是要用质疑的心态对待所有事物&#xff0c;你从未停下质疑&#xff0c;那你将不可避免地成为一个发明家 1.2. 并非所有的事情都有现成的轮子可以拿来用 1.3. 自己重新写一个新的API&#xff0c;最终调用你使用的库 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…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...