【排序算法】 计数排序(非比较排序)详解!了解哈希思想!

在这里插入图片描述

🎥 屿小夏 : 个人主页
🔥个人专栏 : 算法—排序篇
🌄 莫道桑榆晚,为霞尚满天!

文章目录

  • 📑前言
  • 🌤️计数排序的概念
    • ☁️什么是计数排序?
    • ☁️计数排序思想
      • ⭐绝对映射
      • ⭐相对映射
  • 🌤️计数排序的实现
    • ☁️实现思路
    • ☁️代码实现
    • ☁️代码解析
  • 🌤️计数排序特性总结
    • ☁️时间复杂度:
    • ☁️空间复杂度
    • ☁️稳定性
    • ☁️适用性限制
    • ☁️不适用于大规模数据
    • ☁️总结
  • 🌤️全篇总结

📑前言

什么是计数排序?计数排序的思想是什么?它是如何实现的?

本文会对计数排序进行由浅入深的探究,让你彻底掌握计数排序!

🌤️计数排序的概念

☁️什么是计数排序?

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

​ 统计每个元素出现的次数,然后根据元素的大小顺序将它们放入正确的位置。

☁️计数排序思想

计数排序是一种小众的排序,它适合于数据密集的场景,按最大数的数值来开空间。

⭐绝对映射

假设现有一组数据,最大的数据是1000,那么便会开一千个大小的空间,这种属于绝对映射,在极端的场景下,极易造成空间上的浪费,比如现在有5,99,88,1000,8888,452,635,82,777,555,只有10个数但是最大的数是8888因此要开8888大小的空间,剩余的空间全部都浪费了。

⭐相对映射

因此绝大多数情况下,都会使用相对映射。

具体的步骤如下:

  1. 找出待排序数组中的最大值和最小值,并创建一个计数数组,长度为最大值和最小值之差加1。
  2. 遍历待排序数组,统计每个元素出现的次数,并将次数存储在计数数组的相应位置上。
  3. 对计数数组进行累加操作,得到每个元素在排序后数组中的最终位置。
  4. 创建一个与待排序数组长度相同的临时数组,用于存储排序后的结果。
  5. 从后向前遍历待排序数组,根据计数数组中每个元素的值,将元素放入临时数组的相应位置上。
  6. 将临时数组中的元素复制回待排序数组,完成排序。

在这里插入图片描述

🌤️计数排序的实现

☁️实现思路

  1. 找到数组中的最小值和最大值,以确定计数数组的大小。
  2. 然后,根据最小值和最大值计算计数数组的大小,并分配内存空间。
  3. 接下来,将计数数组的所有元素初始化为0。
  4. 然后,遍历原数组,统计每个元素出现的次数,将统计结果保存在计数数组中。
  5. 接着,使用两个循环,将计数数组中的元素按照次数依次放回原数组中。
  6. 最后,释放计数数组的内存空间。

☁️代码实现

//计数排序
void CountSort(int* a, int n)
{int min = a[0];int max = a[0];for (int i = 0; i < n; i++){if (a[i] < min){min = a[i];}if (a[i] > max){max = a[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail");exit(-1);}memset(count, 0, sizeof(int) * range);for (int i = 0; i < n; i++){count[a[i] - min]++;}int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

☁️代码解析

  1. 寻找最小值和最大值: 首先,通过循环遍历输入数组 a,找到数组中的最小值 min 和最大值 max。这是为了确定排序范围。
  2. 确定排序范围: 计算排序范围 range,即 (max - min + 1),这表示需要排序的整数范围。
  3. 创建计数数组: 使用 malloc 函数为计数数组 count 分配内存,该数组的大小是排序范围 range。计数数组用于存储每个整数在输入数组中出现的次数。
  4. 初始化计数数组: 使用 memset 函数将计数数组 count 中的所有元素初始化为0。
  5. 计数: 遍历输入数组 a,对于每个整数 a[i],将其减去 min 的值作为索引,然后在计数数组中对应索引位置的值加1。这一步会统计每个整数在输入数组中出现的次数。
  6. 重构排序数组: 使用两个循环,首先遍历计数数组 count,然后在内部循环中,根据计数数组中的值,将相应数量的整数值还原到原始输入数组 a。这将完成排序过程。

🌤️计数排序特性总结

☁️时间复杂度:

计数排序的时间复杂度为 O(n+k),其中 n 是输入数组的大小,k 是整数的范围。它具有线性时间复杂度的优点,适用于整数排序,特别是当整数范围相对较小且分布均匀时。

☁️空间复杂度

计数排序的空间复杂度取决于整数范围,为 O(k)。因此,它需要额外的空间来存储计数数组,当整数范围较大时可能会占用较多内存。

☁️稳定性

计数排序是一种稳定的排序算法。稳定性意味着具有相同值的元素在排序后仍保持相对顺序不变。在计数排序中,具有相同值的元素会按照它们在输入数组中的顺序被放置在输出数组中。

☁️适用性限制

计数排序仅适用于整数排序,特别是当整数范围相对较小且分布均匀时。它不适用于排序包含负数或浮点数的数组。此外,如果整数范围过大,可能会导致内存占用过多。

☁️不适用于大规模数据

尽管计数排序具有线性时间复杂度的优点,但它对于大规模数据集的排序可能并不理想。当整数范围非常大且分布不均匀时,计数排序的性能可能会受到限制。

☁️总结

计数排序适用于特定范围内的整数排序,并且在这种情况下具有稳定的性能表现。然而,在应用计数排序时,需要仔细考虑整数范围和数据集的分布情况,以确保不会出现内存占用过大或性能下降的情况。

🌤️全篇总结

本章专门对计数排序从概念到实现,进行了细致入微的讲解,期望对你理解掌握计数有所帮助!

看到这里希望给博主留个:👍点赞🌟收藏⭐️关注!
你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。

在这里插入图片描述

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

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

相关文章

四川天蝶电子商务有限公司:短视频运营怎么样?

短视频是一种以短小精悍的内容来吸引用户的新型媒体形式&#xff0c;近年来在社交网络平台上迅速走红&#xff0c;成为当今互联网世界的新宠。然而&#xff0c;要想成功运营短视频&#xff0c;需要借助一系列的策略和技巧&#xff0c;通过精心的规划和执行&#xff0c;才能够吸…

后端开发基本步骤(未完成继续写中)

1.使用spring initializr创建项目 注意&#xff1a;然后低下提供的依赖可用可不用&#xff0c;先不用&#xff0c;后边Maven统一配置依赖&#xff0c; 2.导入依赖 <!-- web --> <dependency><groupId>org.springframework.boot</groupId><artifa…

使用IO完成端口实现简单回显服务器

说明 使用IO完成端口实现简单回显服务器&#xff0c;因为是测试用的&#xff0c;所以代码很粗糙。 提醒 使用的是ReadFile、WriteFile来实现Overlapped IO&#xff0c;正式场合应该用WSARecv、WSASend&#xff0c;原因&#xff1a;来自《Windows网络编程技术》 8.2.5节 在这里…

使用Docker搭建一个“一主两从”的 Redis 集群(超详细步骤)

目录 1、Redis 单机版安装1.1 拉取 Redis1.2 创建数据卷目录1.3 修改 redis.conf1.4 启动 Redis 容器1.5 进入容器连接 Redis 2、Redis 一主两从集群搭建2.1 复制三份 redis.conf2.2 启动 master2.3 启动 两个redis slave2.4 三者关系查看2.5 数据测试 1、Redis 单机版安装 1.…

uniapp生命周期

uniapp生命周期包括应用生命周期、页面生命周期和组件生命周期&#xff1b; 1、应用生命周期 app.vue/uvue是uni-app的朱组件。所有页面都是在app.vue下进行切换&#xff0c;是应用入口文件。但app.vue本身不是页面&#xff0c;这里补鞥编写视图元素&#xff0c;也就没有。 这…

Recommender System复习(考试向)

Recommender System Review OverviewCollaborative Filtering基于用户的CF&#xff08;User CF&#xff09;基于物品的CF&#xff08;Item CF&#xff09;Similarity CalculationBias in CF Evaluation of Recommender SystemFactorization MachinesLatent factor modelLFM算法…

Day 5 登录页及路由 (三) 基于axios的API调用

系列文章目录 本系列记录一下通过Abp搭建后端&#xff0c;VueElement UI Plus搭建前端&#xff0c;实现一个小型项目的过程。 Day 1 Vue 页面框架Day 2 Abp框架下&#xff0c;MySQL数据迁移时&#xff0c;添加表和字段注释Day 3 登录页以及路由 (一&#xff09;Day 4 登录页以…

为什么树莓派安装Ubuntu的时候无法通过有线(网线)连网

这个东西从软件角度有很多解释&#xff0c;但是我这里遇到的情况是&#xff1a; 因为一个标注2A但是实际电流虚标的充电头浪费了我2天的时间。 也即是说&#xff1a;如果你的树莓派无法通过网线联网&#xff0c;很有可能是因为供电不足。因为一个新的树莓派一般不会有故障&am…

XUbuntu22.04之解决桌面突然放大,屏幕跟着鼠标移动问题(一百九十)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…

瑞禧生物分享纳米粉体~二硫化钼粉体 MoS2 纯度:99% 纳米二硫化钼(MoS2)

二硫化钼粉体 名称&#xff1a;二硫化钼粉体 纯度&#xff1a;99% 外观&#xff1a;粉末 纳米二硫化钼(MoS2)粉体硫化钼粉体 二硫化铝化学性质稳定、热稳定性好 、摩擦系数低 、润滑作用优 良且在较为苛 刻的工作环境下能保持 良好的摩擦性能因此二硫化铝被广泛应用于固体润…

拓扑排序--C++实现

1. 定义 前置知识 DAG: Directed Acyclic Graph 有向无环图拓扑序&#xff1a; 像先修课程一样&#xff0c;即任意课程的前置课程都在其前面。 举个例子 在这个图中&#xff0c;1234或者1324是拓扑序。而其他的序列不是&#xff0c;即在一个节点出现之前他的所有祖先节点需…

OSPF复习(2)

目录 一、LSA的头部 二、6种类型的LSA&#xff08;课堂演示&#xff09; 1、type1-LSA&#xff1a;----重要且复杂 2、type2-LSA&#xff1a; 3、type3-LSA&#xff1a; 4、type4-LSA&#xff1a; 5、type5-LSA&#xff1a; 6、type7-LSA&#xff1a; 三、OSPF的网络类…

CSS3媒体查询与页面自适应

2017年9月&#xff0c;W3C发布媒体查询(Media Query Level 4)候选推荐标准规范&#xff0c;它扩展了已经发布的媒体查询的功能。该规范用于CSS的media规则&#xff0c;可以为文档设定特定条件的样式&#xff0c;也可以用于HTML、JavaScript等语言。 1、媒体查询基础 媒体查询…

windows docker desktop 更换镜像 加速

最近 docker hub 访问不了; 经过研究 可以通过添加 代理镜像网址 添加代理服务器的方式 实现完美访问 1添加镜像网站 修改成国内镜像地址就能享受到飞一般的速度&#xff0c;但有一个问题&#xff0c;部分站点镜像不全或者镜像比较老&#xff0c;建议使用多个镜像站。 https…

供应商等级:一级、二级和三级供应商之间有什么区别

作为一名专业采购人员&#xff0c;你知道拥有一个可靠且具有成本效益的供应链有多么重要。确保供应链顺利运行的方法之一就是利用供应商分级。 什么是供应商分级&#xff1f; 供应商分级是根据供应商的绩效和对企业的重要性&#xff0c;对其进行分类的做法。 因此&#xff0c…

计算机毕业设计选题推荐-超市售货微信小程序/安卓APP-项目实战

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…

有方N58 HTTP POST 请求连接 TDengine

串口调试软件&#xff1a;格西调试精灵 第一步先注册网络获取IP地址 建立PPP连接 ATXIIC1\r PPP链路建立成功&#xff0c;查询IP地址 ATXIIC?\r 设置网络APN ATCREG?\r 运行结果&#xff0c;红线处是获…

深度学习数据集大合集—疾病、植物、汽车等

最近又收集了一大批深度学习数据集&#xff0c;今天分享给大家&#xff01;废话不多说&#xff0c;直接上数据&#xff01; 1、招聘欺诈数据集 招聘欺诈数据集&#xff1a;共收集了 200,000 条数据&#xff0c;来自三个网站。 该数据集共收集了 200.000 条数据&#xff0c;分别…

智慧渔业养殖远程监控解决方案

智慧渔业养殖远程监控解决方案 项目背景 影响水产养殖环境的关键参数就是水温、光照、溶氧&#xff0c;氨氮&#xff0c;硫化物、亚硝酸盐等&#xff0c;但这些关键因素即看不见又摸不着很难准确把握。现有的水产管理是以养殖经验为指导&#xff0c;也就是一种普遍的养殖经验…