【初阶数据结构】计数排序 :感受非比较排序的魅力
文章目录
- 前言
- 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基础的学习来一个基础的实战,做一个简单的图书管理系统,这里边综合利用了我们之前学习到的类和对象&…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...

SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...