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

Java排序算法之基数排序

基数排序(Radix Sort)是一种线性时间复杂度的排序算法,其时间复杂度为O(d(n+k)),其中d是数字的位数,k是进制数。基数排序是一种非比较排序算法,它按照数位的大小来进行排序。它可以处理正整数、负整数和小数。

基数排序的实现过程如下:

  1. 找到最大数,并确定最大数的位数。

  2. 从个位数开始,把所有数按照该位数进行排序。可以使用计数排序或桶排序。排序后,原数组变成了按照该位数排序后的数组。

  3. 重复第二步,直到最大数的最高位被处理完。

举个例子:

假设有以下六个数字要排序:23,46,12,67,34,89。我们先找到最大数89,确定最大数的位数为2。

第一轮排序按照个位数排序:

个位数桶1桶2桶3桶4桶5桶6桶7桶8桶9
32334466789
212
6

第二轮排序按照十位数排序:

十位数桶1桶2桶3桶4桶5桶6桶7桶8桶9
31223344667
889

最终排序结果为:12,23,34,46,67,89。

Java实现基数排序的核心思想是:将数字按照每个位数分别排序,从低位到高位依次进行排序,最后得到有序序列。

下面是Java实现基数排序的代码:

public class RadixSort {/*** 基数排序* @param arr 待排序数组*/public static void radixSort(int[] arr) {if (arr == null || arr.length == 0) return;int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) max = arr[i]; // 找到最大值}int radix = 10; // 进制数,这里是10进制int exp = 1; // 指数int[] aux = new int[arr.length]; // 临时数组while (max / exp > 0) { // 从个位开始,对每一位进行排序int[] buckets = new int[radix];// 统计每个桶中的记录数for (int i = 0; i < arr.length; i++) {int bucketIndex = (arr[i] / exp) % radix;buckets[bucketIndex]++;}// 将各个桶中的数字个数,转化成各个桶中最后一个数字的索引位置for (int i = 1; i < radix; i++) {buckets[i] += buckets[i - 1];}// 将原数组中的元素放入临时数组中,根据桶中位置排序for (int i = arr.length - 1; i >= 0; i--) {int bucketIndex = (arr[i] / exp) % radix;aux[--buckets[bucketIndex]] = arr[i];}// 将有序的数组写回原数组for (int i = 0; i < arr.length; i++) {arr[i] = aux[i];}exp *= radix;}}public static void main(String[] args) {int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };radixSort(arr);System.out.println(Arrays.toString(arr)); // [2, 24, 45, 66, 75, 90, 170, 802]}
}

相关文章:

Java排序算法之基数排序

基数排序&#xff08;Radix Sort&#xff09;是一种线性时间复杂度的排序算法&#xff0c;其时间复杂度为O(d(nk))&#xff0c;其中d是数字的位数&#xff0c;k是进制数。基数排序是一种非比较排序算法&#xff0c;它按照数位的大小来进行排序。它可以处理正整数、负整数和小数…...

Ubuntu20.0中安装Gradle

下载Gradle到temp文件夹 wget https://services.gradle.org/distributions/gradle-8.3-bin.zip -P /tmp 然后解压文件到/opt/gradle目录 sudo unzip -d /opt/gradle /tmp/gradle-8.3.zip 配置Gradle环境变量 接下来我们会创建一个gradle.sh文件来保存Gradle的环境变量 sudo…...

【Java并发编程六】多线程越界问题

ArrayList()越界错误 import java.util.ArrayList; public class myTest implements Runnable {static ArrayList<Integer> a new ArrayList<>(10);public static void main(String[] args) throws InterruptedException {Thread t1 new Thread(new myTest());T…...

聊聊httpclient的disableConnectionState

序 本文主要研究一下httpclient的disableConnectionState disableConnectionState org/apache/http/impl/client/HttpClientBuilder.java /*** Disables connection state tracking.*/public final HttpClientBuilder disableConnectionState() {connectionStateDisabled t…...

Tomcat web.xml文件中的mime-mapping

在Tomcat安装目录的conf/web.xml文件中&#xff0c;定义了大量的<mime-mapping>元素&#xff0c;例如&#xff1a; 其中<extension>指定了文件的扩展名&#xff0c;<mime-type>指定了mime类型&#xff0c;放在<mime-mapping>元素中&#xff0c;就是将…...

【Java 进阶篇】JQuery 事件绑定:`on` 与 `off` 的奇妙舞曲

在前端开发的舞台上&#xff0c;用户与页面的互动是一场精彩的表演。而 JQuery&#xff0c;作为 JavaScript 的一种封装库&#xff0c;为这场表演提供了更为便捷和优雅的事件绑定方式。其中&#xff0c;on 和 off 两位主角&#xff0c;正是这场奇妙舞曲中的核心演员。在这篇博客…...

模块化Common JS 和 ES Module

目录 历程 1.几个函数&#xff1a;全局变量的污染&#xff0c;模块间没有联系 2.对象&#xff1a;暴露成员&#xff0c;外部可修改 3.立即执行函数&#xff1a;闭包实现模块私有作用域 common JS module和Module 过程 模块依赖&#xff1a;深度优先遍历、父 -> 子 -…...

基于java web个人财务管理系统

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…...

soc估计:DESIGN AND DEVELOPMENT OF SoC ESTIMATION MODEL USING MACHINE LEARNING

这是一篇印度那边学生的毕业论文&#xff0c;唯一要记录的是里面提到了一个特征构造的思想&#xff0c;记录如下&#xff1a; 论文思想&#xff1a; 特征选用速度、电流、电压、温度、平均电压、平均电流、平均速度&#xff0c;模型用cnnlstmlrlr 平均特征计算方式&#xff1a;…...

2、LeetCode之两数相加

给你两个非空的链表&#xff0c;表示两个非负的整数。它们每位数字都是按照逆序的方式存储的&#xff0c;并且每个节点只能存储一位数字。请你将两个数相加&#xff0c;并以相同形式返回一个表示和的链表。你可以假设除了数字0之外&#xff0c;这两个数都不会以0开头。 输入&am…...

redis三种集群方式

redis有三种集群方式&#xff1a;主从复制&#xff0c;哨兵模式和集群。 1.主从复制 主从复制原理&#xff1a; 从服务器连接主服务器&#xff0c;发送SYNC命令&#xff1b; 主服务器接收到SYNC命名后&#xff0c;开始执行BGSAVE命令生成RDB文件并使用缓冲区记录此后执行的所…...

Java --- JVM之垃圾回收相关算法

目录 一、垃圾标记算法 1.1、垃圾标记阶段&#xff1a;对象存活判断 1.2、引用计数算法 1.3、可达性分析算法 1.4、GC Roots 二、对象的finalization机制 2.1、生存还是死亡&#xff1f; 三、查看GC Roots 3.1、使用MAT查看 四、使用JProfiler分析OOM 五、清除阶段算…...

CentOS 7.9 安装 nginx

系统版本 # cat /etc/redhat-release CentOS Linux release 7.9.2009 (Core)搜索nginx相关的软件包 yum search nginx显示已安装的与 “nginx” 相关的软件包 yum list | grep nginx列出可用的 Nginx 软件包 yum list nginx --showduplicates安装 Nginx yum install -y ng…...

Newman

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 一&#xff09;如何安装Newman 1、下载并安装NodeJs 在官网下载NodeJs&#xff1a; Download | Node.js&#xff08;官网的…...

Transformer中WordPiece/BPE等不同编码方式详解以及优缺点

❤️觉得内容不错的话&#xff0c;欢迎点赞收藏加关注&#x1f60a;&#x1f60a;&#x1f60a;&#xff0c;后续会继续输入更多优质内容❤️ &#x1f449;有问题欢迎大家加关注私戳或者评论&#xff08;包括但不限于NLP算法相关&#xff0c;linux学习相关&#xff0c;读研读博…...

Ubuntu20.04安装Beyond Compare 4.4.7

参考链接&#xff1a; 1.Ubuntu20.04 Beyond Compare 4.3.7 安装 2.Ubuntu20.04安装Beyond Compare 4.3.7...

制作含有音频、视频的网页

参考代码如下 <!DOCTYPE html> <html> <head><title>视频音乐网页</title> </head> <body><!-- 视频 --><video width"320" height"240" controls><source src"movie.mp4" type"…...

QPair的介绍及用法

QPair是一个模板类&#xff0c;它存储一对值&#xff08;key&#xff0c;value&#xff09;&#xff0c;可以是不同的数据类型。QPair的用法有以下几个方面&#xff1a; QPair的构造函数有以下几种形式&#xff1a; QPair()&#xff1a;默认构造函数&#xff0c;创建一个空的QP…...

掌握未来技术趋势,Python编程引领人工智能时代

掌握未来技术趋势&#xff0c;Python编程引领人工智能时代 摘要&#xff1a;Python作为一种高级编程语言&#xff0c;在人工智能领域中扮演着越来越重要的角色。本文将通过介绍Python编程的特点、应用场景及发展前景&#xff0c;展望Python未来的发展趋势&#xff0c;并结合代…...

【自留地】后端 - PHP - MySQL - Nginx - Python - Java

PHP ThinkPHP6入门手册 【精选】【汇总】ThinkPHP6入门手册_tp6手册_Rudon滨海渔村的博客-CSDN博客文章浏览阅读5.4k次。安装安装Composer【win】https://getcomposer.org/Composer-Setup.exe【Linux & MacOS】curl -sS https://getcomposer.org/installer | phpmv compo…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...