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

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...