深入浅出排序算法之计数排序
目录
1. 原理
2. 代码实现
3. 性能分析
1. 原理
首先看一个题目,有n个数,取值范围是 0~n,写出一个排序算法,要求时间复杂度和空间复杂度都是O(n)的。
为了达到这种效果,这一篇将会介绍一种不基于比较的排序方法。这种方法被称为计数排序。
计数排序的思路是这样的,对于每一个待排序元素a,如果知道了待排序数组中有多少个比它小的数,那么就可以直接知道在排序后的数组中 a 应该在什么位置上。比如,如果一个数组中有3个数是比a小的,那么,在排序后的数组里,a必然会出现在第4位。
现在问题转化成,对于待排序数组里的一个数,如何能快速知道比它小的数字有多少个。要解决这个问题,我们不能使用比较的办法,那样时间复杂度是无法降下来,只有换一个思路,以空间换时间。因为n个数的取值范围是 0~n,所以,不妨使用一个大小为 n 的数组来统计从0到n,每个数在待排序数组中出现的次数。这个数组类似于直方图数组,因为这种方式也被称做是基于统计的排序。直方图统计的思路简单清晰,在很多题目中都会有出现,一定要熟练掌握这种技巧。

强调:计数排序适合排序一组集中的数据。
2. 代码实现
//计数排序public static void countSort(int[] array) {//1. 找到待排序数组的范围,也就是找到最大值和最小值int max = array[0];int min = array[0];//循环遍历找寻最小值和最大值for (int i = 1; i < array.length; i++) {if (array[i] > max)max = array[i];if (array[i] < min)min = array[i];}//计算待排数组的长度int len = max - min + 1;//2. 定义一个计数数组int[] count = new int[len];//3. 遍历array数组,把数据计数到计数数组中for (int i = 0; i < array.length; i++) {count[array[i] - min]++;}//4. 将array数组还原int index = 0;//来控制array数组的下标for (int i = 0; i < array.length; i++) {//这个循环的作用,是把count里面标记的数据取出来while (count[i] > 0) {array[index] = i + min;index++;count[i]--;}}}public static void main(String[] args) {int[] a = {5,4,3,2,1};Sort.countSort(a);for (int x : a) {System.out.print(x + " ");}}

3. 性能分析
| 时间复杂度 | 空间复杂度 |
| O(MAN(N,范围)) | O(N) |
| 对数据的范围敏感 | 对数据的范围敏感 |
相关文章:
深入浅出排序算法之计数排序
目录 1. 原理 2. 代码实现 3. 性能分析 1. 原理 首先看一个题目,有n个数,取值范围是 0~n,写出一个排序算法,要求时间复杂度和空间复杂度都是O(n)的。 为了达到这种效果,这一篇将会介绍一种不基于比较的排序方法。这…...
大坝水库安全监测终端MCU,智能化管理的新篇章!
我国目前拥有超过9.8万座水库大坝,其中超过95%为土石坝,这些大坝主要是在上世纪80年代以前建造的。这些水库大坝在保障防洪、发电、供水、灌溉等方面发挥了巨大的作用,但是同时也存在一定的安全风险,比如坝体结构破损、坝基渗漏、…...
LeetCode 面试题 16.09. 运算
文章目录 一、题目二、C# 题解 一、题目 请实现整数数字的乘法、减法和除法运算,运算结果均为整数数字,程序中只允许使用加法运算符和逻辑运算符,允许程序中出现正负常数,不允许使用位运算。 你的实现应该支持如下操作:…...
spring-代理模式
代理模式 一、概念1.静态代理2.动态代理 一、概念 ①介绍 二十三种设计模式中的一种,属于结构型模式。它的作用就是通过提供一个代理类,让我们在调用目标 方法的时候,不再是直接对目标方法进行调用,而是通过代理类间接调用。让不…...
我用好说 AI 做二次元人设
你有没有想过自己做一部原创作品? 就像开发《星露谷物语》那样,自己把控作品的 角色、故事、载体、宣传 等方方面面,让 idea 不再只是灵光一闪。 以前是 “万事开头难”,可能第一步都举步维艰。但现在有了 AI 就不同了ÿ…...
付费阅读微信小程序源码/小程序和公众号双版本-多种付费模式前后端+独立源码
源码简介: 付费阅读微信小程序源码,这个是小程序和公众号双版本,它支持多种付费模式前后端独立源码。能够支持免费观看部分文字、视频和音频内容,而其他部分则需要付费才能继续观看。这样更方便变现。 这是付费阅读微信小程序合…...
ref、reactive、toRef、toRefs
ref 作用:定义一个响应式数据 语法:const xxx ref(initValue) 创建一个包含响应式数据的引用对象 js中操作数据:xxx.value 模板中读取数据:不需要.value,直接<div>{{xxx}}</div> 接收的数据:基本类型、对…...
GPT实战系列-如何用自己数据微调ChatGLM2模型训练
GPT实战系列-如何用自己数据微调ChatGLM2模型训练 目录 GPT实战系列-如何用自己数据微调ChatGLM2模型训练1、训练数据广告文案生成模型训练和测试数据组织: 2、训练脚本3、执行训练调整运行 4、问题解决问题一问题二问题三问题四 1、训练数据 广告文案生成模型 输…...
【数电知识点_2023.10.28】
数制与码制 十进制转二进制 8 bits 1 Byte 2|12 //121100自下而上 商为0为止 2|_ 6_…0 2|_ 3_…0 2|1…1 0…1 0.375 //0.3750.011自上而下 小数点为0为止 x 2 ———— 0.75…0 x 2 ———— 1.5…1 x 2 ———— 1…1 BCD码:每4位二进制表示一位十进制 8421…...
spring boot配置ssl(多cer格式)保姆级教程
1. 准备cer格式的证书; 2. 合并cer证书并转化成jks格式的证书 为啥有这一步,因为cer证书配置在spring boot项目中,项目启动不起来。如果有大佬想指导一下可以给我留言,在此先谢过大佬。 1)先创建一个jks格式的证…...
第2篇 机器学习基础 —(4)k-means聚类算法
前言:Hello大家好,我是小哥谈。聚类算法是一种无监督学习方法,它将数据集中的对象分成若干个组或者簇,使得同一组内的对象相似度较高,不同组之间的对象相似度较低。聚类算法可以用于数据挖掘、图像分割、文本分类等领域…...
【Python爬虫+可视化】解析小破站热门视频,看看播放量为啥会这么高!评论、弹幕主要围绕什么展开
大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 如果有什么疑惑/资料需要的可以点击文章末尾名片领取源码 环境使用 Python 3.8 Pycharm 模块使用 import requests import csv import datetime import hashlib import time 一. 数据来源分析 明确需求 明确采集网站以及数…...
Mac电脑专业三维模型展UV贴图编辑工具RizomUV RS + VS 2023有哪些特点
RizomUV RS VS是一款功能强大的UV展开软件,用于在三维模型上创建和编辑UV贴图。它具有直观的用户界面和丰富的功能,能够帮助艺术家和设计师更高效地进行UV展开工作。 RizomUV RS VS支持多种模型格式,包括OBJ、FBX、DAE和3DS等,使…...
Linux文件描述符和文件指针互转
本文研究的主要是Linux中文件描述符fd与文件指针FILE*互相转换的相关内容,具体介绍如下。 简介 1.文件描述符fd的定义: 文件描述符在形式上是一个非负整数。实际上,它是一个索引值,指向内核为每一个进程所维护的该进程打开文件的记录表。当…...
C++11线程
C11线程 创建线程 创建线程需要包含头文件<thread>,使用线程类std::thread 构造函数 默认构造函数 thread() noexcept; 默认构造函数,构造一个线程对象,但它不会启动任何实际的线程执行。 任务函数构造函数 template< class Fun…...
VIVO应用商店评论数据抓取
VIVO应用商店的app评论数据抓取 每个应用的评论能获取到最新的 100页 数据 每页20条,也就是 2000条评论数据 接口: pl.appstore.vivo.com.cn/port/comments/ 爬取运行截图:...
第00章_写在前面
第00章_写在前面 讲师:尚硅谷-宋红康(江湖人称:康师傅) 官网:http://www.atguigu.comhttp://www.atguigu.com/) 一、MySQL数据库基础篇大纲 MySQL数据库基础篇分为5个篇章: 1. 数据库概述与MySQL安装篇…...
测绘人注意,你可能会改变历史!
你也许想不到,曾经有一个测绘人员在进行实地测量作业时,在地图上就这么随手一标注,却让这个地方成为了如今的网红打卡地。 这个地方就是外地游客慕名而来的“宽窄巷子”,如果连这个地方都不知道的成都人,就应该不能算…...
MySQL - 慢查询
慢查询日志用于记录执行时间超过设定的时间阈值的 SQL 查询语句。它的目的是帮助数据库管理员识别和优化执行时间较长的查询,以提高数据库性能: 慢查询定义:慢查询日志记录那些执行时间超过 long_query_time 参数设定的时间阈值的 SQL 查询语…...
go中“哨兵错误”的由来及使用建议
“哨兵错误(sentinel error)”这个词的出处。之前我也只是在一些书籍和资料中见到过,也没深究。当这个网友问了我之后,就深入的翻了翻资料,在golang的官方博客中找到了这个词的提法,也算是比较官方的了吧。…...
【科研必备】Elsevier Tracker:5分钟搞定学术投稿监控的终极解决方案
【科研必备】Elsevier Tracker:5分钟搞定学术投稿监控的终极解决方案 【免费下载链接】Elsevier-Tracker 项目地址: https://gitcode.com/gh_mirrors/el/Elsevier-Tracker 你是否也曾为了追踪Elsevier期刊的审稿状态而反复刷新页面?每天登录系统…...
GME多模态向量模型实战部署:华为云ModelArts一键启动图文检索
GME多模态向量模型实战部署:华为云ModelArts一键启动图文检索 1. 引言:多模态检索的实用价值 想象一下,你正在管理一个大型数字资产库,里面有成千上万的图片和文档。当你想找"去年会议上讨论过的那张数据流程图"时&am…...
别再手动查ID了!用R包一键搞定单细胞Marker基因ID转换(附org.Hs.eg.db实战)
单细胞Marker基因ID转换实战:用org.Hs.eg.db实现高效精准映射 刚完成单细胞聚类分析的研究者,常常会面临一个看似简单却极其耗时的任务——将Marker基因的Symbol标识转换为标准的Entrez ID。这个步骤虽然基础,却直接影响后续GO富集分析的可靠…...
Qt网络编程实战:基于QTcpSocket构建带进度反馈的可靠文件传输系统
1. 为什么需要带进度反馈的文件传输系统 在开发桌面应用时,文件传输是个绕不开的刚需功能。特别是传输大文件时,用户最怕的就是看着界面发呆——不知道传输进行到哪一步了,也不知道还要等多久。我做过一个医疗影像传输系统,医生们…...
OpenCV实战:3种图像降噪滤波器的Python代码对比(附效果图)
OpenCV实战:3种图像降噪滤波器的Python代码对比(附效果图) 在数字图像处理中,噪声是影响图像质量的主要因素之一。无论是来自传感器的不完美,还是传输过程中的干扰,噪声都会降低图像的清晰度和可用性。对于…...
用STM32的定时器输入捕获功能,精准解码433MHz遥控器信号(附完整代码)
STM32定时器输入捕获技术解析:433MHz遥控信号精准解码实战 在智能家居DIY和工业控制领域,433MHz无线通信凭借其穿透性强、成本低廉的优势成为常见选择。但如何稳定可靠地解码这些无线信号,一直是开发者面临的挑战。本文将深入探讨基于STM32硬…...
益象创新与数谷智能,轻量化 AI 定制方案设计谁更优?
在企业数字化转型的下半场,人工智能(AI)的应用正从“大算力、大模型”的盲目崇拜,转向“轻量化、高适配”的务实落地上。对于中小型企业或大型企业的特定业务部门而言,动辄百万级的算力投入并不现实,一套能…...
在Ubuntu 22.04上搞定Gen6D位姿估计:从CUDA 11.8到Pytorch3D 0.7.8的完整环境搭建避坑指南
在Ubuntu 22.04上构建Gen6D位姿估计开发环境的全流程解析 计算机视觉领域的位姿估计技术正在重塑增强现实与机器人导航的边界。Gen6D作为香港大学团队开源的前沿项目,其无需CAD模型的特性为物体位姿识别提供了新思路。本文将彻底拆解Ubuntu 22.04环境下从驱动层到算…...
CYBER-VISION零号协议互联网舆情智能监测与分析系统
CYBER-VISION零号协议:构建你的互联网舆情智能监测雷达 最近和几个做市场、公关的朋友聊天,他们都在抱怨同一个问题:每天花大量时间刷新闻、看社交媒体,就为了捕捉行业动态和用户反馈,生怕错过什么重要信息。人工监测…...
造相Z-Image文生图模型v2:3步搭建你的专属AI画师
造相Z-Image文生图模型v2:3步搭建你的专属AI画师 1. 为什么选择Z-Image v2作为你的AI画师 在众多文生图模型中,造相Z-Image v2以其独特的优势脱颖而出。作为阿里通义万相团队开源的高性能模型,它原生支持768768及以上分辨率的高清图像生成&…...
