当前位置: 首页 > 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…...

OpenAI 官方API Java版SDK,两行代码即可调用。包含GhatGPT问答接口。

声明&#xff1a;这是一个非官方的社区维护的库。 已经支持OpenAI官方的全部api&#xff0c;有bug欢迎朋友们指出&#xff0c;互相学习。 注意&#xff1a;由于这个接口&#xff1a; https://platform.openai.com/docs/api-reference/files/retrieve-content 免费用户无法使…...

SpringBoot 日志文件

(一)日志文件有什么用&#xff1f;除了发现和定位问题之外&#xff0c;我们还可以通过日志实现以下功能&#xff1a;记录用户登录日志&#xff0c;以便分析用户是正常登录还是恶意破解用户。记录系统的操作日志&#xff0c;以便数据恢复和定位操作 。记录程序的执行时间&#x…...

SQL71 检索供应商名称

描述Vendors表有字段供应商名称&#xff08;vend_name&#xff09;、供应商国家&#xff08;vend_country&#xff09;、供应商州&#xff08;vend_state&#xff09;vend_namevend_countryvend_stateappleUSACAvivoCNAshenzhenhuaweiCNAxian【问题】编写 SQL 语句&#xff0c;…...

02:入门篇 - 漫谈 CTK

作者: 一去、二三里 个人微信号: iwaleon 微信公众号: 高效程序员 十万个为什么 五千个在哪里?七千个怎么办?十万个为什么?。。。生活中,有很多奥秘在等着我们去思考、揭示! 同样地,在使用 CTK 时,很多小伙伴一定也存在诸多疑问: 为什么 CTK Plugin Framework 要借…...

SpringBoot常用注解

SpringBootApplication注解包含如下三个SpringBootConfigurationEnableAutoConfigurationComponentScanSpringBootConfiguration等同于Configuration&#xff0c;是属于spring的一个配置类这里的 Configuration 对我们来说并不陌生&#xff0c;它就是 JavaConfig 形式的 Spring…...

RBAC权限模型

什么是RBAC权限模型&#xff1f; RBAC是基于角色的访问控制&#xff0c;在RBAC中&#xff0c;权限与角色相关联&#xff0c;用户通过成为适当角色的成员而得到这些角色的权限。 1.0级 用户、角色、权限 2.0 权限分级 公司>部门>小组 2.1 权限继承 ps: 这个人是一个小组长…...

【郭东白架构课 模块一:生存法则】07|法则三:架构师如何找到自己的商业模式?

你好&#xff0c;我是郭东白&#xff0c;今天我们来聊聊架构活动中对商业价值的考量。 今天我们要讲的是架构师的第三个生存法则&#xff1a;作为一个架构师&#xff0c;必须要在有限的资源下最大化架构活动所带来的商业价值。对于任何一个架构活动而言&#xff0c;架构师的可…...

STM32 - 看门狗

独立看门狗 IWDG专业时钟LSI 低功耗仍可以运行对定时的控制比较松喂狗这些时间是按照40kHz时钟给出。实际上&#xff0c;MCU内部的RC频率会在30kHz到60kHz之间变化。此外&#xff0c;即使RC振荡器的频率是精确的&#xff0c;确切的时序仍然依赖于APB接口时钟与RC振荡器时钟之间…...

Redis集群搭建

一、哨兵模式 在 redis3.0之前&#xff0c;redis使用的哨兵架构&#xff0c;它借助 sentinel 工具来监控 master 节点的状态&#xff1b;如果 master 节点异常&#xff0c;则会做主从切换&#xff0c;将一台 slave 作为 master。 哨兵模式的缺点&#xff1a; &#xff08;1&…...

车载基础软件——AUTOSAR AP典型应用案例

我是穿拖鞋的汉子&#xff0c;魔都中一位坚持长期主义的工程师&#xff01; 最近不知道为何特别喜欢苏轼的一首词&#xff1a; 缺月挂疏桐&#xff0c;漏断人初静。谁见幽人独往来&#xff0c;缥缈孤鸿影。 惊起却回头&#xff0c;有恨无人省。拣尽寒枝不肯栖&#xff0c;寂寞…...

那个做头像的网站好/网络公司网络推广服务

两三年过去了&#xff0c;中间考研&#xff0c;毕业等事宜&#xff0c;一直没有再动过博客。 原本自己的文笔和表达能力就有限&#xff0c;中间一直不断学习新东西&#xff0c;更觉得没有精力去经营博客。 看到很多人能写出高质量博客深感羡慕&#xff0c;自己也是一枚菜鸡&…...

城乡建设委员会网站/站长工具seo词语排名

广州疯狂软件学院拥有三大课程体系包括&#xff1a;java课程&#xff0c;android课程&#xff0c;ios课程&#xff0c;疯狂软件年终钜惠&#xff0c;报名java就业班&#xff0c;免费赠送基础班&#xff0c;名额有限&#xff0c;本月火热报名中&#xff0c;欢迎有志之士电话或者…...

网页站点设计/网站模板套用教程

前言 1、锁机制之所以存在是因为并发问题导致的资源竞争&#xff0c;为了确保操作的有效性和完整性&#xff0c;可以通过锁机制将并发状态转换成串行状态。作为锁机制中的一种&#xff0c;PHP 的文件锁也是为了应对资源竞争。假设一个应用场景&#xff0c;在存在较大并发的情况…...

俄文企业网站建设/整合营销传播名词解释

1、实现效果&#xff1a; 案例描述&#xff1a;当用户单击不同的导航时&#xff0c;与其对应的内容回相应的呈现。 案例要求&#xff1a;使用jquery制作实现tab选项卡单击切换效果。 2、实现思路&#xff1a; &#xff08;1&#xff09;divcss布局&#xff0c;制作选项卡和对…...

广州网站建设o2o/新东方英语培训机构官网

说到文件大小&#xff0c;刚好常有人问我说MySQL是否有单个表的大小限制&#xff1f;限制多大呢&#xff1f;这里做一个简单的介绍吧。 在老版本的MySQL 3.22中&#xff0c;MySQL的单表限大小为4GB&#xff0c;当时的MySQL的存储引擎还是ISAM存储引擎。但是&#xff0c;当出现…...

什么网站可以做平面赚钱/淘宝美工培训推荐

源码包安装和apt-get/yum的区别 安装前的区别&#xff1a;概念上的区别 rpm和dpkg包是经过编译过的包&#xff0c;并且其安装位置由厂商说了算&#xff0c;厂商觉得安装在哪里合适&#xff0c;就会装在哪里&#xff0c;而源码包则是没有经过编译的文件&#xff0c;大部分由c语言…...