当前位置: 首页 > news >正文

经典非比较排序—计数排序的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.具体思路&#xff1a; 2.代码实现&#xff1a; 3.代码分析 4.示例测试&#xff1a; 测试源码&#xff1a; 测试结果&#xff1a; 计数排序&#xff0c;又被称为鸽巢原理&#xff0c;属于桶排序的一种&#xff0c;其本质是通过哈希映射思想&#xff0c;设定计数数组输入以…...

【C++从小白到大牛】栈和队列(优先级队列)

目录 引言&#xff1a; 使用方法篇&#xff1a; stack&#xff1a; queue priority_queue 使用方法&#xff1a; 模拟实现篇&#xff1a; stack&#xff1a; 原码&#xff1a; queue 原码&#xff1a; priority_queue 插入和删除数据的思想&#xff1a; 仿函数实…...

Golang之OpenGL(一)

使用OpenGL实现窗口中绘制三角形&#xff08;纯色|彩色&#xff09;、正方形&#xff08;变色&#xff09; 一、简单实现窗口绘制三角形二、绘制的多颜色三角形&#xff08;基于 ‘ 简单实现窗口绘制三角形 ’ &#xff09;1、在顶点着色器和片段着色器中添加了颜色的输入和输出…...

122. Go反射中与结构体相关的常用方法与应用

文章目录 encoding/jsonreflect 简介reflect.Value 常用方法reflect.Type 常用方法 应用一&#xff1a;使用 reflect 实现 encoding/json序列化反序列化 应用二&#xff1a;使用Tag实现字段级别的访问控制tag 行为自定义案例&#xff1a;结构体字段访问控制 总结 在使用 Go 语言…...

Java入门、进阶、强化、扩展、知识体系完善等知识点学习、性能优化、源码分析专栏分享

场景 作为一名Java开发者&#xff0c;势必经历过从入门到自学、从基础到进阶、从学习到强化的过程。 当经历过几年企业级开发的磨炼&#xff0c;再回头看之前的开发过程、成长阶段发现确实是走了好多的弯路。 作为一名终身学习的信奉者&#xff0c;秉承Java体系需持续学习、…...

Spring-bean销毁

bean销毁(找到销毁的bean) 在bean的声明周期中&#xff0c;存在一个记录bean销毁方法的阶段&#xff0c;以备于spring关闭的时候可以执行bean的销毁方法&#xff08;单例bean&#xff09; v1.0 registerDisposableBeanIfNecessary protected void registerDisposableBeanIfNec…...

【4】BlazorUI库

【4】BlazorUI库 一、Blazorise二、Ant Design Blazor三、Radzen Blazo四、Radzen Blazo 一、Blazorise Blazorise Blazorise 是一个广泛使用的 UI 框架&#xff0c;提供了丰富的组件库和多个主题支持&#xff0c;如 Bootstrap、Bulma、Material 和 AntDesign。 二、Ant Desig…...

树与二叉树【下】

目录 三. 哈夫曼树3.1 带权路径长度3.2 哈夫曼树的定义3.3 哈夫曼树的构造3.4 哈夫曼编码&#xff08;经常考察&#xff09; 四. 并查集4.1 如何表示“集合”关系&#xff1f;4.2 “并查集”的代码实现4.3 “并查集”的优化4.4 “并查集”的进一步优化 \quad 三. 哈夫曼树 \qua…...

ElementPlus 中el-select自定义指令实现触底加载请求options数据

1) 背景: 老项目翻新时&#xff0c;发现一个下拉框数据非常多&#xff0c;客户呢&#xff0c;希望全部数据一起展示&#xff0c;意思就是全部数据一起返回给前端用于展示。但这会造成明显的卡顿。~~明显的不合理! QAQ!~~ 于是压力给到前端&#xff0c;查询资料&#xff0c;各种…...

基于Selenium实现操作网页及操作windows桌面应用

Selenium操作Web页面 Why? 通常情况下&#xff0c;网络安全相关领域&#xff0c;更多是偏重于协议和通信。但是&#xff0c;如果协议通信过程被加密或者无法了解其协议构成&#xff0c;是无法直接通过协议进行处理。此时&#xff0c;可以考虑模拟UI操作&#xff0c;进而实现相…...

科普文:linux系列之操作系统内存管理简介

概叙 操作系统内存管理是计算机系统中的核心技术之一&#xff0c;页式管理、段式管理和段页式管理各有优缺点。页式管理通过固定大小的页框减少了外部碎片&#xff0c;但可能导致内部碎片&#xff1b;段式管理符合程序逻辑&#xff0c;提供了灵活的内存保护&#xff0c;但可能…...

【已解决】关于MyBatis的collection集合中只能取到一条数据的问题

一、问题 在涉及多表查询的时候&#xff0c;使用collection元素来映射集合属性时&#xff0c;出现了只能查询到一条数据的情况&#xff0c;但用sql语句在数据库中查询会有多条记录。 二、原因 如果两表联查&#xff0c;主表和明细表的主键都是id的话&#xff0c;明细表的多条…...

前端的学习-CSS(弹性布局-flex)

一&#xff1a;什么是弹性布局-Flex flex 是 Flexible Box 的缩写&#xff0c;意为"弹性布局"&#xff0c;用来为盒状模型提供最大的灵活性。 语法&#xff1a; .box{display: flex; } .box{display: inline-flex; } 注意&#xff0c;设为 Flex 布局以后&#xff0…...

vue3集成LuckySheet实现导入本地Excel进行在线编辑,以及导出功能

第一步&#xff1a;克隆或者下载下面的代码 git clone https://github.com/dream-num/Luckysheet.git第二步&#xff1a;安装依赖 npm install npm install gulp -g 第三步&#xff1a;运行 npm run dev效果如下图所示 第四步&#xff1a;打包 打包执行成功后&#xff0c;…...

【征求意见】同济大学--城镇给水厂碳排放核算与评价方法

城镇给水厂保障城镇居民正常生活&#xff0c;是社会经济良性发展的重要基础性设施&#xff0c;对于我国双碳战略目标的实现至关重要。 随着城镇化的发展&#xff0c;城镇供水量不断升高&#xff0c;加上 水资源与生态环境问题不断涌现&#xff0c;人们对水的安全和品质的需求日…...

【Python】后台开发返回方法和状态码类的实现

Python 后台开发中&#xff0c;获取返回的类方法&#xff0c;以及状态码类的实现 代码备份 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: 下载得到&#xff1a;TensorRT-10.2.0.19.Linux.x86_64-gnu.cuda-11.8.tar.gz 3: 下载后配置环境变量&#xff0c;上面地址记得改成真实地址。 4: 如果想python使用tensorrt&#xff0c;那么 解压后目录&#xff0c…...

ELK对业务日志进行收集

ELK对业务日志进行收集 下载httpd 进到文件设置收集httpd的文件进行 设置 编辑内容 用于收集日志的内容 将日志的内容发送到实例当中 input {file{path > /etc/httpd/logs/access_logtype > "access"start_position > "beginning"}file{path &g…...

新质生产力

新质生产力”是一个相对较新的概念&#xff0c;指的是在数字化、智能化背景下&#xff0c;依托新技术、新业态、新模式&#xff0c;提升生产力质量和效率的一种生产力形态。它强调的是技术和创新对生产力的提升作用&#xff0c;尤其是在人工智能、大数据、互联网等新兴技术的推…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...