当前位置: 首页 > 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;尤其是在人工智能、大数据、互联网等新兴技术的推…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

如何理解 IP 数据报中的 TTL?

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