【初阶数据结构】计数排序 :感受非比较排序的魅力
文章目录
- 前言
- 1. 什么是计数排序?
- 2. 计数排序的算法思路
- 2.1 绝对位置和相对位置
- 2.2 根据计数数组的信息来确认
- 3. 计数排序的代码
- 4. 算法分析
- 5. 计数排序的优缺点
- 6.计数排序的应用场景
前言
如果大家仔细思考的话,可能会发现这么一个问题。我们学的七大排序(冒泡排序、选择排序、插入排序、希尔排序、堆排序、快速排序、归并排序)都是通过数组中元素之间比较进行数组中数字挪动,从而达到排序的目的。
以上的排序我们也把它们称为"比较排序"。那在本文中,我们就了解一个非比较的排序——“计数排序”。
1. 什么是计数排序?
计数排序(Counting Sort)是一种线性时间复杂度的排序算法,它通过统计数组中元素的出现次数,来确定每个元素在排序后的数组中的正确位置。
为了让大家更好的理解理解计数排序,我给大家画一幅图:
2. 计数排序的算法思路
- 🍉统计相同元素出现的次数
- 🍉根据统计的结果将序列回收到原来的序列中
想必上面的图已经给你一点提示了。这里就会有两个问题想问一下大家:
- 怎么将待排序的数组中的数字映射到计数的数组中?
- 如何将计数数组中的元素回写到待待排序的数组中,从而达到排序的效果?
2.1 绝对位置和相对位置
绝对位置:从数组首元素开始计算,剩余每个元素的位置都是按照数组首元素为参照的。
举个例子:数组a:[1,5,6,8,9,7,3,2,0,4],那对于计数数组来说用绝对位置就比较好,原因是这个待排序的数组a的元素最小值是为0,最大值为9,这里用绝对位置就比较舒服!
相对位置:先选取待排序数组中的最小值,以这个最小值为基准,从而给剩余的元素在计数数组中确定位置。
举个例子:数组a:[101,100,106,103,105,104],如果你这里硬是要使用绝对位置的话,你就要申请106个整型数据的空间,而我只有6个数据需要排序,开这么大的数据空间就有点得不偿失了。所以我们得采用相对位置,以数组a中的最小值(100)为基准,其余元素按照大小关系依次记录到计数数组中。
所以我建议大家使用相对位置来实现计数排序。
2.2 根据计数数组的信息来确认
我们创建了计数数组之后,我们要怎么讲信息还原到原序列中呢?
就根据我们设定的相对位置加上原本的最小值,就可以还原出待排序数组中元素的值。然后再建立一个循环,根据count数组中的位置元素的值决定循环这个相对位置加上原本的最小值多少次。
3. 计数排序的代码
#include<stdio.h>
#include<stdlib.h>//计数排序 -- 是一个非比较的排序方式
//通过统计数组中每个数字出现的次数,通过创建一个count数组记录这些数字对应出现的次数。(利用相对位置进行对应)void CountSort(int* a, int n)
{//1.为获得相对位置,我们要想找到数组中的最小值还要找最大值int min = a[0],max = a[0];for (int i = 1; i < n; i++){if (min > a[i]){min = a[i];}if (max < a[i]){max = a[i];}}int* count = (int*)calloc(max, sizeof(int));if (count == NULL){perror("calloc fail");return;}//统计数字出现的次数,并将其对应到count数组中for (int i = 0; i < n; i++){//a[i]-min:就相当于a[i]其在count数组中的相对位置count[a[i] - min]++;}int j = 0;//根据count数组复现数字到目标数组中for (int i = 0; i < max; i++){while (count[i]--){a[j++] = min + i;}}
}int main()
{int a[] = { 1,1,6,6,9,8,4,5,1,3,4,7,4 };int size = sizeof(a) / sizeof(int);CountSort(a,size);for (int i = 0; i < size; i++){printf("%d ",a[i]);}printf("\n");return 0;
}
这个排序比较简单,大家只要注重算法的思路就行!!!
4. 算法分析
时间复杂度:计数排序的时间复杂度为 O ( n + k ) O(n + k) O(n+k),其中 n n n 是输入数组的大小, k k k 是输入数据的范围大小。由于不涉及元素之间的比较,计数排序可以在较小的数据范围内达到比比较类排序更高效的结果。
空间复杂度:额外的空间复杂度为 O ( k ) O(k) O(k),因为需要创建一个计数数组用来记录元素的出现次数和累积结果。如果 k k k 过大,则计数排序的空间消耗会很大。
稳定性:计数排序是一种稳定的排序算法,即排序后相同的元素相对位置不发生改变。这一点对于一些带有附加信息的数据排序非常有用。
5. 计数排序的优缺点
- 优点:
🍉时间复杂度低:在适合的情况下,能够达到 O ( n ) O(n) O(n) 的线性时间复杂度。
🍉稳定性:保持了相同元素的相对顺序,对数据处理有额外需求时非常有用。 - 缺点:
🍇限制范围:计数排序只能用于整数类型数据不适用浮点数类型、字符类型的数据等,且适用于数据范围较小的情况。如果数据范围过大,空间复杂度会急剧增加。
🍇额外空间:需要额外的空间来存储计数数组,尤其在范围较大时,空间消耗会非常明显。
6.计数排序的应用场景
由于计数排序对元素范围有一定限制,它更适用于以下场景:
-
成绩统计:假设一个班级的学生成绩是 0-100 分的整数,那么使用计数排序能够快速对这些分数进行排序。
-
投票计数:如果投票结果是有限个选项,可以用计数排序来统计每个选项的票数。
-
基数排序的子过程:在基数排序中,计数排序通常被用作处理每一位数的排序过程。
好了,到这里本文就结束了。觉得本文对你有帮助的话,麻烦给偶点个赞吧!
相关文章:

【初阶数据结构】计数排序 :感受非比较排序的魅力
文章目录 前言1. 什么是计数排序?2. 计数排序的算法思路2.1 绝对位置和相对位置2.2 根据计数数组的信息来确认 3. 计数排序的代码4. 算法分析5. 计数排序的优缺点6.计数排序的应用场景 前言 如果大家仔细思考的话,可能会发现这么一个问题。我们学的七大…...

前后双差速轮之LQR控制
在之前的代码中,我们实现了前后两对双差速轮AGV的运动学正解和逆解。但为了实现对AGV的精确路径跟踪和姿态控制,我们需要引入控制算法。线性二次型调节器(LQR)是一种常用的最优控制方法,可以有效地将系统的状态误差最小化。本文将详细说明如何在之前的C++代码中加入LQR控制…...

Linux之远程连接服务器
1、远程连接服务器简介 (1)什么是远程连接服务器 远程连接服务器通过文字或图形接口方式来远程登录系统,让你在远程终端前登录linux主机以取得可操作主机接口(shell),而登录后的操作感觉就像是坐在系统前面…...
k8s 部署 nexus3 详解
创建命名空间 nexus3-namespace.yaml apiVersion: v1 kind: Namespace metadata:name: nexus-ns创建pv&pvc nexus3-pv-pvc.yaml apiVersion: v1 kind: PersistentVolume metadata:name: nfs-pvnamespace: nexus-ns spec:capacity:storage: 3GiaccessModes:- ReadWriteM…...

从“摸黑”到“透视”:AORO A23热成像防爆手机如何改变工业检测?
在工业检测领域,传统的检测手段常因效率低下、精度不足和潜在的安全风险而受到诟病。随着科技的不断进步,一种新兴的检测技术——红外热成像技术,正逐渐在该领域崭露头角。近期,小编对一款集成红外热成像技术的AORO A23防爆手机进…...

让你的 IDEA 使用更流畅 | IDEA内存修改
随着idea使用越来越频繁,笔者最近发现使用过程中有时候会出现卡顿现象,例如,启动软件变慢,打开项目的速度变慢等: 因此如果各位朋友觉得最近也遇到了同样的困惑,不妨跟着笔者一起来设置IDEA的内存大小吧~ …...

docker run 命令解析
docker run 命令解析 docker run 命令用于从给定的镜像启动一个新的容器。这个命令可以包含许多选项,下面是一些常用的选项: -d:后台运行容器,并返回容器ID;-i:以交互模式运行容器,通常与 -t …...

[Unity Demo]从零开始制作空洞骑士Hollow Knight第十七集:制作第一个BOSS苍蝇之母
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、战斗场景Battle Scene相关逻辑处理 1.防止玩家走出战斗场景的门2.制作一个简单的战斗场景二、制作游戏第一个BOSS苍蝇之母 1.导入素材和制作相关动画2.制作…...

【Nginx系列】499错误
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
Springboot项目控制层注释
Springboot主流的 ----------------------- 简略写法 package com.dx.wlmq.controller;import com.dx.wlmq.domain.Address; import com.dx.wlmq.service.AddresssService; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.web.b…...
从Docker容器中备份整个PostgreSQL
问题 现在需要从Docker容器中备份整个PostgreSQL后,然后,使用备份文件在另外一个pg的docker容器中恢复过来。 步骤 备份旧容器中的PG # 登录到旧的PG容器中 docker exec -it postgres bash # 备份数据库 pg_dumpall -c -U postgres > dump_date %…...

从小需求看大格局:如何用技术智慧赢得客户信任
时间:2024年 10月 26日 作者:小蒋聊技术 邮箱:wei_wei10163.com 微信:wei_wei10 音频:从小需求看大格局:如何用技术智慧赢得客户信任 欢迎大家回到“小蒋聊技术”,这是一个不只是教你如何写…...

模型 支付矩阵
系列文章 分享 模型,了解更多👉 模型_思维模型目录。策略选择的收益分析工具。 1 支付矩阵的应用 1.1 支付矩阵在市场竞争策略分析中的应用 支付矩阵是一种强大的决策工具,它在多个领域的应用中都发挥着重要作用。以下是一个具体的应用案例…...

擎创科技声明
近日,我司陆续接到求职者反映,有自称是擎创科技招聘人员,冒用“上海擎创信息技术有限公司”名义,用“126.com”的邮箱向求职者发布招聘信息,要求用户下载注册APP,进行在线测评。 对此,我司郑重…...

二叉树习题其六【力扣】【算法学习day.13】
前言 书接上篇文章二叉树习题其四,这篇文章我们将基础拓展 ###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一…...

互联网的无形眼睛:浏览器指纹与隐私保护攻略
你是否曾有过这样的经历:在某个电商网站上搜索了某件商品,随后无论你打开哪个网页,都能看到与之相关的广告?或者当你再次访问某个网站时,它居然记得你之前的浏览记录?这一切,背后都有一只“看不…...
后端技术:有哪些常见的应用场景?
篇一、 原文链接:https://www.zhihu.com/question/642709585/answer/3388752666 1、数据处理和存储 后端技术可用于处理和存储大量数据,例如构建数据库系统、设计高效的数据结构、实现算法等。常见的数据库技术有关系型数据库(如MySQL、O…...

【Unity 安装教程】
Unity 中国官网地址链接 Unity - 实时内容开发平台 | 3D、2D、VR & AR可视化https://unity.cn/首先我们想要安装Unity之前,需要安装Unity Hub: Unity Hub 是 Unity Technologies 开发的一个集成软件,它为使用 Unity 引擎的开发者提供了一…...
C++ 二级测试卷及答案
1.与指定数字相同的数的个数 题目描述:输出一个整数序列中与指定数字相同的数的个数。 输入 输入包含三行: 第一行为N,表示整数序列的长度(N≤100); 第二行为N个整数,整数之间以一个空格分开; 第三行包含一个整数,为指定的数字m。 输出 输出为…...

Java基础(7)图书管理系统
目录 1.前言 2.正文 2.1思路 2.2Book包 2.3people包 2.4operation包 2.5主函数 3.小结 1.前言 哈喽大家好吖,今天来给前面Java基础的学习来一个基础的实战,做一个简单的图书管理系统,这里边综合利用了我们之前学习到的类和对象&…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...

css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...

QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...

GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...

MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...