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

14 基数排序(桶排序)

文章目录

  • 1 基数排序基本思想
  • 2 基数排序的代码实现
    • 2.1 java
    • 2.2 scala
  • 3 基数排序总结

1 基数排序基本思想

1) 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或 bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用
2) 基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法
3) 基数排序(Radix Sort)是桶排序的扩展
4) 基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。

在这里插入图片描述
在这里插入图片描述

2 基数排序的代码实现

2.1 java

package sort;/*** @author Andy* @email andy.gsq@qq.com* @date 2023/2/17 16:58:44* @desc 基数排序方法*/public class RadixSortForJava {public static void main(String[] args) {int sum = 8;int[] arr = new int[sum];for (int i = 0; i < sum; i++) {arr[i] = (int) (Math.random() * sum); //生成一个[0, sum) 数}System.out.println("排序前:");show(arr);radixSort(arr);System.out.println("排序后:");show(arr);}//基数排序方法public static void radixSort(int[] arr) {// 1.得到数组中最大数的位数int max = arr[0];for (int i = 1; i < arr.length; i++) {if (max < arr[i]) {max = arr[i];}}int maxLength = (max + "").length();//定义一个二维数组,表示 10 个桶, 每个桶就是一个一维数组//说明//1. 二维数组包含 10 个一维数组//2. 为了防止在放入数的时候,数据溢出,则每个一维数组(桶),大小定为 arr.length//3. 名明确,基数排序是使用空间换时间的经典算法int[][] bucket = new int[10][arr.length];//为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数//可以这里理解//比如:bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数int[] bucketElementCounts = new int[10];for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {//(针对每个元素的对应位进行排序处理), 第一次是个位,第二次是十位,第三次是百位...for (int j = 0; j < arr.length; j++) {//取出每个元素对应位的值int digitOfElement = arr[j] / n % 10;bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];bucketElementCounts[digitOfElement] += 1;}//按照这个桶的顺序(一维数组的下标依次取出数据,放入原来数组)int index = 0;//遍历每一桶,并将桶中是数据,放入到原数组for (int k = 0; k < bucketElementCounts.length; k++) {if (bucketElementCounts[k] != 0) {for (int m = 0; m < bucketElementCounts[k]; m++) {arr[index++] = bucket[k][m];}}//第 i+1 轮处理后,需要将每个 bucketElementCounts[k] = 0 !!!!bucketElementCounts[k] = 0;}}}public static void show(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}
}

2.2 scala

package sort/**** @author Andy* @email andy.gsq@qq.com* @date 2023/2/17 17:20:36* @desc TODO**/object RadixSortForScala {def main(args: Array[String]): Unit = {val sum = 8val arr = Array.ofDim[Int](sum)for (i <- 0 until arr.length) {arr(i) = (math.random() * sum).toInt}println("排序前:")show(arr)radixSort(arr)println("排序后:")show(arr)}def radixSort(arr: Array[Int]): Unit = {val maxLenght = arr.max.toString.lengthval buckey = Array.ofDim[Int](10, arr.length)val bucketElementCounts = Array.ofDim[Int](10)for (i <- 0 until maxLenght; n = math.pow(10, i).toInt) {for (j <- 0 until arr.length) {val digitOfElement = arr(j) / n % 10buckey(digitOfElement)(bucketElementCounts(digitOfElement)) = arr(j)bucketElementCounts(digitOfElement) += 1}var index = 0for (n <- 0 until bucketElementCounts.length) {if (bucketElementCounts(n) != 0) {for (m <- 0 until bucketElementCounts(n)) {arr(index) = buckey(n)(m)index += 1}}bucketElementCounts(n) = 0}}}def show(arr: Array[Int]): Unit = {for (i <- arr) {print(i + " ")}println()}
}

3 基数排序总结

1) 基数排序是对传统桶排序的扩展,速度很快.
2) 基数排序是经典的空间换时间的方式,占用内存很大, 当对海量数据排序时,容易造成 OutOfMemoryError 。
3) 基数排序时稳定的。[注:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且 r[i]在 r[j]之前,而在排序后的序列中,r[i]仍在 r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的]
4) 有负数的数组,我们不用基数排序来进行排序, 如果要支持负数,参考: https://code.i-harness.com/zh-CN/q/e98fa9

相关文章:

14 基数排序(桶排序)

文章目录1 基数排序基本思想2 基数排序的代码实现2.1 java2.2 scala3 基数排序总结1 基数排序基本思想 1) 基数排序&#xff08;radix sort&#xff09;属于“分配式排序”&#xff08;distribution sort&#xff09;&#xff0c;又称“桶子法”&#xff08;bucket sort&#…...

汉明距离Java解法

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。 给你两个整数 x 和 y&#xff0c;计算并返回它们之间的汉明距离。 例&#xff1a; 输入&#xff1a;x 1, y 4 输出&#xff1a;2 解释&#xff1a; 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上…...

Netty服务端请求接受过程源码剖析

目标 服务器启动后&#xff0c;客户端进行连接&#xff0c;服务器端此时要接受客户端请求&#xff0c;并且返回给客户端想要的请求&#xff0c;下面我们的目标就是分析Netty 服务器端启动后是怎么接受到客户端请求的。我们的代码依然与上一篇中用同一个demo&#xff0c; 用io.…...

金三银四春招特供|高质量面试攻略

&#x1f530; 全文字数 : 1万5千 &#x1f552; 阅读时长 : 20min &#x1f4cb; 关键词 : 求职规划、面试准备、面试技巧、谈薪职级 &#x1f449; 公众号 : 大摩羯先生 本篇来聊聊一个老生常谈的话题————“面试”。利用近三周工作午休时间整理了这篇洋洋洒洒却饱含真诚…...

搭建Hexo博客-第4章-绑定自定义域名

搭建Hexo博客-第4章-绑定自定义域名 搭建Hexo博客-第4章-绑定自定义域名 搭建Hexo博客-第4章-绑定自定义域名 在这一篇文章中&#xff0c;我将会介绍如何给博客绑定你自己的域名。其实绑定域名本应该很简单的&#xff0c;但我当初在这上走了不少弯路&#xff0c;所以我觉得有…...

lightdb-sql拦截

文章目录LightDB - sql 审核拦截一 简介二 参数2.1 lightdb_sql_mode2.2 lt_firewall.lightdb_business_time三 规则介绍及使用3.1 select_without_where3.1.1 案例3.2 update_without_where/delete_without_where3.2.1 案例3.3 high_risk_ddl3.3.1 案例LightDB - sql 审核拦截…...

二进制中1的个数-剑指Offer-java位运算

一、题目描述编写一个函数&#xff0c;输入是一个无符号整数&#xff08;以二进制串的形式&#xff09;&#xff0c;返回其二进制表达式中数字位数为 1 的个数&#xff08;也被称为 汉明重量).&#xff09;。提示&#xff1a;请注意&#xff0c;在某些语言&#xff08;如 Java&…...

学自动化测试可以用这几个练手项目

练手项目的业务逻辑比较简单&#xff0c;只适合练手&#xff0c;不能代替真实项目。 学习自动化测试最难的是没有合适的项目练习。 测试本身既要讲究科学&#xff0c;又有艺术成分&#xff0c;单单学几个 api 的调用很难应付工作中具体的问题。 你得知道什么场景下需要添加显…...

2023年保健饮品行业分析:市场规模不断攀升,年度销额增长近140%

随着人们健康意识的不断增强&#xff0c;我国保健品市场需求持续增长&#xff0c;同时&#xff0c;保健饮品的市场规模也在不断攀升。 根据鲸参谋电商数据显示&#xff0c;2022年度&#xff0c;京东平台上保健饮品的年度销量超60万件&#xff0c;同比增长了约124%&#xff1b;该…...

2023-02-17 学习记录--TS-邂逅TS(一)

TS-邂逅TS&#xff08;一&#xff09; 不积跬步&#xff0c;无以至千里&#xff1b;不积小流&#xff0c;无以成江海。&#x1f4aa;&#x1f3fb; 一、TypeScript在线编译器 https://www.typescriptlang.org/play/ 二、类型 1、普通类型 number&#xff08;数值型&#xff…...

SpringMVC创建异步回调请求的4种方式

首先要明确一点&#xff0c;同步请求和异步请求对于客户端用户来讲是一样的&#xff0c;都是需客户端等待返回结果。不同之处在于请求到达服务器之后的处理方式&#xff0c;下面用两张图解释一下同步请求和异步请求在服务端处理方式的不同&#xff1a;同步请求异步请求两个流程…...

MySQL(二)表的操作

一、创建表 CREATE TABLE table_name ( field1 datatype, field2 datatype, field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎; 说明&#xff1a; field 表示列名 datatype 表示列的类型 character set 字符集&#xff0c;如…...

SpringCloud - 入门

目录 服务架构演变 单体架构 分布式架构 分布式架构要考虑的问题 微服务 初步认识 案例Demo 服务拆分注意事项 服务拆分示例 服务调用 服务架构演变 单体架构 将业务的所有功能集中在一个项目中开发&#xff0c;打成一个包部署优点&#xff1a; 架构简单部署成本低缺…...

进一步了解C++函数的各种参数以及重载,了解C++部分的内存模型,C++独特的引用方式,巧妙替换指针,初步了解类与对象。满满的知识,希望大家能多多支持

C的编程精华&#xff0c;走过路过千万不要错过啊&#xff01;废话少说&#xff0c;我们直接进入正题&#xff01;&#xff01;&#xff01;&#xff01; 函数高级 C的函数提高 函数默认参数 在C中&#xff0c;函数的形参列表中的形参是可以有默认值的。 语法&#xff1a;返…...

Chapter6:机器人SLAM与自主导航

ROS1{\rm ROS1}ROS1的基础及应用&#xff0c;基于古月的课&#xff0c;各位可以去看&#xff0c;基于hawkbot{\rm hawkbot}hawkbot机器人进行实际操作。 ROS{\rm ROS}ROS版本&#xff1a;ROS1{\rm ROS1}ROS1的Melodic{\rm Melodic}Melodic&#xff1b;实际机器人&#xff1a;Ha…...

Sass的使用要点

Sass 是一个 CSS 预处理器&#xff0c;完全兼容所有版本的 CSS。实际上&#xff0c;Sass 并没有真正为 CSS 语言添加任何新功能。只是在许多情况下可以可以帮助我们减少 CSS 重复的代码&#xff0c;节省开发时间。 一、注释 方式一&#xff1a;双斜线 // 方式二&#xff1a;…...

计算机启动过程,从按下电源按钮到登录界面的详细步骤

1、背景 自接触计算机以来&#xff0c;一直困扰着我一个问题。当我们按下电脑的开机键后&#xff0c;具体发生了哪些过程呢&#xff1f;计算机启动的具体步骤是什么&#xff1f; 计算机启动过程通常分为五个步骤&#xff1a;电源自检、BIOS自检、引导设备选择、引导程序加载和…...

LeetCode 刷题之 BFS 广度优先搜索【Python实现】

1. BFS 算法框架 BFS&#xff1a;用来搜索 最短路径 比较合适&#xff0c;如&#xff1a;求二叉树最小深度、最少步数、最少交换次数&#xff0c;一般与 队列 搭配使用&#xff0c;空间复杂度比 DFS 大很多DFS&#xff1a;适合搜索全部的解&#xff0c;如&#xff1a;寻找最短…...

Hadoop01【尚硅谷】

大数据学习笔记 大数据概念 大数据&#xff1a;指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合&#xff0c;是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。 主要解决&#xff0c;海量数据的存储…...

Echarts 配置横轴竖轴指示线,更换颜色、线型和大小

第018个点击查看专栏目录本示例是描述如何在Echarts上配置横轴竖轴指示线&#xff0c;更换颜色、线型和大小。方法很简单&#xff0c;参考示例源代码。 文章目录示例效果示例源代码&#xff08;共85行&#xff09;相关资料参考专栏介绍示例效果 示例源代码&#xff08;共85行&a…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

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

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

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...