排序——计数排序

文章目录

  • 概念
  • 思路
    • 绝对映射:
    • 相对映射
  • 代码实现
  • 特性
  • 结果演示

概念

计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法,而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序,堆排序)

思路

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

绝对映射:

在这里插入图片描述
要排序的数字是多少,对应存放的下标就是多少。

相对映射

在这里插入图片描述
使最小数据和0下标对应,其他数据-最小数据=该数据对应下标。
相对映射解决了决定映射不能存放负数和元素很大时浪费空间的缺点。

代码实现

void CountSort(int* a, int n)
{int min = a[0], 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*)calloc(range, sizeof(int));//用calloc可以把count数组初始化为0,方便后续计数统计for (int i = 0; i < n; i++){count[a[i] - min]++;}int i = 0;for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;//相对映射时减去了min,这里加上min得出原来的数据}}
}

特性

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

结果演示

int main()
{int b[] = { 2,7,3,4,1,2,6,5,11,8 };int n2 = sizeof(b) / sizeof(b[0]);CountSort(b, n2);
printf("CountSort:");for (int i = 0; i < n2; i++){printf("%d ", b[i]);}return 0;
}

在这里插入图片描述

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

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

相关文章

typora导出html添加目录

typora导出html添加目录 使用方法 首先要从typora导出html文件&#xff0c;之后用记事本编辑器html文件 找到文档最后面&#xff0c;如图&#xff1a; 用文字编辑类工具打开sideBar.txt&#xff0c;复制其中所有内容【内容在下面】 在如上图的位置插入所复制的内容 打开修改…

【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)

HashMap工作原理全揭秘 — 核心源码解析 知识盲点概念介绍数据结构数组链表数组VS链表哈希表不同JVM版本HashMap的展现形式 HashMap VS HashTable特性区别对比 hashcodehashCode的作用equals方法和hashcode的关系key为null怎么办执行步骤 核心参数容量探讨负载因子探讨加载因子…

usb个人总结

一、usb工具分析 1、不同的usb抓包工具抓包分析 2、USB抓包分析方式 外接usb分析仪分析 &#xff08;1&#xff09;力科usb分析仪 &#xff08;2&#xff09;HD-USB12 协议分析仪 &#xff08;3&#xff09;沁恒CH552 usb分析仪&#xff0c;软件工具USB2.0 Monitor (4)等等…

PHP留言板实现

完整教程PHP留言板 登陆界面 一个初学者的留言板&#xff08;登录和注册&#xff09;_php留言板登录注册-CSDN博客 留言板功能介绍 百度网盘 请输入提取码 进入百度网盘后&#xff0c;输入提取码&#xff1a;knxt&#xff0c;即可下载项目素材和游客访问页面的模板文件。 &…

基于springboot书籍学习平台源码和论文

首先,论文一开始便是清楚的论述了平台的研究内容。其次,剖析平台需求分析,弄明白“做什么”,分析包括业务分析和业务流程的分析以及用例分析,更进一步明确平台的需求。然后在明白了平台的需求基础上需要进一步地设计平台,主要包罗软件架构模式、整体功能模块、数据库设计。本项…

数学建模-Matlab R2022a安装步骤

软件介绍 MATLAB是一款商业数学软件&#xff0c;用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境&#xff0c;主要包括MATLAB和Simulink两大部分&#xff0c;可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程…

行云部署成长之路 -- 慢 SQL 优化之旅 | 京东云技术团队

当项目的SQL查询慢得像蜗牛爬行时&#xff0c;用户的耐心也在一点点被消耗&#xff0c;作为研发&#xff0c;我们可不想看到这样的事。这篇文章将结合行云部署项目的实践经验&#xff0c;带你走进SQL优化的奇妙世界&#xff0c;一起探索如何让那些龟速的查询飞起来&#xff01;…

【C++干货铺】会旋转的二叉树——AVLTree

个人主页点击直达&#xff1a;小白不是程序媛 C系列专栏&#xff1a;C干货铺 代码仓库&#xff1a;Gitee 目录 前言 AVL树 AVL树的概念 AVL树结点的定义 AVL树的插入 寻找插入结点的位置 修改平衡因子 AVL树的旋转 右单旋 左单旋 先右旋再左旋 先左旋再右旋 AVL树…

SpringBoot多环境配置Maven Profile组

Maven profile组 注意切换配置时 mvn clean下 或者 clean 加install 或者compile 编译 clean之后 install下 或者compile 编译 nohup java -Xms256m -Xmx512m -Dfile.encodingUTF-8 -jar demo.jar --spring.profiles.activeprod > system.log 2>&1 &

数据交付变革:研发到产运自助化的转型之路

作者 | Chris 导读 本文讲述为了提升产运侧数据观察、分析、决策的效率&#xff0c;支持业务的快速迭代&#xff0c;移动生态数据研发部对数仓建模与BI工具完成升级&#xff0c;采用宽表建模与TDA平台相结合的方案&#xff0c;一站式自助解决数据应用需求。在此过程中&#xff…

软件测试|如何使用selenium操作窗口滚动条

简介 我们在进行自动化测试工作的时候&#xff0c;如果页面内容过多&#xff0c;一次性加载耗时太长的话&#xff0c;会使用分段加载来加载页面内容&#xff0c;比如开始只加载页面顶端的内容&#xff0c;而如果要加载更多的数据&#xff0c;就需要我们向下滑动&#xff0c;让…

跳跃游戏,经典算法实战。

&#x1f3c6;作者简介&#xff0c;普修罗双战士&#xff0c;一直追求不断学习和成长&#xff0c;在技术的道路上持续探索和实践。 &#x1f3c6;多年互联网行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &#x1f389;欢迎 &#x1f44d;点赞✍评论…

Go 优雅判断 interface 是否为 nil

关注公众号【爱发白日梦的后端】分享技术干货、读书笔记、开源项目、实战经验、高效开发工具等&#xff0c;您的关注将是我的更新动力&#xff01; 背景 很久之前发过一篇文章&#xff1a;《10个令人惊叹的Go语言技巧&#xff0c;让你的代码更加优雅》&#xff0c;这篇文章中第…

Dockerfile: CMD与ENTRYPOINT区别

CMD和ENTRYPOINT的作用 CMD和ENTRYPOINT这两个命令&#xff0c;我接触到的是用在了Dockerfile中用于构建容器。 CMD&#xff1a;The main purpose of a CMD is to provide defaults for an executing container. CMD的主要用途是为正在执行的容器提供默认值。也就是指定这个容…

如何用ArcGIS制作城市用地适应性评价

01概述 “城市用地适宜性评价是城市总体规划的一项重要前期工作&#xff0c;它首先对工程地质、社会经济和生态环境等要素进行单项用地适宜性评价&#xff0c;然后用地图叠加技术根据每个因子所占权重生成综合的用地适宜性评价结果&#xff0c;俗称“千层饼模式”。 做用地适…

外包干了4年,废了···

有一说一&#xff0c;外包没有给很高的薪资&#xff0c;是真不能干呀&#xff01; 先说一下自己的情况&#xff0c;大专生&#xff0c;19年通过校招进入湖南某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0…

tensorflow报错: DNN library is no found

错误描述 如上图在执行程序的时候&#xff0c;会出现 DNN library is no found 的报错 解决办法 这个错误基本上说明你安装的 cudnn有问题&#xff0c;或者没有安装这个工具。 首先检测一下你是否安装了 cudnn 进入CUDA_HOME下&#xff0c;也就是进入你的cuda的驱动的安装目…

rime中州韵小狼毫 联想词组 滤镜

教程目录&#xff1a;rime中州韵小狼毫须鼠管安装配置教程 保姆级教程 100增强功能配置教程 在 rime中州韵小狼毫 自定义词典 一文中&#xff0c;我们分享了如何在rime中州韵小狼毫须鼠管输入法中定义用户自定义词典&#xff1b;通过自定义词典&#xff0c;我们可以很方便的在…

ppt怎么录屏录音并且导出?好用录屏软件推荐

ppt已经成为了日常工作与学习中必不可少的工具&#xff0c;而ppt屏幕录制功能&#xff0c;可以方便用户将他人的演讲或视频中的内容记录下来&#xff0c;以便进一步学习与研究。录制ppt演示并将其导出为视频文件&#xff0c;可以帮助我们进行分享&#xff0c;但是很多人不知道p…

Qt QGraphicsItem获取鼠标位置对应图像坐标

本次使用了QGraphicsView来加载图像&#xff0c;然后给其设置了一个QGraphicsScene场景&#xff0c;再给场景添加了一个自定义的QGraphicsItem&#xff0c;在其中重写了paint事件&#xff0c;用来重绘图像。 正常情况时&#xff0c;QGraphicsItem上图像的有效区域QRect大小和QG…