经典非比较排序—计数排序的Java实现方式
目录
1.具体思路:
2.代码实现:
3.代码分析
4.示例测试:
测试源码:
测试结果:
计数排序,又被称为鸽巢原理,属于桶排序的一种,其本质是通过哈希映射思想,设定计数数组输入以及输出,实现非比较排序。
1.具体思路:
首先遍历待排序数组获取数组的最大值以及最小值,以此获取极差(两最值之差),根据极差大小设定计数数组,然后继续遍历待排序数组,根据映射关系在计数数组中计数,最后同时遍历计数数组与待排序数组,根据计数数组的计数内容将数据取出输出至待排序的原数组中。
2.代码实现:
该代码中计数数组的映射关系为:计数数组下标为i处的存储空间为大小为i+min(待排序数组中的最小值)的值进行计数,读者也可使用其他合理的映射关系。
public class CountSort {public static void countSort(int[]array){//遍历数组求最大值与最小值,以此获得极差创建计数数组//默认最大值与最小值均为起始元素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[]count=new int[max-min+1];//遍历数组,根据映射关系开始计数for(int i=0;i< array.length;i++){//根据映射关系算出该元素在计数数组中的下标int index=array[i]-min;//对应位置计数加1count[index]++;}//计数完毕,开始遍历计数数组,输出到原数组中//设定原数组下标int index=0;for(int i=0;i< count.length;i++){//值相同的元素可能有多个,即计数数组中可能存在计数不为1的元素,需要多次取出while(count[i]>0){//根据映射关系取出元素int elem=i+min;//输出至原数组中array[index]=elem;//原数组下标移动index++;//计数数组对应计数减1count[i]--;}}}
}
3.代码分析
(1)时间复杂度:O(max(n,极差))(即n与待排序数组极差中的较大值);
(2)空间复杂度:O(极差);
(3)稳定性:稳定。
4.示例测试:
测试源码:
public class Test {public static void main(String[] args) {int[]array={2,4,1,3,6,8,5,7};System.out.println("排序前数组"+Arrays.toString(array));CountSort.countSort(array);System.out.println("排序后数组"+Arrays.toString(array));}
}
测试结果:
以上便是通过java实现计数排序的全部内容,如有不当,敬请斧正!
相关文章:

经典非比较排序—计数排序的Java实现方式
目录 1.具体思路: 2.代码实现: 3.代码分析 4.示例测试: 测试源码: 测试结果: 计数排序,又被称为鸽巢原理,属于桶排序的一种,其本质是通过哈希映射思想,设定计数数组输入以…...

【C++从小白到大牛】栈和队列(优先级队列)
目录 引言: 使用方法篇: stack: queue priority_queue 使用方法: 模拟实现篇: stack: 原码: queue 原码: priority_queue 插入和删除数据的思想: 仿函数实…...

Golang之OpenGL(一)
使用OpenGL实现窗口中绘制三角形(纯色|彩色)、正方形(变色) 一、简单实现窗口绘制三角形二、绘制的多颜色三角形(基于 ‘ 简单实现窗口绘制三角形 ’ )1、在顶点着色器和片段着色器中添加了颜色的输入和输出…...
122. Go反射中与结构体相关的常用方法与应用
文章目录 encoding/jsonreflect 简介reflect.Value 常用方法reflect.Type 常用方法 应用一:使用 reflect 实现 encoding/json序列化反序列化 应用二:使用Tag实现字段级别的访问控制tag 行为自定义案例:结构体字段访问控制 总结 在使用 Go 语言…...

Java入门、进阶、强化、扩展、知识体系完善等知识点学习、性能优化、源码分析专栏分享
场景 作为一名Java开发者,势必经历过从入门到自学、从基础到进阶、从学习到强化的过程。 当经历过几年企业级开发的磨炼,再回头看之前的开发过程、成长阶段发现确实是走了好多的弯路。 作为一名终身学习的信奉者,秉承Java体系需持续学习、…...
Spring-bean销毁
bean销毁(找到销毁的bean) 在bean的声明周期中,存在一个记录bean销毁方法的阶段,以备于spring关闭的时候可以执行bean的销毁方法(单例bean) v1.0 registerDisposableBeanIfNecessary protected void registerDisposableBeanIfNec…...
【4】BlazorUI库
【4】BlazorUI库 一、Blazorise二、Ant Design Blazor三、Radzen Blazo四、Radzen Blazo 一、Blazorise Blazorise Blazorise 是一个广泛使用的 UI 框架,提供了丰富的组件库和多个主题支持,如 Bootstrap、Bulma、Material 和 AntDesign。 二、Ant Desig…...

树与二叉树【下】
目录 三. 哈夫曼树3.1 带权路径长度3.2 哈夫曼树的定义3.3 哈夫曼树的构造3.4 哈夫曼编码(经常考察) 四. 并查集4.1 如何表示“集合”关系?4.2 “并查集”的代码实现4.3 “并查集”的优化4.4 “并查集”的进一步优化 \quad 三. 哈夫曼树 \qua…...

ElementPlus 中el-select自定义指令实现触底加载请求options数据
1) 背景: 老项目翻新时,发现一个下拉框数据非常多,客户呢,希望全部数据一起展示,意思就是全部数据一起返回给前端用于展示。但这会造成明显的卡顿。~~明显的不合理! QAQ!~~ 于是压力给到前端,查询资料,各种…...

基于Selenium实现操作网页及操作windows桌面应用
Selenium操作Web页面 Why? 通常情况下,网络安全相关领域,更多是偏重于协议和通信。但是,如果协议通信过程被加密或者无法了解其协议构成,是无法直接通过协议进行处理。此时,可以考虑模拟UI操作,进而实现相…...
科普文:linux系列之操作系统内存管理简介
概叙 操作系统内存管理是计算机系统中的核心技术之一,页式管理、段式管理和段页式管理各有优缺点。页式管理通过固定大小的页框减少了外部碎片,但可能导致内部碎片;段式管理符合程序逻辑,提供了灵活的内存保护,但可能…...
【已解决】关于MyBatis的collection集合中只能取到一条数据的问题
一、问题 在涉及多表查询的时候,使用collection元素来映射集合属性时,出现了只能查询到一条数据的情况,但用sql语句在数据库中查询会有多条记录。 二、原因 如果两表联查,主表和明细表的主键都是id的话,明细表的多条…...

前端的学习-CSS(弹性布局-flex)
一:什么是弹性布局-Flex flex 是 Flexible Box 的缩写,意为"弹性布局",用来为盒状模型提供最大的灵活性。 语法: .box{display: flex; } .box{display: inline-flex; } 注意,设为 Flex 布局以后࿰…...

vue3集成LuckySheet实现导入本地Excel进行在线编辑,以及导出功能
第一步:克隆或者下载下面的代码 git clone https://github.com/dream-num/Luckysheet.git第二步:安装依赖 npm install npm install gulp -g 第三步:运行 npm run dev效果如下图所示 第四步:打包 打包执行成功后,…...

【征求意见】同济大学--城镇给水厂碳排放核算与评价方法
城镇给水厂保障城镇居民正常生活,是社会经济良性发展的重要基础性设施,对于我国双碳战略目标的实现至关重要。 随着城镇化的发展,城镇供水量不断升高,加上 水资源与生态环境问题不断涌现,人们对水的安全和品质的需求日…...
【Python】后台开发返回方法和状态码类的实现
Python 后台开发中,获取返回的类方法,以及状态码类的实现 代码备份 Code - response.py """ Response class for quick generate response """ from loguru_logger import get_loggerlogger get_logger(__name__)clas…...
opencloudosV8.6和openEuler 24安装 k8s
在三台机器上部署 Kubernetes 集群 1.环境准备2.在所有节点上进行以下步骤1. 更新系统和安装必要的软件包2. 禁用交换分区3. 禁用防火墙和SElinux4.系统主机名5.设置主机名与IP地址解析6.配置内核转发及网桥过滤7. 配置 Docker Cgroup 驱动8. 添加 Kubernetes 仓库并安装 kubea…...

Tensor安装和测试
1: 打开git官方 https://github.com/NVIDIA/TensorRT 2: 下载得到:TensorRT-10.2.0.19.Linux.x86_64-gnu.cuda-11.8.tar.gz 3: 下载后配置环境变量,上面地址记得改成真实地址。 4: 如果想python使用tensorrt,那么 解压后目录,…...

ELK对业务日志进行收集
ELK对业务日志进行收集 下载httpd 进到文件设置收集httpd的文件进行 设置 编辑内容 用于收集日志的内容 将日志的内容发送到实例当中 input {file{path > /etc/httpd/logs/access_logtype > "access"start_position > "beginning"}file{path &g…...
新质生产力
新质生产力”是一个相对较新的概念,指的是在数字化、智能化背景下,依托新技术、新业态、新模式,提升生产力质量和效率的一种生产力形态。它强调的是技术和创新对生产力的提升作用,尤其是在人工智能、大数据、互联网等新兴技术的推…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...

vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...

如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...