当前位置: 首页 > 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; 第四范式 多值依赖于主键...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...