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

数据结构:基数排序(c++实现)

在这里插入图片描述

个人主页 : 个人主页
个人专栏 : 《数据结构》 《C语言》《C++》《Linux》《网络》 《redis学习笔记》

文章目录

  • 基数排序的定义和基本原理
    • 基本原理
    • 具体步骤
  • 基数排序的优缺点:
  • 代码实现
  • 总结


基数排序的定义和基本原理

基数排序(Radix Sort)是一种非比较型整数排序算法,其基本原理是根据数字的每一位来进行排序。具体来说,基数排序通过将整数按位数切割成不同的数字,然后按每一位数进行排序(不断接近有序的过程),最终得到有序序列。


基本原理

  1. 按位排序:基数排序从最低有效位(Least Significant Digit, LSD) 或 最高位有效位(Most Significant Digit, MSD)开始,逐位进行排序。对于有d位的整数(排序整数的最长长度d),需要进行d趟排序。
  2. 使用桶排序:在每一轮排序中,将待排序的数字分配到不同的桶中,每个桶代表一个特定的数字范围。然后,从桶中取出数字并从新组合,形成新的有序序列
  3. 重复排序:重复上述过程,直到所有位数都排序完成。

具体步骤

  1. 确定最大值:找出待排序数组中的最大值,以确定需要进行多少趟排序
  2. 分配和搜集:根据当前位数,将每一个数字分配到相应的桶中,然后从桶中收集数字
  3. 重新排序:重复上述过程,直到所有位数都排序完成

下面列子,采用LSD:从最低位开始排序,逐步向上进行
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述


基数排序的优缺点:

优点:

  1. 时间复杂度低:基数排序的时间复杂度为O(nk), 其中n是待排序元素的数量,k是最大数的位数。
  2. 稳定性:基数排序是稳定的排序算法,相同值的元素在排序后保持其原有的顺序。
  3. 适用于大规模数据:基数排序特别适合处理大规模整数排序,能够有效利用计算机的并行处理能力

缺点:

  1. 空间复杂度高:基数排序需要额外的空间来存储中间结果,空间复杂度为O(n + k)或O(n + r),其中r是桶的数量
  2. 适用范围有限:基数排序主要用于整数排序,对于浮点数或字符串等其它类型的数据,需要进行额外的转换或处理
  3. 位数限制:当待排序元素位数较多时,基数排序的效率会下降,因为需要进行更多的轮次分类

代码实现

// 基数排序,核心思想是通过逐位排序实现整体有序
// 使用到queue,[0, 9]个queue来排列每一位
void RadixSort(vector<int>& arr) {int size = arr.size();if (size == 0)return;// 找到最大值,确认最大位数int maxVal = arr[0];for (int i = 1; i < size; ++i) {if (maxVal < arr[i])maxVal = arr[i];}int maxDigits = to_string(maxVal).length();// 初始化10个队列vector<queue<int>> buckets(10);// 逐位排序for (int i = 0; i < maxDigits; ++i) {int divisor = pow(10, i);// 分配元素到桶中for (int j = 0; j < size; ++j) {int index = arr[j] / divisor % 10;	// 获取当前位数buckets[index].push(arr[j]);}// 从桶中收集元素int index = 0;for (int j = 0; j < 10; ++j) {while (!buckets[j].empty()) {arr[index++] = buckets[j].front();buckets[j].pop();}}}
}

总结

以上就是我总结的C++面试题,TCP和UDP方面(1)

在这里插入图片描述

相关文章:

数据结构:基数排序(c++实现)

个人主页 &#xff1a; 个人主页 个人专栏 &#xff1a; 《数据结构》 《C语言》《C》《Linux》《网络》 《redis学习笔记》 文章目录 基数排序的定义和基本原理基本原理具体步骤 基数排序的优缺点&#xff1a;代码实现总结 基数排序的定义和基本原理 基数排序(Radix Sort)是一…...

DOM 事件 HTML 标签属性速查手册

以下是一份 DOM 事件 & HTML 标签属性速查手册&#xff0c;涵盖常用场景和示例&#xff0c;助你快速查阅和使用&#xff1a; 一、DOM 事件速查表 1. 鼠标事件 事件名触发时机适用元素示例代码click元素被点击任意可见元素button.addEventListener(click, () > { ... …...

PhotoShop学习01

了解Photoshop 这里省略了Photoshop的软件安装&#xff0c;请自行查找资源下载。 1.打开图片 下图为启动photoshop后出现的界面&#xff0c;我们可以通过创建新文件或打开已有文件来启用photoshop的工作界面。 可以通过左边的按钮进行新文件的创建或打开已有文件。 也可以点…...

mongodb【实用教程】

MongoDB 是一个开源的文档型数据库管理系统 下载安装 Windows 系统 https://blog.csdn.net/weixin_41192489/article/details/126777309 GUI工具 【推荐】MongoDB Compass https://www.mongodb.com/zh-cn/docs/compass/current/ Robo 3T https://blog.csdn.net/weixin_4119248…...

C语言机试编程题

编写版本&#xff1a;vc2022 1.求最大/小值 #include<stdio.h> int main(){int a[50],n;int max, min;printf("请输入您要输入几个数");scanf_s("%d", &n);printf("请输入您要比较的%d个数\n",n);for (int i 0; i<n; i) {scanf_…...

threeJs+vue 轻松切换几何体贴图

嗨&#xff0c;我是小路。今天主要和大家分享的主题是“threeJsvue 轻松切换几何体贴图”。 想象一下&#xff0c;手头上正好有个在线3D家具商店&#xff0c;用户不仅可以看到产品的静态图片&#xff0c;还能实时更换沙发的颜色或材质&#xff0c;获得真实的购物体验。…...

Android ObjectBox数据库使用与集成指南

ObjectBox其核心特点ObjectBox与 SQLite 和 Realm 的对比Android集成ObjectBox创建ObjectBox实体对象创建ObjectBox操作管理类OBManager在Application初始化ObjectBox插入或更新数据查询数据统计数据分页数据查询删除数据总结今天分享一套Android另一个数据库ObjectBox。Object…...

【HarmonyOS Next】地图使用详解(一)

背景 这系列文章主要讲解鸿蒙地图的使用&#xff0c;当前可以免费使用&#xff0c;并提供了丰富的SDK给开发者去自定义控件开发。目前可以实现个性化显示地图、位置搜索和路径规划等功能&#xff0c;轻松完成地图构建工作。需要注意的是&#xff0c;现在测试只能使用实体手机去…...

seacmsv9注入管理员账号密码+orderby+limi

1&#xff1a;mysql默认存储引擎innoDB携带的表 1&#xff0c;mysql.innodb_table_stats 2,mysql.innodb_index_stats SELECT table_name FROM mysql.innodb_table_stats WHERE database_name DATABASE(); 2&#xff1a; 关键字做处理 HEX编码:0x696E666F726D6174696F6E5F7…...

C#与AI的交互(以DeepSeek为例)

C#与ai的交互 与AI的交互使用的Http请求的方式&#xff0c;通过发送请求&#xff0c;服务器响应ai生成的文本 下面是完整的代码&#xff0c;我这里使用的是Ollama本地部署的deepseek&#xff0c;在联网调用api时&#xff0c;则url会有不同 public class OllamaRequester {[Se…...

面试八股文--数据库基础知识总结(2) MySQL

本文介绍关于MySQL的相关面试知识 一、关系型数据库 1、定义 关系型数据库&#xff08;Relational Database&#xff09;是一种基于关系模型的数据库管理系统&#xff08;DBMS&#xff09;&#xff0c;它将数据存储在表格&#xff08;表&#xff09;中&#xff0c;并通过表格…...

Failed to start The PHP FastCGI Process Manager.

报错如下&#xff1a; Job for php-fpm.service failed because the control process exited with error code. See "systemctl status php-fpm.service" and "journalctl -xe" for details. 2月 25 21:49:00 nginx systemd[1]: Starting The PHP FastC…...

软件供应链安全工具链研究系列——RASP自适应威胁免疫平台(上篇)

1.1 基本能力 RASP是一种安全防护技术&#xff0c;运行在程序执行期间&#xff0c;使程序能够自我监控和识别有害的输入和行为。也就是说一个程序如果注入或者引入了RASP技术&#xff0c;那么RASP就和这个程序融为一体&#xff0c;使应用程序具备了自我防护的能力&#xff0c;…...

Spring Boot集成MyBatis访问MySQL:从项目搭建到基础数据库查询(基础入门)

Spring Boot集成MyBatis访问MySQL 一、引言 在当今企业级应用开发中&#xff0c;Spring Boot、MyBatis与MySQL的组合凭借其高效性和灵活性&#xff0c;成为构建数据驱动型应用的首选方案。本文将带你从零开始搭建项目&#xff0c;掌握Spring Boot集成MyBatis的基础入门内容。…...

一周学会Flask3 Python Web开发-Jinja2模板继承和include标签使用

锋哥原创的Flask3 Python Web开发 Flask3视频教程&#xff1a; 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 不管是开发网站还是后台管理系统&#xff0c;我们页面里多多少少有公共的模块。比如博客网站&#xff0c;就有公共的头部&…...

【2025.2.25更新】wordpress免费AI插件,文章内容、图片自动生成、视频自动生成、网站AI客服、批量采集文章,内置deepseek联网满血版

wordpress免费AI插件&#xff0c;文章内容、文章图片、长尾关键词、视频自动生成、网站AI客服、批量采集文章&#xff0c;插件已接入腾讯云大模型知识引擎xDeepSeek&#xff0c;基于腾讯云大模型知识引擎xDeepSeek可联网满血版&#xff0c;插件可实现文章生成、长尾关键词生成、…...

待解决 leetcode71 简化路径 栈的应用

用多种ifelse很不好很复杂容易丢情况 class Solution { public:string simplifyPath(string path) {stack<char> st;string result;int n path.size();while(n > 1 && (path[n-1] / || path[n-1] .)){if(n > 2 && path[n-2] . && pat…...

数据安全_笔记系列09_人工智能(AI)与机器学习(ML)在数据安全中的深度应用

数据安全_笔记系列09_人工智能&#xff08;AI&#xff09;与机器学习&#xff08;ML&#xff09;在数据安全中的深度应用 人工智能与机器学习技术通过自动化、智能化的数据分析&#xff0c;显著提升了数据分类、威胁检测的精度与效率&#xff0c;尤其在处理非结构化数据、复杂…...

RocketMQ 可观测性最佳实践

RocketMQ 概述 Apache RocketMQ 是一个开源的分布式消息传递和流处理平台&#xff0c;由阿里巴巴团队最初开发并捐赠给 Apache 软件基金会。它主要用于处理大规模消息的发送和接收&#xff0c;支持高吞吐量、可扩展性强且具有高可用性的消息服务。 RocketMQ 的优势有以下几点…...

P9420 [蓝桥杯 2023 国 B] 子 2023

P9420 [蓝桥杯 2023 国 B] 子 2023 题目 分析代码 题目 分析 刚拿到这道题&#xff0c;我大脑简单算了一下&#xff0c;这个值太大了&#xff0c;直观感觉就很难&#xff01;&#xff01; 但是&#xff0c;你仔仔细细的一看&#xff0c;先从最简单的第一步入手&#xff0c;再…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...