基数排序之代码解析
基数排序是生活中咱们写程序用的比较少的排序,但是这个排序比较巧妙,今天就给大家讲一讲,原理都在代码里面,下面会给一些解释。
import java.util.Arrays;public class Code04_RadixSort {// only for no-negative valuepublic static void radixSort(int[] arr) {if (arr == null || arr.length < 2) {return;}radixSort(arr, 0, arr.length - 1, maxbits(arr));}public static int maxbits(int[] arr) {int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {max = Math.max(max, arr[i]);}int res = 0;while (max != 0) {res++;max /= 10;}return res;}// arr[L..R]排序 , 最大值的十进制位数digitpublic static void radixSort(int[] arr, int L, int R, int digit) {final int radix = 10;int i = 0, j = 0;// 有多少个数准备多少个辅助空间int[] help = new int[R - L + 1];for (int d = 1; d <= digit; d++) {// 有多少位就进出几次// 10个空间// count[0] 当前位(d位)是0的数字有多少个// count[1] 当前位(d位)是(0和1)的数字有多少个// count[2] 当前位(d位)是(0、1和2)的数字有多少个// count[i] 当前位(d位)是(0~i)的数字有多少个int[] count = new int[radix]; // count[0..9]for (i = L; i <= R; i++) {// 103 1 3// 209 1 9j = getDigit(arr[i], d);count[j]++;}for (i = 1; i < radix; i++) {count[i] = count[i] + count[i - 1];}for (i = R; i >= L; i--) {j = getDigit(arr[i], d);help[count[j] - 1] = arr[i];count[j]--;}for (i = L, j = 0; i <= R; i++, j++) {arr[i] = help[j];}}}public static int getDigit(int x, int d) {return ((x / ((int) Math.pow(10, d - 1))) % 10);}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {
// int testTime = 500000;
// int maxSize = 6;
// int maxValue = 100000;
// boolean succeed = true;
// for (int i = 0; i < testTime; i++) {
// int[] arr1 = generateRandomArray(maxSize, maxValue);
// int[] arr2 = copyArray(arr1);
// radixSort(arr1);
// comparator(arr2);
// if (!isEqual(arr1, arr2)) {
// succeed = false;
// printArray(arr1);
// printArray(arr2);
// break;
// }
// }
// System.out.println(succeed ? "Nice!" : "Fucking fucked!");
//
// int[] arr = generateRandomArray(maxSize, maxValue);int[] arr = new int[]{2,1,5,3,7};printArray(arr);radixSort(arr);printArray(arr);}}
上面是基数排序的整段代码,其实最核心的还是下面部分:
public static void radixSort(int[] arr, int L, int R, int digit) {final int radix = 10;int i = 0, j = 0;// 有多少个数准备多少个辅助空间int[] help = new int[R - L + 1];for (int d = 1; d <= digit; d++) {// 有多少位就进出几次// 10个空间// count[0] 当前位(d位)是0的数字有多少个// count[1] 当前位(d位)是(0和1)的数字有多少个// count[2] 当前位(d位)是(0、1和2)的数字有多少个// count[i] 当前位(d位)是(0~i)的数字有多少个int[] count = new int[radix]; // count[0..9]for (i = L; i <= R; i++) {// 103 1 3// 209 1 9j = getDigit(arr[i], d);count[j]++;}for (i = 1; i < radix; i++) {count[i] = count[i] + count[i - 1];}for (i = R; i >= L; i--) {j = getDigit(arr[i], d);help[count[j] - 1] = arr[i];count[j]--;}for (i = L, j = 0; i <= R; i++, j++) {arr[i] = help[j];}}}
for (i = R; i >= L; i--)
: 这是一个循环,从数组中的右端(R
)向左端(L
)遍历。
j = getDigit(arr[i], d)
: 这一行代码用于获取第i
个元素arr[i]
在第d
位上的数字j
。通常,getDigit
函数会根据位数d
来提取数字。例如,如果d
是个位数,那么getDigit
可能会返回arr[i]
的个位数字;如果d
是十位数,那么它可能会返回arr[i]
的十位数字,以此类推。
help[count[j] - 1] = arr[i]
: 这行代码将第i
个元素arr[i]
放入辅助数组help
中的合适位置。count[j]
表示第j
个数字在当前位数d
上的出现次数,通过count[j] - 1
找到j
在help
数组中的合适位置,然后将arr[i]
放入这个位置。
count[j]--
: 在将arr[i]
放入help
数组后,将count[j]
减一,以便下一个相同数字的元素(如果有的话)可以放入help
数组的前一个位置。
上面是整段核心代码的解释,通过这段代码的解释,可以 把整个流程都搞明白了
相关文章:
基数排序之代码解析
基数排序是生活中咱们写程序用的比较少的排序,但是这个排序比较巧妙,今天就给大家讲一讲,原理都在代码里面,下面会给一些解释。 import java.util.Arrays;public class Code04_RadixSort {// only for no-negative valuepublic s…...

使用C语言EasyX 创建动态爱心背景
简介 在计算机图形学的世界中,有很多方法可以使程序的界面更加吸引人。在本篇博客中,我将向大家介绍如何使用 EasyX 图形库在 C 中创建一个动态的爱心背景。这不仅是一个简单的动画效果,它还包括背景的星星、旋转的心形以及一个美观的背景渐…...

springboot redisTemplate.opsForValue().setIfAbsent返回null原理
一、版本 springboot版本:spring-boot-starter-data-redis 2.1.6 redisson版本:redisson-spring-boot-starter 3.11.5 二、场景 Boolean res redisTemplate.opsForValue().setIfAbsent("key","value");以上代码同一时间多次执行…...

Python调用Jumpserver的Api接口增删改查
引言 Jumpserver是一款强大的堡垒机系统,可以有效管理和控制企业内部服务器的访问权限,提高网络安全性。本文将介绍如何使用Python编程语言,结合Jumpserver提供的API接口,实现对跳板机的管理和操作。 1、什么是Jumpserver&#…...
后端入门教程:从零开始学习后端开发
1. 编程基础 首先,作为一名后端开发者,你需要掌握至少一门编程语言。Python是一个很好的选择,因为它易于学习且功能强大。让我们从一个简单的示例开始,在控制台输出 "Hello, World!"。 2. 学习Web基础 了解Web开发基…...

无涯教程-JavaScript - DB函数
描述 DB函数使用固定余额递减法返回指定期间内资产的折旧。 语法 DB (cost, salvage, life, period, [month])争论 Argument描述Required/OptionalCostThe initial cost of the asset.RequiredSalvageThe value at the end of the depreciation (sometimes called the salv…...

2023年财务顾问行业研究报告
第一章 行业概况 1.1 定义及分类 财务顾问(Financial Advisor,FA)也被称为融资顾问,主要为创业公司提供投资和融资的专业服务。他们在创业者和投资者之间扮演着至关重要的中介角色,为双方搭建桥梁,确保投…...
2023SICTF ROUND2 baby_heap
附件:baby_heap libc版本:glibc2.23 思路一:通过house of orange泄露libc地址,然后通过unsorted bin attack将main_arena88地址写入到chunk_ptr(也就是申请出来的堆数组)中,这时候unsorted bi…...

buuctf crypto 【密码学的心声】解题记录
1.打开可以看到一个曲谱 2.看到曲谱中的提示埃塞克码可以想到ascii码,没有八可以联想到八进制,而八进制又对应着三位的二进制,然后写个脚本就好了 oct [111,114,157,166,145,123,145,143,165,162,151,164,171,126,145,162,171,115,165,143,…...

论文阅读 (100):Simple Black-box Adversarial Attacks (2019ICML)
文章目录 1 概述1.1 要点1.2 代码1.3 引用 2 背景2.1 目标与非目标攻击2.2 最小化损失2.3 白盒威胁模型2.4 黑盒威胁模型 3 简单黑盒攻击3.1 算法3.2 Cartesian基3.3 离散余弦基3.4 一般基3.5 学习率 ϵ \epsilon ϵ3.6 预算 1 概述 1.1 要点 题目:简单黑盒对抗攻…...

41 个下载免费 3D 模型的最佳网站
推荐:使用 NSDT场景编辑器 快速搭建3D应用场景 1. Pikbest Pikbest是一个设计资源平台,提供超过3万件创意艺术品。您可以在Pikbest上找到设计模板,演示幻灯片,视频和音乐等。您可以找到不同的3D模型,例如婚礼装饰&…...

SpringMVC之JSR303和拦截器
认识JSR303 JSR303是一项Java标准规范,也叫做Bean Validation规范,提供了一种JavaBean数据验证的规范方式。在SpringMVC中,可以通过引入JSR303相关的依赖,来实现数据的校验。 在使用JSR303进行校验时,需要在需要校验的…...

通过rabbitmq生成延时消息,并生成rabbitmq镜像
通过rabbitmq生成延时消息队列,并生成rabbitmq镜像 整体描述1. 使用场景2. 目前问题3. 前期准备 具体步骤1. 拉取镜像2. 运行镜像3. 安装插件4. 代码支持4.1 config文件4.2 消费监听4.2 消息生产 5. 功能测试 镜像操作1. 镜像制作2. 镜像导入 总结 整体描述 1. 使用…...
结构型模式-外观模式
隐藏系统的复杂性,并向客户端提供了一个客户端可以访问系统的接口。这种类型的设计模式属于结构型模式,它向现有的系统添加一个接口,来隐藏系统的复杂性。 这种模式涉及到一个单一的类,该类提供了客户端请求的简化方法和对现有系…...

vue三个点…运算符时报错 Syntax Error: Unexpected token
出现以下问题报错: 解决: 在项目根目录新建一个名为.babelrc的文件 {"presets": ["stage-2"] }...

C# wpf 实现桌面放大镜
文章目录 前言一、如何实现?1、制作无边框窗口2、Viewbox放大3、截屏显示(1)、截屏(2)、转BitmapSource(3)、显示 4、定时截屏 二、完整代码三、效果预览总结 前言 做桌面截屏功能时需要放大镜…...
Mybatis中的#{}和${}的区别
#{}和${}他们两都是替换参数的作用,但也还是有很大区别的。 目录 一、${} 二、#{} 三、注意点 一、${} 它是直接替换过来,不添加其它的什么。 比如下面的sql语句 select *from user where id${id} 如果id1,那么他替换过来就还是1ÿ…...

选择(使用)数据库
MySQL从小白到总裁完整教程目录:https://blog.csdn.net/weixin_67859959/article/details/129334507?spm1001.2014.3001.5502 语法格式: use 数据库名称;大家应该知道,在对数据库进行操作的时候,要制定数据库的操作对象,也就是说操作哪一个数据库 案列:选择testing数据库 …...

GFS分布式文件系统
1、GlusterFS简介 GlusterFS(GFS)是一个开源的分布式文件系统 由存储服务器、客户端以及NFS/Samba 存储网关(可选,根据需要选择使用)组成。MFS 传统的分布式文件系统大多通过元服务器来存储元数据,元数据…...

虚函数、纯虚函数、多态
一.虚函数 在基类的函数前加上virtual关键字,在派生类中重写该函数,运行时将会根据所指对象的实际类型来调用相应的函数,如果对象类型是派生类,就调用派生类的函数,如果对象类型是基类,就调用基类的函数。 …...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...