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

【C/C++ 06】基数排序

基数排序是桶排序的一种,算法思路为:

  1. 利用队列进行数据收发
  2. 创建一个队列数组,数组大小为10,每个元素都是一个队列,存储取模为1~9的数
  3. 从低位到高位进行数据收发,完成排序
  4. 适用于数据位不高的情况(若不知道数据集的最大位数,则只能往大了猜,降低效率)

基数排序是不稳定排序算法,时间复杂度为O(K*n),K为数据最大位数,也可表示为O(n)

虽然基数排序有着非常优秀的效率,甚至比快排还快,但是由于算法受限于数据的位数,因此并不常见。

代码示例,假设测试数据数组元素最大位数为3:

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
#include <queue>
using namespace std;// 数据最大位数
#define K 3		// 取模的类别数(桶数、基数)
#define RADIX 10// 桶
queue<int> _q[RADIX];// 获取val值对应桶的位置,即哈希映射
int GetPos(int a, int k)
{int pos = a % RADIX;while (k--){a /= RADIX;pos = a % RADIX;}return pos;
} // 分发数据,将数组数据按模分发到哈希桶上
void Distribute(int* arr, int left, int right, int k)
{for (int i = left; i < right; ++i){int pos = GetPos(arr[i], k);_q[pos].push(arr[i]);}
} // 收集数据,根据队列的特性从哈希桶上收集数据,存入数组
void Collect(int* arr)
{int pos = 0;for (int i = 0; i < RADIX; ++i){while (!_q[i].empty()){arr[pos++] = _q[i].front();_q[i].pop();}}
} void RadixSort(int* arr, int n)
{int k = 0;while (k < K){Distribute(arr, 0, n, k++);Collect(arr);}
} /*----------测试模块---------- */// 打印数组
void PrintArr(int* arr, int n)
{for (int i = 0; i < n; ++i){printf("%4d", arr[i]);} cout << endl;
} void TestRadixSort()
{cout << "基数排序:";int arr[20] = {112, 23, 5, 17, 129, 0, 211, 4, 61, 8,511, 51, 25, 10, 210, 111, 3, 5, 18, 6};RadixSort(arr, 20);PrintArr(arr, 20);
} int main()
{TestRadixSort();return 0;
}

运行结果:

相关文章:

【C/C++ 06】基数排序

基数排序是桶排序的一种&#xff0c;算法思路为&#xff1a; 利用队列进行数据收发创建一个队列数组&#xff0c;数组大小为10&#xff0c;每个元素都是一个队列&#xff0c;存储取模为1~9的数从低位到高位进行数据收发&#xff0c;完成排序适用于数据位不高的情况&#xff08…...

Flume1.9基础学习

文章目录 一、Flume 入门概述1、概述2、Flume 基础架构2.1 Agent2.2 Source2.3 Sink2.4 Channel2.5 Event 3、Flume 安装部署3.1 安装地址3.2 安装部署 二、Flume 入门案例1、监控端口数据官方案例1.1 概述1.2 实现步骤 2、实时监控单个追加文件2.1 概述2.2 实现步骤 3、实时监…...

ThinkPHP6的助手函数汇总

原文地址 abort(): 抛出 HTTP 异常 1. /** 2. * 抛出 HTTP 异常 3. * param integer|Response $code 状态码 或者 Response 对象实例 4. * param string $message 错误信息 5. * param array $header 参数 6. */ 7. abort($code, string…...

·备忘录模式

备忘录模式 备忘录模式 备忘录模式 介绍&#xff1a;在不破坏封装的前提下&#xff0c;捕获一个对象的内部状态&#xff0c;并在该对象之外保存这个状态&#xff0c;这样可以在以后将对象恢复到原先的状态。 实现&#xff1a;备忘录类&#xff0c;有一个私有状态属性&#xf…...

docker-学习-2

docker学习第二天 docker学习第二天1.docker和虚拟机的区别2.docker的底层隔离机制2.1 Namespaces(命名空间)2.1.1 什么是命名空间 2.2 Cgroups2.3 Union file systems2.4 Container format2.5 docker在底层如何做隔离的&#xff0c;如何进行资源限制的&#xff1f; 3. docker命…...

树--二叉树(C语言纯手凹)

目录 目录 1.什么是树&#xff1f;&#xff08;不深入&#xff0c;仅做了解&#xff09; 2.树的表示方式 2.1孩子兄弟表示法&#xff08;左孩子右兄弟&#xff09; 2.2孩子表示法 2.3双亲表示法 3.什么是二叉树 4.二叉树分类 4.1满二叉树 4.2完全二叉树 4.3二叉搜索树…...

TypeScript(七) 函数

1. TypeScript 函数 1.1. 函数的定义 函数就是包裹在花括号中的代码块&#xff0c;前面使用关键字function。 语法&#xff1a; // An highlighted block function function_name() {// 执行代码 }实例&#xff1a; function test() { // 函数定义console.log("我就是…...

学fpga和还是嵌入式?

具体要选哪个&#xff0c;更多还是看个人喜好还有基础知识结构。 我们先来明白下两者区别在哪&#xff1f; 1、嵌入式&#xff1a;分两部分&#xff0c;第一是嵌入式软件开发&#xff0c;主要与嵌入式操作系统、应用软件等有关。第二是嵌入式硬件开发&#xff0c;需要掌握硬件…...

Day01-变量和数据类型课后练习-参考答案

文章目录 1、输出你最想说的一句话&#xff01;2、定义所有基本数据类型的变量和字符串变量3、用合适类型的变量存储个人信息并输出4、定义圆周率PI5、简答题 1、输出你最想说的一句话&#xff01; 编写步骤&#xff1a; 定义类 Homework1&#xff0c;例如&#xff1a;Homewo…...

Docker 数据管理、容器互联、网络与资源控制

一、docker数据管理 管理 Docker 容器中数据主要有两种方式&#xff1a;数据卷(Data volumes)和数据卷容器(Datavolumes containers)。 1、数据卷 数据卷是一个供容器使用的特殊目录&#xff0c;位于容器中。可将宿主机的目录挂载到数据卷上&#xff0c;对数据卷的修改操作立…...

密码加密——MD5与BCryptPasswordEncoder

目录 一、问题 二、密码加密 1、MD5密码加密 2、BCryptPasswordEncoder加密&#xff08;推荐&#xff09; 2.1 特点 2.2 使用步骤 一、问题 在数据库表中的密码都是明文存储的&#xff0c;安全性太低 需求&#xff1a; 将密码加密后存储&#xff0c;提高安全性 二、密码加密…...

利用外卖系统源码构建高效的在线订餐平台

在当今数字化时代&#xff0c;外卖服务已成为人们日常生活中不可或缺的一部分。为了满足用户需求&#xff0c;许多创业者和企业都希望搭建自己的在线订餐平台。利用现有的外卖系统源码&#xff0c;可以快速构建一个高效、安全的在线订餐平台。本文将介绍如何利用外卖系统源码来…...

数据分析数据 -(用数据讲故事)

书中有一句话我很喜欢- 献给大家 一个完美的设计&#xff0c;不是因为它没有多余的东西可以添加&#xff0c;而是它没有多余的部分可以删减 首先看几个对比的图形分析 处理工单和新增工单的随月份的变化趋势 这个图形的缺点就是 1: 月份对齐的情况 2&#xff1a;使用条形图需…...

如何运用5W2H分析法分析自己适合哪种办公室

随着时代的发展&#xff0c;办公室已经不再是传统的四壁之内&#xff0c;而是多种多样的形态&#xff0c;涵盖了开放式办公区、远程办公、共享办公空间等多种选择。对于刚刚创业的企业来说&#xff0c;选择一个适合自己发展的办公室至关重要。在这个过程中&#xff0c;运用5W2H…...

为什么考虑电子采购而非传统采购?

采购是重要的业务职能之一&#xff0c;为实现无缝运营而大规模采购商品或服务的行为。考虑到数字化转型带来的影响&#xff0c;决策者对于应维持传统采购还是转向电子采购或多或少会有困惑。 通过本文&#xff0c;你将更了解电子采购和传统采购&#xff0c;从而为业务连续性采…...

【git】git update-index --assume-unchanged(不改动.gitignore实现忽略文件)

文章目录 原因分析&#xff1a;添加忽略文件(取消跟踪)的命令&#xff1a;取消忽略文件(恢复跟踪)的命令&#xff1a;查看已经添加了忽略文件(取消跟踪)的命令&#xff1a; 原因分析&#xff1a; 已经维护的项目&#xff0c;文件已经被追踪&#xff0c;gitignore文件不方便修…...

科普类——无压缩图像传输带宽的计算(七)

无压缩图像传输带宽的计算 问题计算 问题 要计算1080p&#xff08;1920x1080&#xff09;分辨率的彩色图像在30帧每秒&#xff08;fps&#xff09;下的带宽需求&#xff0c;我们需要考虑图像的颜色深度&#xff08;位深&#xff09;和压缩情况。假设我们使用的是无压缩的RGB图…...

云原生周刊:K8s 1.26 到 1.29 版本的更新 | 2024.1.29

开源项目推荐 Skaffold Skaffold 是一个命令行工具&#xff0c;有助于 Kubernetes 应用程序的持续开发。您可以在本地迭代应用程序源代码&#xff0c;然后部署到本地或远程 Kubernetes 集群。Skaffold 处理构建、推送和部署应用程序的工作流程。它还提供构建块并描述 CI/CD 流…...

手机壳也能散热了?

作为一个玩了6年的王者荣耀玩家&#xff0c;手机发热真的很影响游戏体验&#xff01;&#xff01;游戏掉帧&#xff0c;性能下降很恼人&#xff0c;试过好几个散热工具&#xff0c;实际效果都不太好&#xff5e; 自从入了Mate 60之后&#xff0c;看着这款微泵液冷壳毫无犹豫第…...

《微信小程序开发从入门到实战》学习九十七

7.3 表单组件 7.3.1 picke-view与picker-view-column组件 一个picker-view-column代表 一个滚动选择器子项&#xff0c;一个picker-view组件可以包含多个picker-view-column组件&#xff0c;这样可以一次性选择多项内容如年、月、日等。 picker-view-column组件中需包含多个…...

【FastAPI】 + SQLAlchemy 异步 ORM 实现完整 CRUD 操作

&#x1f680;从零实战&#xff1a;FastAPI SQLAlchemy 异步 ORM 实现完整 CRUD 操作&#xff08;附完整代码&#xff09; 一、为什么要学「FastAPI SQLAlchemy 异步 ORM」&#xff1f; 在现代 Web 服务中&#xff0c;数据库是核心组件。然而&#xff0c;传统同步操作&#x…...

旋转ReDet目标检测环境配置、旋转ReDet目标检测模型代跑训练、旋转ReDet目标检测模型改进创新旋转ReDet目标检测环境配置:Windows、Ubuntu、Centos、Macos等系统

旋转ReDet目标检测环境配置、 旋转ReDet目标检测模型代跑训练、 旋转ReDet目标检测模型改进创新 旋转ReDet目标检测环境配置&#xff1a;Windows、Ubuntu、Centos、Macos等系统环境&#xff0c;如果电脑拥有显卡&#xff0c;可配置GPU版本的ReDet环境。 旋转ReDet目标检测模型代…...

Dual-Loop Adaptive AI System Whitepaper(DLAAS)双环自适应AI系统正式命名白皮书

Dual-Loop Adaptive AI System Whitepaper&#xff08;DLAAS&#xff09;双环自适应AI系统—— 基于六元结构&#xff08;TSPR-WEB-LLM-HIC-A-F&#xff09;的生成式AI决策操作系统版权与所有权声明本技术系统的全部知识产权归以下主体独家所有&#xff1a;拓世网络技术开发室&…...

模电实战-比较器正反馈接法的窗口电压设计

1. 比较器正反馈接法的核心价值 我第一次接触比较器正反馈接法是在设计工业传感器信号调理电路时。当时遇到一个头疼的问题&#xff1a;环境噪声导致比较器在临界电压附近频繁误触发&#xff0c;整个系统像得了"癫痫"一样不停抖动。直到尝试了正反馈接法&#xff0c;…...

如何用ControlNet-Union-SDXL-1.0实现多条件图像生成?解锁12种创意控制方案

如何用ControlNet-Union-SDXL-1.0实现多条件图像生成&#xff1f;解锁12种创意控制方案 【免费下载链接】controlnet-union-sdxl-1.0 项目地址: https://ai.gitcode.com/hf_mirrors/xinsir/controlnet-union-sdxl-1.0 ControlNet-Union-SDXL-1.0是一款革命性的多条件控…...

2026届学术党必备的AI论文网站横评

Ai论文网站排名&#xff08;开题报告、文献综述、降aigc率、降重综合对比&#xff09; TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 在人工智能助力写作越发普遍的情形下&#xff0c;文本里残留的机械迹象常常致使可信度跟亲和…...

告别云端依赖:用Docker-Compose搭建私有化Jitsi-Meet,并打包成离线安装包

私有化视频会议解决方案&#xff1a;基于Docker-Compose的Jitsi-Meet离线部署全指南 想象一下&#xff0c;你正在为一个跨国企业部署内部视频会议系统&#xff0c;但客户要求完全私有化部署&#xff0c;且服务器位于无外网连接的隔离环境。这种场景下&#xff0c;传统的云服务依…...

《Qt/UI美化实战课程》| 第五章 自定义仪表盘(美观/高度定制/自适应大小)| 9. 实现仪表盘(1) 新建项目、界面布局

1. 从零搭建Qt仪表盘项目框架 第一次接触Qt自定义控件开发时&#xff0c;我被仪表盘这种既美观又实用的组件深深吸引。记得当时为了做一个工业监控项目&#xff0c;需要展示温度、压力等实时数据&#xff0c;传统的进度条和数字显示实在太枯燥。下面我就带大家从最基础的项目搭…...

Keil5避坑大全:如何解决中文路径、红叉问题和动态语法检查的误区

Keil5开发实战&#xff1a;彻底解决中文路径、红叉与语法检查三大难题 在嵌入式开发领域&#xff0c;Keil MDK作为ARM处理器的主流开发环境&#xff0c;其稳定性和专业性备受开发者信赖。但即使是这样一个成熟的工具链&#xff0c;在实际使用中仍会遇到几个高频痛点&#xff1a…...

Pandoc 格式转换引擎:2025年3大突破性更新

Pandoc 格式转换引擎&#xff1a;2025年3大突破性更新 【免费下载链接】pandoc Universal markup converter 项目地址: https://gitcode.com/gh_mirrors/pa/pandoc 在数字化文档处理领域&#xff0c;格式转换的痛点长期困扰着专业人士。医疗行业报告显示&#xff0c;67.…...