当前位置: 首页 > 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…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...