【初阶数据结构】计数排序 :感受非比较排序的魅力
文章目录
- 前言
- 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基础的学习来一个基础的实战,做一个简单的图书管理系统,这里边综合利用了我们之前学习到的类和对象&…...
使用 Spring Boot 实现图片上传
目录 一、前言 二、项目准备 2.1、创建SpringBoot项目 2.2、项目结构 2.3、配置文件 2.4、创建控制器 2.5、创建服务 2.6创建前端界面 2.7、静态资源 三、运行项目 四、测试上传功能 总结 一、前言 在现代 web 开发中,图片上传功能是一个…...
深度解析跨境支付之产品架构
跨境支付企业有能力开放更多的底层能力接口给到外界合作伙伴。其中包括购汇及申报、结汇及申报、换汇(包含汇率查询和外汇兑换、远期锁汇等功能)、境外本地下单、查询、退款、外汇跨境收款、海外代发、VA账户开户及余额查询、VCC发卡及查询等能力。 在这…...
Linux下的线程同步与死锁避免
文章目录 死锁的四个必要条件破坏死锁条件的方法破坏互斥条件使用读写锁(pthread_rwlock_t) 破坏持有并等待条件一次性申请所有资源 破坏不可剥夺条件使用超时锁定机制可重入锁(递归锁) 破坏循环等待条件统一锁顺序 在 Linux 下进…...
【Python爬虫实战】Selenium自动化网页操作入门指南
#1024程序员节|征文# 🌈个人主页:易辰君-CSDN博客 🔥 系列专栏:https://blog.csdn.net/2401_86688088/category_12797772.html 目录 前言 一、准备工作 (一)安装 Selenium 库 ࿰…...
mono源码交叉编译 linux arm arm64全过程
初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github:codetoys,所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的,可以在任何平台上使用。 源码指引:github源…...
矩阵的可解性:关于Ax=b的研究
上一篇文章讲解了如何求解 A x 0 Ax0 Ax0,得到 A A A的零空间。 类似的,我们今天学习的是如何求解 A x b Axb Axb,并以此加强你对线性代数中,代数与空间的理解。 同样的,我们举与上一次一样的例子,矩阵 …...
10.22.2024刷华为OD C题型(三)--for循环例子
脚踝动了手术,现在宾馆恢复,伤筋动骨一百天还真不是说笑的,继续努力吧。 文章目录 靠谱的车灰度图恢复灰度图恢复 -- for循环使用例子 靠谱的车 https://www.nowcoder.com/discuss/564514429228834816 这个题目思路不难,就是要自…...
QT:MaintenanceTool 模块安装工具
QT的MaintenanceTool 工具对已安装的 Qt 进行卸载、修复等其他操作时提示At least one valid and enabled repository required for this action to succeed 解决方式:在设置中添加一个临时的仓库 https://mirrors.tuna.tsinghua.edu.cn/qt/online/qtsdkrepositor…...
同标签实现监听LocalStorage
使用 React 生命周期函数 useEffect来监听和处理 LocalStorage 的变化 import React, { useEffect } from react;const LocalStorageListener () > {useEffect(() > {// 注册监听器const handleStorageChange (event) > {if (event.key myKey) {console.log(注册…...
JAVA高性能缓存项目
版本一 代码实现 import java.util.HashMap; import java.util.concurrent.TimeUnit;public class CacheExample01 {private final static HashMap<String, Integer> cache new HashMap<>();public static Integer check(String userId) throws InterruptedExce…...
做销售用什么网站好/百度关键词搜索技巧
已经在PHP中使用crypt创建了一个哈希密码,并希望在Python中使用crypt模块进行哈希处理。我怎么能做到呢?在这是我的PHP代码:function generateSalt($cost 10) {if (!is_numeric($cost) || $cost < 4 || $cost > 31) {throw new CExcep…...
做网站的需要什么资质证明/百度代做seo排名
1、什么是函数?为什么要用函数? 简单来说,函数就是一个代码段,这个代码段的主体 用{}包含,函数就是讲功能模块化。 2、函数的好处 函数可以使程序更具稳定性和可复用性 3、函数的定义 函数有两种定义方法:1…...
博物馆建设 政府网站/搜索关键词热度
今天我们介绍还有一种用户内核空间通信的方法:proc文件系统。 proc文件系统作为linux提供的一种虚拟文件系统并不占用实际外围存储空间,它仅存在于内存中。系统断电即消失。proc文件系统最開始的设计主要是为满足内核向用户态进程报告其状态而设计&#…...
wordpress主题手机主题/百度文库个人登录
为什么 redis 单线程却能支撑高并发? 纯内存操作 核心是基于非阻塞的 IO 多路复用机制 单线程反而避免了多线程的频繁上下文切换问题 一、Redis的高并发和快速原因 1.redis是基于内存的,内存的读写速度非常快(纯内存); 数据存在内存中,数据结构用H…...
贵阳网站建设制作/营销软文范例大全100
C语言常用宏定义技巧用C语言编程,宏定义是个很重要的编程技巧。用好了宏定义,它可以增强程序的可读性、可移植性、方便性、灵活性等等。 1. 防止一个头文件被重复包含: #ifndef COMDEF_H #define COMDEF_H //头文件内容 #endif 当你所建的工程…...
wordpress主题 时光/少儿培训
取出每个数的各个数位分别与2进行比较即可 public class Main {public static void main(String[] args) {int count 0;for (int i 1; i < 2021; i){int temp i;while(temp ! 0){if(temp % 10 2){count;}temp / 10;}}System.out.println(count); //624} }...