Java代码实现基数排序算法(附带源码)
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
1. 基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法:
这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
- 基数排序:根据键值的每位数字来分配桶;
- 计数排序:每个桶只存储单一键值;
- 桶排序:每个桶存储一定范围的数值;
2. LSD 基数排序动图演示

代码实现
Java
/*** 基数排序* 考虑负数的情况还可以参考: https://www.erdangjiade.com/js*/
public class RadixSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝,不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);int maxDigit = getMaxDigit(arr);return radixSort(arr, maxDigit);}/*** 获取最高位数*/private int getMaxDigit(int[] arr) {int maxValue = getMaxValue(arr);return getNumLenght(maxValue);}private int getMaxValue(int[] arr) {int maxValue = arr[0];for (int value : arr) {if (maxValue < value) {maxValue = value;}}return maxValue;}protected int getNumLenght(long num) {if (num == 0) {return 1;}int lenght = 0;for (long temp = num; temp != 0; temp /= 10) {lenght++;}return lenght;}private int[] radixSort(int[] arr, int maxDigit) {int mod = 10;int dev = 1;for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {// 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)int[][] counter = new int[mod * 2][0];for (int j = 0; j < arr.length; j++) {int bucket = ((arr[j] % mod) / dev) + mod;counter[bucket] = arrayAppend(counter[bucket], arr[j]);}int pos = 0;for (int[] bucket : counter) {for (int value : bucket) {arr[pos++] = value;}}}return arr;}/*** 自动扩容,并保存数据** @param arr* @param value*/private int[] arrayAppend(int[] arr, int value) {arr = Arrays.copyOf(arr, arr.length + 1);arr[arr.length - 1] = value;return arr;}
}
希望你也学会了,更多编程源码模板请来二当家的素材网:https://www.erdangjiade.com
相关文章:
Java代码实现基数排序算法(附带源码)
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。 1. 基数排序…...
基于python+django,我开发了一款药店信息管理系统
功能介绍 平台采用B/S结构,后端采用主流的Python语言进行开发,前端采用主流的Vue.js进行开发。 功能包括:药品管理、分类管理、顾客管理、用户管理、日志管理、系统信息模块。 代码结构 server目录是后端代码web目录是前端代码 部署运行…...
VSCODE使用ssh远程连接时启动服务器失败问题
错误情况 ping服务器的ip可通并且使用terminal可以ssh连接到远程服务器。但使用vscode的remote-ssh时,在「输出」栏出现了一直报 Waiting for server log… 的情况! 解决方法一 重置服务器设置,包括以下手段: 1.清理服务器端的…...
easyexcle 导出csv
导入jar <dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>3.3.3</version></dependency>代码 private static List<List<String>> head() {List<List<String>&g…...
Ubuntu22.04 gnome-builder gnome C 应用程序习练笔记(一)
一、序言 gnome-builder构建器是gnome程序开发的集成环境,支持主力语言C, C, Vala, jscript, python等,界面以最新的 gtk 4.12 为主力,将其下版本的gtk直接压入了depreciated,但gtk4.12与普遍使用的gtk3有很大区别,原…...
ESP32QRCodeReader库使用,ESP32-CAM识别二维码并向自写接口发出请求确认身份。
#include <Arduino.h> #include <WiFi.h> #include <HTTPClient.h> #include <ESP32QRCodeReader.h>#define WIFI_SSID "username" #define WIFI_PASSWORD "password" // 连接电脑主机的IP地址的8088端口 #define WEBHOOK_URL &qu…...
什么是网络渗透,应当如何防护?
什么是网络渗透 网络渗透是攻击者常用的一种攻击手段,也是一种综合的高级攻击技术,同时网络渗透也是安全工作者所研究的一个课题,在他们口中通常被称为"渗透测试(Penetration Test)"。无论是网络渗透(Network Penetration)还是渗透…...
掌握C++中的动态数据:深入解析list的力量与灵活性
1. 引言 简介std::list和其在C中的角色 std::list是C标准模板库(STL)中提供的一个容器类,实现了双向链表的数据结构。与数组或向量等基于连续内存的容器不同,std::list允许非连续的内存分配,使得元素的插入和删除操作…...
天地伟业接入视频汇聚/云存储平台EasyCVR详细步骤
安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快,可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等,以及支持厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…...
Vue源码系列讲解——虚拟DOM篇【二】(Vue中的DOM-Diff)
目录 1. 前言 2. patch 3. 创建节点 4. 删除节点 5. 更新节点 6. 总结 1. 前言 在上一篇文章介绍VNode的时候我们说了,VNode最大的用途就是在数据变化前后生成真实DOM对应的虚拟DOM节点,然后就可以对比新旧两份VNode,找出差异所在&…...
基于AST实现一键自动提取替换国际化文案
背景:在调研 formatjs/cli 使用(使用 formatjs/cli 进行国际化文案自动提取 )过程中,发现有以下需求formatjs/cli 无法满足: id 需要一定的语义化; defaultMessage和Id不能直接hash转换; 需要…...
嵌入式硬件工程师与嵌入式软件工程师
嵌入式硬件工程师与嵌入式软件工程师 纯硬件设备与嵌入式设备 纯硬件设备是指内部不包含微处理器,无需烧写软件就能够运行的电子设备。如天线、老式收音机、老式电视机、老式洗衣机等。这类设备通常功能简单,易于操作,用户通常只需要打开电…...
【华为云】云上两地三中心实践实操
写在前面 应用上云之后,如何进行数据可靠性以及业务连续性的保障是非常关键的,通过华为云云上两地三中心方案了解相关方案认证地址:https://connect.huaweicloud.com/courses/learn/course-v1:HuaweiXCBUCNXI057Self-paced/about当前内容为华…...
Linux大集合
Linux Linux是什么? Linux是一套免费使用和自由传播的类Unix操作系统,是一个基于POSIX和UNIX的多用户、多任务、 支持多线程和多CPU的操作系统。它能运行主要的UNIX工具软件、应用程序和网络协议。它支持32位和 64位硬件。 Linux内核 是一个Linux系统…...
深入解析 Spring 事务机制
当构建复杂的企业级应用程序时,数据一致性和可靠性是至关重要的。Spring 框架提供了强大而灵活的事务管理机制,成为开发者处理事务的首选工具。本文将深入探讨 Spring 事务的使用和原理,为大家提供全面的了解和实际应用的指导。 本文概览 首…...
第9章 安全漏洞、威胁和对策(9.11-9.16)
9.11 专用设备 专用设备王国疆域辽阔,而且仍在不断扩张。 专用设备是指为某一特定目的而设计,供某一特定类型机构使用或执行某一特定功能的任何设备。 它们可被看作DCS、物联网、智能设备、端点设备或边缘计算系统的一个类型。 医疗设备、智能汽车、…...
Mysql-数据库压力测试
安装软件 官方软件 安装插件提供了更多的监听器选项 数据库驱动 数据库测试 配置 这里以一个简单的案例进行,进行连接池为10,20,30的梯度压测: select * from tb_order_item where id 1410932957404114945;新建一个线程组 新增一个连接池配置 新建一…...
CI/CD总结
bitbucket deployment: Bitbucket Cloud resources | Bitbucket Cloud | Atlassian Support Jenkins:...
【CSS】margin塌陷和margin合并及其解决方案
【CSS】margin塌陷和margin合并及其解决方案 一、解决margin塌陷的问题二、避免外边距margin重叠(margin合并) 一、解决margin塌陷的问题 问题:当父元素包裹着一个子元素且父元素没有边框的时候,当给子元素设置margin-top:100px&…...
Python并发
Python是运行在解释器中的语言,查找资料知道,python中有一个全局锁(GIL),在使用多线程(Thread)的情况下,不能发挥多核的优势。而使用多进程(Multiprocess),则可以发挥多核的优势真正地提高效率。…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
Vue3 PC端 UI组件库我更推荐Naive UI
一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用,前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率,还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库(Naive UI、Element …...
