深入浅出排序算法之计数排序
目录
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的官方博客中找到了这个词的提法,也算是比较官方的了吧。…...
炉石传说HsMod插件终极指南:55项免费功能解锁全新游戏体验
炉石传说HsMod插件终极指南:55项免费功能解锁全新游戏体验 【免费下载链接】HsMod Hearthstone Modify Based on BepInEx 项目地址: https://gitcode.com/GitHub_Trending/hs/HsMod 你是否厌倦了炉石传说中冗长的动画等待?是否想要更流畅的游戏体…...
从HBM到IEC61000-4-2:解码三大ESD模型在芯片与整机设计中的关键分野
1. 为什么你的芯片还是被静电打坏了? 很多硬件工程师都有过这样的困惑:明明选用的芯片数据手册上明确标注了"ESD防护等级2000V",为什么产品到客户手里还是频繁出现静电损坏?上周我就遇到一个真实案例——某智能门锁厂商…...
PIPAL数据集实战:如何用Elo评分系统提升图像质量评估的准确性
PIPAL数据集实战:如何用Elo评分系统提升图像质量评估的准确性 在计算机视觉领域,图像质量评估(IQA)一直是算法研发的关键环节。随着生成对抗网络(GAN)等技术的突破,传统IQA方法逐渐暴露出局限性…...
GyverDS18库:工业级DS18B20单总线温度驱动设计与实践
1. GyverDS18库深度解析:面向工业级应用的DS18B20全功能驱动设计Dallas DS18B20是业界最成熟的单总线数字温度传感器之一,凭借其独特的1-Wire协议、无需外部ADC、支持多点组网及寄生供电能力,在工业监控、环境监测、智能家电等领域广泛应用。…...
索尼A6000/A7相机APP免费安装保姆级教程(含最新pmca工具下载)
索尼A6000/A7相机APP免费安装全流程指南(2024最新版) 作为一名长期使用索尼微单的摄影师,我深刻理解官方应用商店里那些本应内置的功能被拆分成付费APP的无奈。延时摄影、多重曝光这些基础功能,在二代机型上居然要额外付费解锁&am…...
Unpaywall扩展:一键解锁学术论文的终极免费方案
Unpaywall扩展:一键解锁学术论文的终极免费方案 【免费下载链接】unpaywall-extension Firefox/Chrome extension that gives you a link to a free PDF when you view scholarly articles 项目地址: https://gitcode.com/gh_mirrors/un/unpaywall-extension …...
Tetrazine-NHBoc,cas:1380500-93-5,四嗪-氨基叔丁酯的结构特点
Tetrazine-NHBoc(四嗪-氨基叔丁酯)是一种结合了四嗪基团和N-叔丁氧羰基(NHBoc)保护基的有机化合物,以下是对其的详细介绍:一、基本信息中文名称:四嗪-氨基叔丁酯英文名称:Tetrazine-…...
intv_ai_mk11 GPU算力优化部署:7B模型在CSDN GPU实例上的高效运行方案
intv_ai_mk11 GPU算力优化部署:7B模型在CSDN GPU实例上的高效运行方案 1. 项目背景与价值 intv_ai_mk11是基于Llama架构的7B参数AI对话模型,专为中文场景优化设计。在CSDN GPU实例上部署这类中型模型时,面临的主要挑战是如何在有限显存条件…...
Win11共享打印机连接失败?绕过安全策略的终极指南
1. Win11共享打印机连接失败的真相 最近帮朋友处理Win11共享打印机的问题时,发现这个看似简单的操作居然能卡住这么多人。明明按照传统方法一步步操作,却总是提示各种错误。其实这背后是微软在Win11 22H2版本后引入的新安全策略在作祟 - 他们默认关闭了S…...
像素语言传送门效果实测:Hunyuan-MT-7B对中文网络新词(如‘绝绝子‘)的跨语种意译能力
像素语言传送门效果实测:Hunyuan-MT-7B对中文网络新词(如绝绝子)的跨语种意译能力 1. 测试背景与工具介绍 像素语言跨维传送门是基于腾讯Hunyuan-MT-7B翻译引擎构建的创新翻译工具。与传统翻译软件不同,它将语言转换过程设计成一…...
