当前位置: 首页 > 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;再…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...