排序算法之计数排序详细解读(附带Java代码解读)
计数排序(Counting Sort)是一种非比较型的排序算法,它通过统计每个元素的出现频率,然后计算元素的位置信息,最后将元素放到正确的位置,从而实现排序。计数排序特别适用于元素范围有限的情况,比如整数的范围较小。
算法思想
计数排序的基本思想是:
- 确定范围:找出待排序数据的最小值和最大值。
- 计数:创建一个计数数组,用来统计每个元素出现的次数。
- 累积:将计数数组中的计数值累积,以确定每个元素的最终位置。
- 排序:根据累积的计数信息将元素放到正确的位置。
过程示例
假设有一个待排序的数组:[4, 2, 2, 8, 3, 3, 1]
步骤 1: 确定范围
- 找到最小值和最大值:
- 最小值 = 1
- 最大值 = 8
步骤 2: 计数
-
创建一个计数数组
count,大小为最大值 - 最小值 + 1:count数组大小为 8(从 1 到 8)。- 初始化
count数组为全零:count = [0, 0, 0, 0, 0, 0, 0, 0]。
-
统计每个元素出现的次数:
- 4 →
count[4 - 1] += 1,count = [0, 0, 0, 1, 0, 0, 0, 0] - 2 →
count[2 - 1] += 1,count = [0, 1, 0, 1, 0, 0, 0, 0] - 2 →
count[2 - 1] += 1,count = [0, 2, 0, 1, 0, 0, 0, 0] - 8 →
count[8 - 1] += 1,count = [0, 2, 0, 1, 0, 0, 0, 1] - 3 →
count[3 - 1] += 1,count = [0, 2, 1, 1, 0, 0, 0, 1] - 3 →
count[3 - 1] += 1,count = [0, 2, 2, 1, 0, 0, 0, 1] - 1 →
count[1 - 1] += 1,count = [1, 2, 2, 1, 0, 0, 0, 1]
- 4 →
步骤 3: 累积
-
将
count数组进行累积:count = [1, 3, 5, 6, 6, 6, 6, 7]
-
累积过程:
count[1] += count[0],count = [1, 3, 2, 1, 0, 0, 0, 1]count[2] += count[1],count = [1, 3, 5, 1, 0, 0, 0, 1]count[3] += count[2],count = [1, 3, 5, 6, 0, 0, 0, 1]count[4] += count[3],count = [1, 3, 5, 6, 6, 0, 0, 1]count[5] += count[4],count = [1, 3, 5, 6, 6, 6, 0, 1]count[6] += count[5],count = [1, 3, 5, 6, 6, 6, 6, 1]count[7] += count[6],count = [1, 3, 5, 6, 6, 6, 6, 7]
步骤 4: 排序
-
创建一个输出数组
output,用于存放排序后的结果:output = [0, 0, 0, 0, 0, 0, 0, 0]
-
从原数组中取出元素,并根据
count数组确定其位置:- 4 →
output[count[4 - 1] - 1] = 4,count[4 - 1] -= 1,output = [0, 0, 0, 4, 0, 0, 0, 0] - 2 →
output[count[2 - 1] - 1] = 2,count[2 - 1] -= 1,output = [0, 0, 2, 4, 0, 0, 0, 0] - 2 →
output[count[2 - 1] - 1] = 2,count[2 - 1] -= 1,output = [0, 2, 2, 4, 0, 0, 0, 0] - 8 →
output[count[8 - 1] - 1] = 8,count[8 - 1] -= 1,output = [0, 2, 2, 4, 0, 0, 0, 8] - 3 →
output[count[3 - 1] - 1] = 3,count[3 - 1] -= 1,output = [0, 2, 2, 3, 0, 0, 0, 8] - 3 →
output[count[3 - 1] - 1] = 3,count[3 - 1] -= 1,output = [0, 2, 2, 3, 3, 0, 0, 8] - 1 →
output[count[1 - 1] - 1] = 1,count[1 - 1] -= 1,output = [1, 2, 2, 3, 3, 0, 0, 8]
最终
output数组为:[1, 2, 2, 3, 3, 4, 8] - 4 →
算法复杂度
-
时间复杂度:
- 最坏情况: O(n + k)
- 平均情况: O(n + k)
- 最佳情况: O(n + k)
其中,n 是元素的数量,k 是元素的范围(最大值 - 最小值 + 1)。
-
空间复杂度: O(n + k) 需要额外的空间来存储计数数组和输出数组。
优点
- 稳定排序:计数排序是一种稳定的排序算法,即相同元素的相对顺序不会改变。
- 时间复杂度低:在元素范围有限的情况下,时间复杂度接近线性。
缺点
- 空间复杂度高:需要额外的空间来存储计数数组,特别是当元素的范围很大时。
- 不适用大范围数据:当数据范围远大于元素数量时,计数排序的空间复杂度可能变得不可接受。
Java代码解读
public class CountingSort {// 主方法:执行计数排序public static void countingSort(int[] arr) {if (arr.length == 0) return;// 1. 找到最小值和最大值int min = arr[0];int max = arr[0];for (int num : arr) {if (num < min) min = num;if (num > max) max = num;}// 2. 创建计数数组int range = max - min + 1;int[] count = new int[range];int[] output = new int[arr.length];// 3. 计数每个元素的出现次数for (int num : arr) {count[num - min]++;}// 4. 累积计数数组for (int i = 1; i < range; i++) {count[i] += count[i - 1];}// 5. 排序元素到输出数组for (int i = arr.length - 1; i >= 0; i--) {output[count[arr[i] - min] - 1] = arr[i];count[arr[i] - min]--;}// 6. 将排序结果复制回原数组System.arraycopy(output, 0, arr, 0, arr.length);}public static void main(String[] args) {int[] arr = {4, 2, 2, 8, 3, 3, 1};System.out.println("排序前的数组:");for (int num : arr) {System.out.print(num + " ");}System.out.println();countingSort(arr);System.out.println("排序后的数组:");for (int num : arr) {System.out.print(num + " ");}}
}
代码说明
-
countingSort方法:
countingSort方法首先找到数组的最小值和最大值,然后创建计数数组和输出数组。- 统计每个元素的出现次数,并将计数数组进行累积。
- 根据累积的计数信息将元素放到正确的位置,并将排序结果复制回原数组。
-
找最小值和最大值:
- 确定数据的范围,以便创建适当大小的计数数组。
-
计数每个元素:
- 使用计数数组统计每个元素的出现次数。
-
累积计数数组:
- 将计数数组累积,以确定每个元素的最终位置。
-
排序到输出数组:
- 根据累积计数信息将元素放到正确的位置,并将排序结果复制回原数组。
相关文章:
排序算法之计数排序详细解读(附带Java代码解读)
计数排序(Counting Sort)是一种非比较型的排序算法,它通过统计每个元素的出现频率,然后计算元素的位置信息,最后将元素放到正确的位置,从而实现排序。计数排序特别适用于元素范围有限的情况,比如…...
Linux:如何使用 Crontab
今天想了解一下Linux Crontab。嗯,在Windows上,可以看做和定时任务差不多。 “要在特定时间进行特定工作。” 如果是这样,可以使用crontab,轻松使用Linux。 1. 基本 (crontab basic) 先看一下基本的crontab使用方法吧。在Linu…...
AI模型:追求全能还是专精?-- 之7 智能工厂程序设计
Q1、感觉上上面离我想做的事情却来越远了。我们跳过讨论直接进入程序设计吧。StringProcessor(文字/信息/数字)抽象代理工厂-创造 Universal given时空区域 |bar PROCESS: 页面版块的图式schema/概念的KE图式CaseFilter 一般应用工厂-制造- General sign…...
如何在本地服务器部署SeaFile自托管文件共享服务结合内网穿透打造私有云盘?
文章目录 1. 前言2. SeaFile云盘设置2.1 Owncould的安装环境设置2.2 SeaFile下载安装2.3 SeaFile的配置 3. cpolar内网穿透3.1 下载安装3.2 Cpolar注册3.3 Cpolar云端设置3.4 Cpolar本地设置 4.公网访问测试5.结语 1. 前言 本文主要为大家介绍,如何使用两个简单软件…...
学习记录:js算法(二十五):合并两个有序链表
文章目录 合并两个有序链表我的思路网上思路 总结 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 图一 示例 1:(如图一) 输入:l1 [1,2,4], l2 [1,3,4] …...
43. 1 ~ n 整数中 1 出现的次数【难】
comments: true difficulty: 中等 edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9843.%201%EF%BD%9En%E6%95%B4%E6%95%B0%E4%B8%AD1%E5%87%BA%E7%8E%B0%E7%9A%84%E6%AC%A1%E6%95%B0/README.md 面试题 43. 1 ~ n 整数中 1 …...
K8S - 理解volumeMounts 中的subpath
在上一篇文章中 springboot service如何动态读取外部配置文件 介绍了springboot 中如何实时读取外部配置文件的内容 部署在K8S 接下来我把它部署在k8s 首先, 我们把配置文件放入项目某个目录 这步部是必须的, 毕竟我们要引入是项目外部的文件…...
java工程师成功转型大数据
时间:2024年09月06日 作者:小蒋聊技术 邮箱:wei_wei10163.com 微信:wei_wei10 音频:喜马拉雅 希望大家帮个忙!如果大家有工作机会,希望帮小蒋推荐一下,小蒋希望遇到一个认真做事…...
visual studio 2022更新以后,之前的有些工程编译出错,升级到Visual studio Enterprise 2022 Preview解决
系列文章目录 文章目录 系列文章目录前言一、解决方法 前言 今天遇到一个问题:visual studio 2022升级成预览版以后,之前的有些工程编译出错。首先代码、项目设置都没有改变,只是更新了visual studio 2022。 在编译工程时,编译器…...
Linux 性能调优技巧
1理解 Linux 性能的基本组成 CPU 使用率:衡量 CPU 在单位时间内被占用的程度。内存使用:关注的是活跃内存与缓存内存的比例,以及是否有过多的交换。I/O 性能:磁盘读写速度直接影响应用程序的响应时间和吞吐量。网络性能ÿ…...
【网络安全】WordPress Uncontrolled Resource Consumption
未经许可,不得转载。 文章目录 WordPresswp-cron.php实战漏洞危害解决措施WordPress WordPress 是全球最广泛使用的内容管理系统(CMS),目前约有 43% 的网站依赖于它。由于其用户友好的界面和丰富的插件功能,WordPress 成为了全球最受欢迎的 CMS。 然而,在使用 WordPres…...
gitee绑定公钥后依旧无法使用_gitee push添加公钥无效
解决: 步骤按照官网操作即可:gitee官方说明 看看远程地址是否使用的http模式,是的话换ssh模式...
Linux 删除 当前下的 mysql-8.0.31 空文件夹
在Linux中,如果你想要删除当前目录下的名为mysql-8.0.31的空文件夹(即该文件夹内没有任何文件或子文件夹),你可以使用rmdir命令。但是,如果mysql-8.0.31文件夹并非完全为空(即它包含文件或子文件夹…...
2024,中国服务器操作系统迎云智主升浪
“主升浪”描述了股市中一轮行情中涨幅最大、上升持续时间最长的阶段。2024年,云与AI深度融合形成了数字经济主升浪,从而打开了中国服务器操作系统的黄金机遇期。 2024年注定将成为非常不平凡的一年。不仅是实现“十四五”规划目标任务的关键一年&#x…...
STM32快速复习(九)RTC时钟模块
文章目录 前言一、RTC是什么?RTC的工作原理?二、库函数以及示例1.标准库函数2.示例代码 总结 前言 STM32 的实时时钟(RTC)是一个独立的定时器。 STM32 的 RTC 模块拥有一组连续计数的计数器,在相应软件配置下…...
Nacos注册中心与OpenFeign远程调用
文章目录 一、注册中心原理二、Nacos注册中心三、服务注册四、服务发现五、OpenFeign 一、注册中心原理 在微服务当中必须有两个角色 服务提供者:提供接口供其它微服务访问 服务消费者:调用其它微服务提供的接口 在大型微服务项目中,服务提供…...
【基础算法总结】双指针
目录 一,双指针算法介绍二,算法原理和代码实现283.移动零1089.复写零202.快乐数11.盛最多水的容器611.有效三角形的个数LRC179.和为s的两个数15.三数之和18.四数之和 三,算法总结 一,双指针算法介绍 双指针算法是基础算法之一&am…...
教你制作一本一对一授权才能阅读的样本册
在这个信息时代,保护个人隐私变得越来越重要。一对一授权阅读机制,正是为了满足这一需求而诞生。今天,就让我来教你如何制作一本只有一对一授权才能阅读的样本册。这不仅适用于保护个人隐私,还能为企业、研究机构等提供安全、高效…...
【DEV工具-IDEA】idea的光标变成黑块了?
项目场景: 解决:windows:按一下insert键。...
没通过算法备案 或许是这几点你没做好
没通过算法备案 或许是这几点你没做好 当企业提交算法备案遭遇“不予通过”时,往往是因为一些看似微小却至关重要的细节未能达到标准。以下是一些常见的原因,希望能为准备备案的企业提供一些预警和指导: ICP备案缺失:互联网信息服…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
