数组排序简介-基数排序(Radix Sort)
基本思想
将整数按位数切割成不同的数字,然后从低位开始,依次到高位,逐位进行排序,从而达到排序的目的。
算法步骤
基数排序算法可以采用「最低位优先法(Least Significant Digit First)」或者「最高位优先法(Most Significant Digit first)」。最常用的是「最低位优先法」。
下面我们以最低位优先法为例,讲解一下算法步骤。
- 确定排序的最大位数:遍历数组元素,获取数组最大值元素,并取得对应位数。
- 从最低位(个位)开始,到最高位为止,逐位对每一位进行排序:
- 定义一个长度为 10的桶数组 buckets,每个桶分别代表 0∼9 中的 1 个数字。
- 按照每个元素当前位上的数字,将元素放入对应数字的桶中。
- 清空原始数组,然后按照桶的顺序依次取出对应元素,重新加入到原始数组中。
以 [692,924,969,503,871,704,542,436]为例,演示一下基数排序算法的整个步骤。

适用场景
大规模整数排序,固定长度数据排序,稳定性要求高的排序场景,数据分布较为均匀的情况,外部排序场景
排序稳定性
基数排序采用的桶排序是稳定的。基数排序是一种 稳定排序算法。
代码实现(golang)
func getMax(arr []int) int {max := arr[0]for _, v := range arr {if v > max {max = v}}return max
}func radixSort(arr []int) []int {max := getMax(arr)exp := 1for max/exp > 0 {buckets := make([][]int, 10)for _, v := range arr {digit := (v / exp) % 10buckets[digit] = append(buckets[digit], v)}arr = []int{}for _, bucket := range buckets {arr = append(arr, bucket...)}exp *= 10}return arr
}func main() {arr := []int{170, 45, 75, 90, 802, 24, 2, 66}sortedArr := radixSort(arr)fmt.Println(sortedArr)
}
相关文章:
数组排序简介-基数排序(Radix Sort)
基本思想 将整数按位数切割成不同的数字,然后从低位开始,依次到高位,逐位进行排序,从而达到排序的目的。 算法步骤 基数排序算法可以采用「最低位优先法(Least Significant Digit First)」或者「最高位优先…...
进程间通信(命名管道 共享内存)
文章目录 命名管道原理命令创建命名管道函数创建命名管道 共享内存原理shmgetFIOK 代码应用:premsnattch 命名管道 用于两个毫无关系的进程间的通信。 原理 Linux文件的路径是多叉树,故文件的路径是唯一的。 让内核缓冲区不用刷新到磁盘中,…...
Python 网络爬虫教程:从入门到高级的全面指南
Python 网络爬虫教程:从入门到高级的全面指南 引言 在信息爆炸的时代,网络爬虫(Web Scraping)成为了获取数据的重要工具。Python 以其简单易用的特性,成为了网络爬虫开发的首选语言。本文将详细介绍如何使用 Python …...
深度学习:正则化(Regularization)详细解释
正则化(Regularization)详细解释 正则化(Regularization)是机器学习和统计建模领域中用以防止模型过拟合同时增强模型泛化能力的一种技术。通过引入额外的约束或惩罚项到模型的损失函数中,正则化能够有效地限制模型的…...
Freertos学习日志(1)-基础知识
目录 1.什么是Freertos? 2.为什么要学习RTOS? 3.Freertos多任务处理的原理 1.什么是Freertos? RTOS,即(Real Time Operating System 实时操作系统),是一种体积小巧、确定性强的计算机操作系统…...
CentOS9 Stream 支持输入中文
CentOS9 Stream 支持输入中文 方法一:确保 gnome-control-center 和相关组件已更新方法二:手动添加输入法源配置方法三:配置 .xinputrc 文件方法四:检查语言包 进入centos9 stream后,点击右上角电源键,点击…...
基于向量检索的RAG大模型
一、什么是向量 向量是一种有大小和方向的数学对象。它可以表示为从一个点到另一个点的有向线段。例如,二维空间中的向量可以表示为 (𝑥,𝑦) ,表示从原点 (0,0)到点 (𝑥,𝑦)的有向线段。 1.1、文本向量 1…...
【力扣 + 牛客 | SQL题 | 每日5题】牛客SQL热题216,217,223
也在牛客力扣写了一百来题了,个人感觉力扣的SQL题要比牛客的高三档的难度。(普遍来说) 1. 牛客SQL热题216:统计各个部门的工资记录数 1.1 题目: 描述 有一个部门表departments简况如下: dept_nodept_named001Marke…...
Unity humanoid 模型头发动画失效问题
在上一篇【Unity实战笔记】第二十二 提到humanoid 模型会使原先的头发动画失效,如下图所示: 头发摆动的是generic模型和动画,不动的是humanoid模型和动画 一开始我是尝试过在模型Optimize Game objects手动添加缺失的头发骨骼的,奈…...
最全Kafka知识宝典之Kafka的基本使用
一、基本概念 传统上定义是一个分布式的基于发布/订阅模式的消息队列,主要应用在大数据实时处理场景,现在Kafka已经定义为一个分布式流平台,用于数据通道处理,数据流分析,数据集成和关键任务应用 必须了解的四个特性…...
机器学习中的数据可视化:常用库、单变量图与多变量图绘制方法
《博主简介》 小伙伴们好,我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍感谢小伙伴们点赞、关注! 《------往期经典推…...
CodeQL学习笔记(3)-QL语法(模块、变量、表达式、公式和注解)
最近在学习CodeQL,对于CodeQL就不介绍了,目前网上一搜一大把。本系列是学习CodeQL的个人学习笔记,根据个人知识库笔记修改整理而来的,分享出来共同学习。个人觉得QL的语法比较反人类,至少与目前主流的这些OOP语言相比&…...
代码随想录训练营Day11 | 226.翻转二叉树 - 101. 对称二叉树 - 104.二叉树的最大深度 - 111.二叉树的最小深度
226.翻转二叉树 题目链接:226.翻转二叉树思路:遍历二叉树,遍历的时候交换左右节点即可代码: TreeNode* invertTree(TreeNode* root) {reverse(root);return root;}// 迭代法,层序遍历void f2(TreeNode* root) {queue…...
“死鱼眼”,不存在的,一个提词小技巧,拯救的眼神——将内容说给用户,而非读给用户!
视频录制时,死鱼眼问题常见 即便内容再好,眼神死板也会减分 痛点真痛:拍视频时容易紧张 面对镜头,许多人难免紧张 神情僵硬,眼神无光,甚至忘词 这不仅影响表现,还让人难以专注 忘我场景&#x…...
深度学习在复杂系统中的应用
引言 复杂系统由多个相互作用的组成部分构成,这些部分之间的关系往往是非线性的,整体行为难以通过简单的线性组合来预测。这类系统广泛存在于生态学、气象学、经济学和社会科学等多个领域,具有动态演变、自组织、涌现现象以及多尺度与异质性…...
vue3图片懒加载
背景 界面很长,屏幕不能一下装下所有内容,如果以进入首页就把所有内容都加载完的话所需时间较长,会影响用户体验,所以可以当用户浏览到时再去加载。 代码 新建index.ts文件 src下新建directives文件夹,并新建Index…...
总结一些高级的SQL技巧
1. 窗口函数 窗函数允许在查询结果的每一行上进行计算,而不需要将数据分组。这使得我们可以计算累积总和、排名等。 SELECT employee_id,salary,RANK() OVER (ORDER BY salary DESC) AS salary_rank FROM employees;2. 公用表表达式 (CTE) CTE 提供了一种更清晰的…...
无人机飞手考证热,装调检修技术详解
随着无人机技术的飞速发展和广泛应用,无人机飞手考证热正在持续升温。无人机飞手不仅需要掌握飞行技能,还需要具备装调检修技术,以确保无人机的安全、稳定和高效运行。以下是对无人机飞手考证及装调检修技术的详细解析: 一、无人机…...
AI资讯快报(2024.10.27-11.01)
1.<国家超级计算济南中心发布系列大模型> 10月28日,以“人才引领创新 开放赋能发展”为主题的第三届山东人才创新发展大会暨第十三届“海洽会”集中展示大会在山东济南举行。本次大会发布了国家超级计算济南中心大模型,包括“智匠工业大模型、知风…...
范式的简单理解
第二范式 消除非键属性对键的部分依赖 第三范式 消除一个非键属性对另一个非键属性的依赖 表中的每个非键属性都应该依赖于键,整个键,而且只有键(键可能为两个属性) 第四范式 多值依赖于主键...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
