当前位置: 首页 > 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组件中需包含多个…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...