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

数组排序简介-基数排序(Radix Sort)

基本思想

        将整数按位数切割成不同的数字,然后从低位开始,依次到高位,逐位进行排序,从而达到排序的目的。

算法步骤

        基数排序算法可以采用「最低位优先法(Least Significant Digit First)」或者「最高位优先法(Most Significant Digit first)」。最常用的是「最低位优先法」。

   下面我们以最低位优先法为例,讲解一下算法步骤。

  1. 确定排序的最大位数:遍历数组元素,获取数组最大值元素,并取得对应位数。
  2. 从最低位(个位)开始,到最高位为止,逐位对每一位进行排序
    1. 定义一个长度为 10的桶数组 buckets,每个桶分别代表 0∼9 中的 1 个数字。
    2. 按照每个元素当前位上的数字,将元素放入对应数字的桶中。
    3. 清空原始数组,然后按照桶的顺序依次取出对应元素,重新加入到原始数组中。

以 [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文件的路径是多叉树,故文件的路径是唯一的。 让内核缓冲区不用刷新到磁盘中&#xff0c…...

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日&#xff0c;以“人才引领创新 开放赋能发展”为主题的第三届山东人才创新发展大会暨第十三届“海洽会”集中展示大会在山东济南举行。本次大会发布了国家超级计算济南中心大模型&#xff0c;包括“智匠工业大模型、知风…...

范式的简单理解

第二范式 消除非键属性对键的部分依赖 第三范式 消除一个非键属性对另一个非键属性的依赖 表中的每个非键属性都应该依赖于键&#xff0c;整个键&#xff0c;而且只有键&#xff08;键可能为两个属性&#xff09; 第四范式 多值依赖于主键...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...

react-pdf(pdfjs-dist)如何兼容老浏览器(chrome 49)

之前都是使用react-pdf来渲染pdf文件&#xff0c;这次有个需求是要兼容xp环境&#xff0c;xp上chrome最高支持到49&#xff0c;虽然说iframe或者embed都可以实现预览pdf&#xff0c;但为了后续的定制化需求&#xff0c;还是需要使用js库来渲染。 chrome 49测试环境 能用的测试…...

【向量库】Weaviate概述与架构解析

文章目录 一、什么是weaviate二、High-Level Architecture1. Core Components2. Storage Layer3. 组件交互流程 三、核心组件1. API Layer2. Schema Management3. Vector Indexing3.1. 查询原理3.2. 左侧&#xff1a;Search Process&#xff08;搜索流程&#xff09;3.3. 右侧&…...

分布式光纤声振传感技术原理与瑞利散射机制解析

分布式光纤传感技术&#xff08;Distributed Fiber Optic Sensing&#xff0c;简称DFOS&#xff09;作为近年来迅速发展的新型感知手段&#xff0c;已广泛应用于边界安防、油气管道监测、结构健康诊断、地震探测等领域。其子类技术——分布式光纤声振传感&#xff08;Distribut…...