超简单的计数排序!!
假设给定混乱数据为:3,0,1,3,6,5,4,2,1,9。
下面我们将通过使用计数排序的思想来完成对上面数据的排序。(先不谈负数)
计数排序
该排序的思路和它的名字一样,通过记录数据出现的次数,来完成数据的排序。我们默认实现的是升序。
思路:
1. 首先我们要先记录下数据的出现次数
这个很简单,我们只需要遍历一遍原数组即可(注意看代码后面的注释!),如下:
count是我们用来记录次数的新数组for (int i = 0; i < sz; ++i){count[a[i]]++;//以原数据的值作为下标!!}
以上面的数据为例,结果如下:

0-9的数字就7和8没有出现。
所以我们现在可以初步的来想一下,用于统计次数的count数组大小是否可以直接使用原数据中最大的一个数据??(之后回答)。
2. 拿到了次数之后,我们就可以开始向原数组进行覆写数据。
比如0出现了1次,我们就将原数组的第1覆写为0。
1出现了2次,将原数组的第二位和第三位覆写为1。
2出现了1次,原数组第四位覆写为2.
.....
7出现了0次,不进行覆写,跳到下一个数据。
8出现了0次,不进行覆写,跳到下一个数据。
...
以此类推,当遍历完count数组之后,数据的覆写就完成了,也就完成了排序。
如下所示:

计数排序的思路已经完成了,现在我们来考虑一下细节问题
1.如何确定count数组的大小
对于上面的数据我们确实可以直接使用9作为count数组的最大值,但是假设有这样一组数据
1000,1001,1002,1008,1009,10005。
此时如果我们选用1009作为count数组的最大值,那么0-998个数组空间根本不会被使用。
所以根据原数据的最大值来确定count数组的最大值是不合理的,我们应该使用原数据中的
最大值-最小值+1来当作count数组的最大值
1009-1000 + 1 = 10;
那么我在统计数据的出现次数的时候也就需要减去一个最小值,比如1000-1000=0;
那么1000就成功的被映射在了count数组的下标0位置处.
1009-1000 = 9,1009也就映射在了下标9的位置处
那么我们在根据次数覆写数据的时候,也就需要count的下标再加上原数据的最小值了。
0+1000 = 1000
1+1000 = 1001
2+1000 = 1002
8+1000 = 1008
9+1000 = 1009
至此我们就完全解决了count数组大小的问题和对极端数据可能会造成空间浪费的问题。
这里是完成的源代码:
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>void Countsort(int* a, int sz)
{//先找去最大和最小的值,以确定数据范围int max = a[0], min = a[0];for (int i = 1; i < sz; ++i){if (a[i] > max)max = a[i];if (a[i] < min)min = a[i];}int range = max - min + 1;//范围int* count = (int*)calloc(range, sizeof(int));if (count == NULL)perror("calloc faild\n");//先统计出次数for (int i = 0; i < sz; ++i){count[a[i] - min]++;//减去最小值是为了防止最大值和最小值差距过大导致的空间浪费}//覆写原数组--排序过程int j = 0;for (int i = 0; i < range; ++i){while (count[i]--){a[j++] = i + min;}}
}
2.原数据中有负数怎么办?
其实这个问题根本不用回答,我们先来用一组负数的数据跑一下,看结果如何:
int main()
{int arr[] = { -9,-8,-4,0,3,3,4,2,1,1,8,9,7 };int sz = sizeof(arr) / sizeof(arr[0]);Countsort(arr, sz);for (int i = 0; i < sz; ++i){printf("%d ", arr[i]);}return 0;
}
运行结果:
![]()
可以看到运行结果完全正确!
至于为什么,就留给大家自己探究了,相信你一定可以!!
相关文章:
超简单的计数排序!!
假设给定混乱数据为:3,0,1,3,6,5,4,2,1,9。 下面我们将通过使用计数排序的思想来完成对上面数据的排序。(先不谈负数) 计数排序 该排序的思路和它的名字一样…...
发现新大陆——原来软件开发根本不需要会编码(看我10分钟应用上线)
目录 一、前言 二、官网基础功能及搭建 三、体验过程 01、连接数据源 02、设计表单 03、流程设计 04、图表呈现 05、组织架构设置 五、效率评价 六、小结 一、前言 众所周知,每家公司在发展过程中都需要构建大量的内部系统, 如运营使用的用户…...
【Leedcode】栈和队列必备的面试题(第二期)
【Leedcode】栈和队列必备的面试题(第二期) 文章目录【Leedcode】栈和队列必备的面试题(第二期)一、题目(用两个队列实现栈)二、思路图解1.定义两个队列2.初始化两个队列3.往两个队列中放入数据4.两个队列出…...
Elasticsearch实战之(商品搜索API实现)
Elasticsearch实战之(商品搜索API实现) 1、案例介绍 某医药电商H5商城基于Elasticsearch实现商品搜索 2、案例分析 2.1、数据来源 商品库 - 平台运营维护商品库 - 供应商维护 2.2、数据同步 2.2.1、同步双写 写入 MySQL,直接也同步往…...
剑指 Offer 14-剪绳子
摘要 剑指 Offer 14- I. 剪绳子 剑指 Offer 14- II. 剪绳子 II 343. 整数拆分 一、动态规划解析 这道题给定一个大于1的正整数n,要求将n 拆分成至少两个正整数的和,并使这些正整数的乘积最大化,返回最大乘积。令x是拆分出的第…...
泰克示波器|MSO64示波器的应用
泰克新一代示波器MSO64为实例来讲解时频域信号分析技术。MSO64采用全新TEK049平台,不仅实现了4通道同时打开时25GS/s的高采样率,而且实现了12-bit高垂直分辨率。同时,由于采用了新型低噪声前端放大ASIC—TEK061,大大降低了噪声水平…...
1.4 黑群晖安装:SataPortMap和DiskIdxMap两种获取方式
tinycore及安装工具下载:工具:链接:https://pan.baidu.com/s/1CMLl6waOuW-Ys2gKZx7Jgg?pwdchct提取码:chcttinycore:链接:https://pan.baidu.com/s/19lchzLj-WDXPQu2cEcskBg?pwddcw2 提取码:d…...
JVM虚拟机概述(2)
3.JVM 运行时数据区 3.1.1 程序计数器(Program Counter Register) 是一块很小的内存空间,用来记录每个线程运行的指令位置,是线程私有的,每个线程都拥有一个程序计数器,生命周期与线程一致,是运行时数据区中唯一一个不…...
Intel CSME 简述
SME 算是 Intel X86 PC 上最神秘的部分了,本文根据 us-19-Hasarfaty-Behind-The-Scenes-Of-Intel-Security-And-Manageability-Engine 一文写成。讲述内容无法证伪,各位随便听听即可,了解这些能够帮助BIOS 工程师更好的理解一些操作的实现。文章基于 Intel 第八代第九代CPU(…...
复位理论基础
先收集资料,了解当前常用的基础理论和实现方式 复位 初始化微控制器内部电路 将所有寄存器恢复成默认值确认MCU的工作模式禁止全局中断关闭外设将IO设置为高阻输入状态等待时钟趋于稳定从固定地址取得复位向量并开始执行 造成复位的原因 有多种引起复位的因素&…...
Python基础知识——列表
列表 列表是可以存放任何数据,包括整型,浮点型,字符串,布尔型等等,是常用的数据类型之一。 1.列表的创建 列表也是一个可迭代对象 1. 普通形式l [1,2,3,4,5] ---整型列表l ["a","b","c&…...
如何使用工时表管理项目和非项目的资源?
对新机会做出反应的能力是企业竞争优势的关键。项目不断涌现,企业需要了解具体的可用性以及是否有资源来接受新事物。更进一步来说,企业需要知道员工将时间花在哪里。 使用 8Manage工时表解决方案,你将始终拥有做出正确业务决策所需的全面知…...
项目经理如何做好质量保证与标准维持?非技术项目经理如何做好质量管控?
项目经理如何做好质量保证与标准维持?非技术项目经理如何做好质量管控?01.质量保障需要重视哪些执行层面的细节02.非技术出身项目经理如何做好质量保障工作03.质量管理除了PDCA,还有哪些推荐的方法04.质量保证与标准维持,作为常态…...
[文件操作] File 类的用法和 InputStream, OutputStream 的用法
能吃是不是件幸福的事呢 文章目录前言1. 文件的相关定义2. 文件类型3. Java对文件系统的操作3.1 对文件的基础操作3.2 读文件3.3 写文件前言 从这章开始,我们就开始学文件操作相关的知识了~ 1. 文件的相关定义 1.文件的定义可以从狭义和广义两个方面解释. 狭义: 指硬盘上的文…...
索莫菲模型的一些理解 Smomerfeld Model
如何解释传统热容算出来的数值与量子模型下的区别? 因为只有费米能附近的电子才能够进行移动,这个是问题的差别所在 我们下面就来介绍如何求费米能(费米能的计算) 既然费米能附近的电子很重要,那么附近的电子有多少很…...
SAP ERP系统MM模块常用增强之四:采购申请输入字段的校验检查
在SAP/ERP项目的实施中采购管理模块(MM)的创建和修改采购申请一般都会有输入字段校验检查的需求,来防止业务人员录入错误或少录入数据,这方面需求部分是可以通过配置实现,比如一些字段是否必输,是否显示等&…...
STM32C0介绍(1)----概述
概述 STM32C0系列微控制器是意法半导体公司推出的一款低功耗、高性能的微控制器产品。它们被设计用于需要小型、低功耗和高度可集成的应用程序,如传感器、消费品、电池供电设备、家庭自动化和安全等应用。该系列的微控制器采用ARM Cortex-M0内核,具有丰…...
windows无盘启动技术开发之传统BIOS(Legacy BIOS)引导程序开发之一
by fanxiushu 2023-03-01 转载或引用请注明原始作者。这个话题可能有点老,UEFI BIOS 已经大量存在,而Legacy BIOS最终会被取代。但是也是作为无盘启动技术里不可或缺的,毕竟还有许多老型号的电脑存在,而且为了兼容性,有…...
mysql实现if语句判断功能的六种使用形式
文章目录 前言一、ifnull函数二、nullif函数三、if函数四、if语句(多用于存储过程)五、if-else语句(多用于存储过程)六、if-elseif-else语句(多用于存储过程)总结前言 在Mysql数据库中实现判断功能有很多方式,具体又分为函数和if语句形式,函数的好处是可以作为sql的一…...
在Vue3这样子写页面更快更高效
前言 在开发管理后台过程中,一定会遇到不少了增删改查页面,而这些页面的逻辑大多都是相同的,如获取列表数据,分页,筛选功能这些基本功能。而不同的是呈现出来的数据项。还有一些操作按钮。 对于刚开始只有 1ÿ…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
