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

基数排序之代码解析

        基数排序是生活中咱们写程序用的比较少的排序,但是这个排序比较巧妙,今天就给大家讲一讲,原理都在代码里面,下面会给一些解释。

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 找到 jhelp 数组中的合适位置,然后将 arr[i] 放入这个位置。

  • count[j]--: 在将 arr[i] 放入 help 数组后,将 count[j] 减一,以便下一个相同数字的元素(如果有的话)可以放入 help 数组的前一个位置。

上面是整段核心代码的解释,通过这段代码的解释,可以 把整个流程都搞明白了 

相关文章:

基数排序之代码解析

基数排序是生活中咱们写程序用的比较少的排序&#xff0c;但是这个排序比较巧妙&#xff0c;今天就给大家讲一讲&#xff0c;原理都在代码里面&#xff0c;下面会给一些解释。 import java.util.Arrays;public class Code04_RadixSort {// only for no-negative valuepublic s…...

使用C语言EasyX 创建动态爱心背景

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

springboot redisTemplate.opsForValue().setIfAbsent返回null原理

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

Python调用Jumpserver的Api接口增删改查

引言 Jumpserver是一款强大的堡垒机系统&#xff0c;可以有效管理和控制企业内部服务器的访问权限&#xff0c;提高网络安全性。本文将介绍如何使用Python编程语言&#xff0c;结合Jumpserver提供的API接口&#xff0c;实现对跳板机的管理和操作。 1、什么是Jumpserver&#…...

后端入门教程:从零开始学习后端开发

1. 编程基础 首先&#xff0c;作为一名后端开发者&#xff0c;你需要掌握至少一门编程语言。Python是一个很好的选择&#xff0c;因为它易于学习且功能强大。让我们从一个简单的示例开始&#xff0c;在控制台输出 "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 定义及分类 财务顾问&#xff08;Financial Advisor&#xff0c;FA&#xff09;也被称为融资顾问&#xff0c;主要为创业公司提供投资和融资的专业服务。他们在创业者和投资者之间扮演着至关重要的中介角色&#xff0c;为双方搭建桥梁&#xff0c;确保投…...

2023SICTF ROUND2 baby_heap

附件&#xff1a;baby_heap libc版本&#xff1a;glibc2.23 思路一&#xff1a;通过house of orange泄露libc地址&#xff0c;然后通过unsorted bin attack将main_arena88地址写入到chunk_ptr&#xff08;也就是申请出来的堆数组&#xff09;中&#xff0c;这时候unsorted bi…...

buuctf crypto 【密码学的心声】解题记录

1.打开可以看到一个曲谱 2.看到曲谱中的提示埃塞克码可以想到ascii码&#xff0c;没有八可以联想到八进制&#xff0c;而八进制又对应着三位的二进制&#xff0c;然后写个脚本就好了 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 要点 题目&#xff1a;简单黑盒对抗攻…...

41 个下载免费 3D 模型的最佳网站

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

SpringMVC之JSR303和拦截器

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

通过rabbitmq生成延时消息,并生成rabbitmq镜像

通过rabbitmq生成延时消息队列&#xff0c;并生成rabbitmq镜像 整体描述1. 使用场景2. 目前问题3. 前期准备 具体步骤1. 拉取镜像2. 运行镜像3. 安装插件4. 代码支持4.1 config文件4.2 消费监听4.2 消息生产 5. 功能测试 镜像操作1. 镜像制作2. 镜像导入 总结 整体描述 1. 使用…...

结构型模式-外观模式

隐藏系统的复杂性&#xff0c;并向客户端提供了一个客户端可以访问系统的接口。这种类型的设计模式属于结构型模式&#xff0c;它向现有的系统添加一个接口&#xff0c;来隐藏系统的复杂性。 这种模式涉及到一个单一的类&#xff0c;该类提供了客户端请求的简化方法和对现有系…...

vue三个点…运算符时报错 Syntax Error: Unexpected token

出现以下问题报错&#xff1a; 解决&#xff1a; 在项目根目录新建一个名为.babelrc的文件 {"presets": ["stage-2"] }...

C# wpf 实现桌面放大镜

文章目录 前言一、如何实现&#xff1f;1、制作无边框窗口2、Viewbox放大3、截屏显示&#xff08;1&#xff09;、截屏&#xff08;2&#xff09;、转BitmapSource&#xff08;3&#xff09;、显示 4、定时截屏 二、完整代码三、效果预览总结 前言 做桌面截屏功能时需要放大镜…...

Mybatis中的#{}和${}的区别

#{}和${}他们两都是替换参数的作用&#xff0c;但也还是有很大区别的。 目录 一、${} 二、#{} 三、注意点 一、${} 它是直接替换过来&#xff0c;不添加其它的什么。 比如下面的sql语句 select *from user where id${id} 如果id1&#xff0c;那么他替换过来就还是1&#xff…...

选择(使用)数据库

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

GFS分布式文件系统

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

虚函数、纯虚函数、多态

一.虚函数 在基类的函数前加上virtual关键字&#xff0c;在派生类中重写该函数&#xff0c;运行时将会根据所指对象的实际类型来调用相应的函数&#xff0c;如果对象类型是派生类&#xff0c;就调用派生类的函数&#xff0c;如果对象类型是基类&#xff0c;就调用基类的函数。 …...

QGIS学习3 - 安装与管理插件

QGIS安装与管理插件主要是使用了菜单栏安装与管理插件这个菜单。 1、通过压缩文件等添加非官方插件 通过压缩文件添加有可能会提示存在安全问题等&#xff0c;直接点是即可。 之后点击install plugins即可完成。安装后导入插件 但是load失败了应该是安装没有成功。只能通过u…...

LeetCode377. 组合总和 Ⅳ

377. 组合总和 Ⅳ 文章目录 [377. 组合总和 Ⅳ](https://leetcode.cn/problems/combination-sum-iv/)一、题目二、题解方法一&#xff1a;完全背包一维数组动态规划思路代码分析 方法二&#xff1a;动态规划二维数组 一、题目 给你一个由 不同 整数组成的数组 nums &#xff0…...

QT将数据写入文件,日志记录

项目场景&#xff1a; 在QT应用中&#xff0c;有时候需要将错误信息记录在log文件里面&#xff0c;或者需要将数据输出到文件中进行比对查看使用。 创建log文件&#xff0c;如果文件存在则不创建 QDir dir(QCoreApplication::applicationDirPath()"/recv_data");if(…...

vue2与vue3的使用区别与组件通信

1. 脚手架创建项目的区别&#xff1a; vue2: vue init webpack “项目名称”vue3: vue create “项目名称” 或者vue3一般与vite结合使用: npm create vitelatest yarn create vite2. template中结构 vue2: template下只有一个元素节点 <template><div><div…...

亚信科技与中国信通院达成全方位、跨领域战略合作

9月11日&#xff0c;亚信科技&#xff08;中国&#xff09;有限公司「简称&#xff1a;亚信科技」与中国信息通信研究院「简称&#xff1a;中国信通院」在京达成战略合作&#xff0c;双方将在关键技术研发、产业链协同等方面展开全方位、跨领域、跨行业深度合作&#xff0c;共促…...

华为Linux系统开发工程师面试

在Linux系统开发工程师的面试中&#xff0c;你可能会遇到以下一些问题&#xff1a; 在同一个网站中&#xff0c;当客户访问的时候&#xff0c;会出现有的页面访问的速度快而有的慢&#xff0c;系统和服务完全正常、网络带宽正常&#xff0c;你如何诊断这个问题&#xff1f;你以…...

Qt利用QTime实现sleep效果分时调用串口下发报文解决串口下发给下位机后产生的粘包问题

Qt利用QTime实现sleep效果分时调用串口下发报文解决串口下发给下位机后产生的粘包问题 文章目录 Qt利用QTime实现sleep效果分时调用串口下发报文解决串口下发给下位机后产生的粘包问题现象解决方法 现象 当有多包数据需要连续下发给下位机时&#xff0c;比如下载数据等&#x…...

人工智能:神经细胞模型到神经网络模型

人工智能领域中的重要流派之一是&#xff1a;从神经细胞模型&#xff08;Neural Cell Model&#xff09;到神经网络模型&#xff08;Neural Network Model&#xff09;。 一、神经细胞模型 第一个人工神经细胞模型是“MP”模型&#xff0c;它是由麦卡洛克、匹茨合作&#xff0…...

Redisson分布式锁实战

实战来源 此问题基于电商 这周遇见这么一个问题&#xff0c;简略的说一下 由MQ发布了两个消息&#xff0c;一个是订单新增&#xff0c;一个是订单状态变更 由于直接付款之后&#xff0c;这两个消息的发布时间不分先后&#xff0c;可能会造成两种情况&#xff0c;1、订单状态变更…...

JavaScript中循环遍历数组、跳出循环和继续循环

循环遍历数组 上个文章我们简单的介绍for循环&#xff0c;接下来&#xff0c;我们使用for循环去读取数据的数据&#xff0c;之前我们写过这样的一个数组&#xff0c;如下&#xff1a; const ITshareArray ["张三","二愣子","2033-1997","…...

wordpress创意主题/关键词如何快速排名

在开发过程中&#xff0c;我们有时候会留下Bug&#xff0c;用户在使用我们的app 的时候&#xff0c;有时会出现闪退&#xff0c;这时候我们能够让用户给我们发送邮件&#xff0c;以让我们开发者更加高速的地位到Bug的所在。以最快的时间解决。同一时候也提高用户体验。在AppDel…...

台湾做的h游戏下载网站/百度推广区域代理

企业管理培训&#xff1a;如何提升中层管理者的执行力&#xff1f;企业中层管理都懂得一个道理“高效执行力是企业做大做强的核心武器&#xff0c;没有好的执行力&#xff0c;再好的决策&#xff0c;也只是一个良好的愿望”&#xff0c;如何提升企业中层管理者的执行力&#xf…...

网站开发人员如何写工作日志/有什么推广的平台

背景七年级数学上册第三章“一元一次方程”中&#xff0c;通过一些实际问题&#xff0c;研究了最基本的方程形式——一元一次方程&#xff0c;对求解一元一次方程采用了“去分母”、“去括号”、“移项”、“合并同类项”、“系数化1”等方法&#xff1b;学生在熟悉这些方法的同…...

西安网站建设招骋/网络推广与优化

情况描述&#xff1a;用一个30行代码的python文件&#xff0c;处理300M的数据&#xff0c;用到的数据结构有&#xff1a;pandas.DataFrame(), list, dict&#xff0c;二重循环&#xff0c;处理完一次写入磁盘。问题&#xff1a;内存占用率97%-99%&#xff0c;大约1.5G内存&…...

如何选择商城网站建设/今天上海重大新闻事件

2019独角兽企业重金招聘Python工程师标准>>> 核心内容&#xff1a; 1、Splinter的简介 2、Splinter的安装 3、检验Splinter是否安装成功 4、Geckodriver驱动的安装 5、Splinter的操作示例 &#xff08;一&#xff09;Splinter的简介 Splinter是一个使用Python开…...

常用网站网址/广州全网推广

作者&#xff1a;杨奇龙 网名“北在南方”&#xff0c;资深 DBA&#xff0c;主要负责数据库架构设计和运维平台开发工作&#xff0c;擅长数据库性能调优、故障诊断。 本文来源&#xff1a;原创投稿 *爱可生开源社区出品&#xff0c;原创内容未经授权不得随意使用&#xff0c;转…...