【C/C++ 06】基数排序
基数排序是桶排序的一种,算法思路为:
- 利用队列进行数据收发
- 创建一个队列数组,数组大小为10,每个元素都是一个队列,存储取模为1~9的数
- 从低位到高位进行数据收发,完成排序
- 适用于数据位不高的情况(若不知道数据集的最大位数,则只能往大了猜,降低效率)
基数排序是不稳定排序算法,时间复杂度为,K为数据最大位数,也可表示为
。
虽然基数排序有着非常优秀的效率,甚至比快排还快,但是由于算法受限于数据的位数,因此并不常见。
代码示例,假设测试数据数组元素最大位数为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】基数排序
基数排序是桶排序的一种,算法思路为: 利用队列进行数据收发创建一个队列数组,数组大小为10,每个元素都是一个队列,存储取模为1~9的数从低位到高位进行数据收发,完成排序适用于数据位不高的情况(…...
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…...
·备忘录模式
备忘录模式 备忘录模式 备忘录模式 介绍:在不破坏封装的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态,这样可以在以后将对象恢复到原先的状态。 实现:备忘录类,有一个私有状态属性…...
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在底层如何做隔离的,如何进行资源限制的? 3. docker命…...
树--二叉树(C语言纯手凹)
目录 目录 1.什么是树?(不深入,仅做了解) 2.树的表示方式 2.1孩子兄弟表示法(左孩子右兄弟) 2.2孩子表示法 2.3双亲表示法 3.什么是二叉树 4.二叉树分类 4.1满二叉树 4.2完全二叉树 4.3二叉搜索树…...
TypeScript(七) 函数
1. TypeScript 函数 1.1. 函数的定义 函数就是包裹在花括号中的代码块,前面使用关键字function。 语法: // An highlighted block function function_name() {// 执行代码 }实例: function test() { // 函数定义console.log("我就是…...
学fpga和还是嵌入式?
具体要选哪个,更多还是看个人喜好还有基础知识结构。 我们先来明白下两者区别在哪? 1、嵌入式:分两部分,第一是嵌入式软件开发,主要与嵌入式操作系统、应用软件等有关。第二是嵌入式硬件开发,需要掌握硬件…...
Day01-变量和数据类型课后练习-参考答案
文章目录 1、输出你最想说的一句话!2、定义所有基本数据类型的变量和字符串变量3、用合适类型的变量存储个人信息并输出4、定义圆周率PI5、简答题 1、输出你最想说的一句话! 编写步骤: 定义类 Homework1,例如:Homewo…...
Docker 数据管理、容器互联、网络与资源控制
一、docker数据管理 管理 Docker 容器中数据主要有两种方式:数据卷(Data volumes)和数据卷容器(Datavolumes containers)。 1、数据卷 数据卷是一个供容器使用的特殊目录,位于容器中。可将宿主机的目录挂载到数据卷上,对数据卷的修改操作立…...
密码加密——MD5与BCryptPasswordEncoder
目录 一、问题 二、密码加密 1、MD5密码加密 2、BCryptPasswordEncoder加密(推荐) 2.1 特点 2.2 使用步骤 一、问题 在数据库表中的密码都是明文存储的,安全性太低 需求: 将密码加密后存储,提高安全性 二、密码加密…...
利用外卖系统源码构建高效的在线订餐平台
在当今数字化时代,外卖服务已成为人们日常生活中不可或缺的一部分。为了满足用户需求,许多创业者和企业都希望搭建自己的在线订餐平台。利用现有的外卖系统源码,可以快速构建一个高效、安全的在线订餐平台。本文将介绍如何利用外卖系统源码来…...
数据分析数据 -(用数据讲故事)
书中有一句话我很喜欢- 献给大家 一个完美的设计,不是因为它没有多余的东西可以添加,而是它没有多余的部分可以删减 首先看几个对比的图形分析 处理工单和新增工单的随月份的变化趋势 这个图形的缺点就是 1: 月份对齐的情况 2:使用条形图需…...
如何运用5W2H分析法分析自己适合哪种办公室
随着时代的发展,办公室已经不再是传统的四壁之内,而是多种多样的形态,涵盖了开放式办公区、远程办公、共享办公空间等多种选择。对于刚刚创业的企业来说,选择一个适合自己发展的办公室至关重要。在这个过程中,运用5W2H…...
为什么考虑电子采购而非传统采购?
采购是重要的业务职能之一,为实现无缝运营而大规模采购商品或服务的行为。考虑到数字化转型带来的影响,决策者对于应维持传统采购还是转向电子采购或多或少会有困惑。 通过本文,你将更了解电子采购和传统采购,从而为业务连续性采…...
【git】git update-index --assume-unchanged(不改动.gitignore实现忽略文件)
文章目录 原因分析:添加忽略文件(取消跟踪)的命令:取消忽略文件(恢复跟踪)的命令:查看已经添加了忽略文件(取消跟踪)的命令: 原因分析: 已经维护的项目,文件已经被追踪,gitignore文件不方便修…...
科普类——无压缩图像传输带宽的计算(七)
无压缩图像传输带宽的计算 问题计算 问题 要计算1080p(1920x1080)分辨率的彩色图像在30帧每秒(fps)下的带宽需求,我们需要考虑图像的颜色深度(位深)和压缩情况。假设我们使用的是无压缩的RGB图…...
云原生周刊:K8s 1.26 到 1.29 版本的更新 | 2024.1.29
开源项目推荐 Skaffold Skaffold 是一个命令行工具,有助于 Kubernetes 应用程序的持续开发。您可以在本地迭代应用程序源代码,然后部署到本地或远程 Kubernetes 集群。Skaffold 处理构建、推送和部署应用程序的工作流程。它还提供构建块并描述 CI/CD 流…...
手机壳也能散热了?
作为一个玩了6年的王者荣耀玩家,手机发热真的很影响游戏体验!!游戏掉帧,性能下降很恼人,试过好几个散热工具,实际效果都不太好~ 自从入了Mate 60之后,看着这款微泵液冷壳毫无犹豫第…...
《微信小程序开发从入门到实战》学习九十七
7.3 表单组件 7.3.1 picke-view与picker-view-column组件 一个picker-view-column代表 一个滚动选择器子项,一个picker-view组件可以包含多个picker-view-column组件,这样可以一次性选择多项内容如年、月、日等。 picker-view-column组件中需包含多个…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
