排序算法-基数排序法(RadixSort)

排序算法-基数排序法(RadixSort)

1、说明

基数排序法与我们之前讨论的排序法不太一样,并不需要进行元素之间的比较操作,而是属于一种分配模式排序方式。

基数排序法比较的方向可分为最高位优先(Most Significant Digit First,MSD)和最低位优先(Least Significant Digit First,LSD)两种。MSD是从最左边的位数开始比较的,而LSD则是从最右边的位数开始比较的。

2、算法分析

  1. 在所有情况下,时间复杂度均为O(n{log_{p}}^{k}),k是原始数据的最大值。
  2. 基数排序法是稳定排序法。
  3. 基数排序法要使用很大的额外空间来存放列表数据,其空间复杂度为O(n*p),n是原始数据的个数,p是数据字符数。
  4. 若n很大,p固定或很小,则此排序法的效率很高。

3、C++代码 

#include<iostream>
#include<iomanip>
using namespace std;void PrintData(int data[], int size) {for (int i = 0; i < size; i++) {cout << data[i] << " ";}cout << endl;
}void SetData(int data[], int size) {srand(time(nullptr));for (int i = 0; i < size; i++) {data[i] = rand() % 999 + 1;}
}void Radix(int data[], int size) {for (int n = 1; n <= 100; n *= 10) {int temp[10][100] = { 0 };for (int i = 0; i < size; i++) {int m = (data[i] / n) % 10;temp[m][i] = data[i];}int k = 0;for (int i = 0; i < 10; i++) {for (int j = 0; j < size; j++) {if (temp[i][j] != 0) {data[k] = temp[i][j];k++;}}}cout << "经过" << setw(3) << n << "位排序后:";PrintData(data, size);}
}int main() {int size = 20;int* data = new int[size];SetData(data, size);cout << "原始数据:";PrintData(data, size);cout << "---------------------------------" << endl;Radix(data, size);cout << "---------------------------------" << endl;cout << "最终数据:";PrintData(data, size);return 0;
}

输出结果 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/160262.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

卡片翻转效果的实现思路

卡片翻转效果的实现思路 HTML 基础布局 <div class"card"><img class"face" src"images/chrome_eSCSt8hUpR.png" /><p class"back"><span>背面背景</span></p> </div>布局完成后如下所示…

IDEA启动报错Failed to create JVM. JVM path的解决办法

今天启动IDEA时IDEA报错&#xff0c;提示如下。 if you already hava a JDK installed, define a JAVA_HOME variable in Computer > Systen Properties > System Settings > Environment Variables.Failed to create JVM. JVM path:D:\ideaIU2023.2.3\IntelliJ IDE…

【广州华锐互动】利用VR开展细胞基础实验教学有什么好处?

在科技发展的驱动下&#xff0c;虚拟现实&#xff08;VR&#xff09;技术已被广泛应用于各个领域&#xff0c;包括教育和医学。尤其是在医学教育中&#xff0c;VR技术已成为一种革新传统教学模式的有效工具。本文将探讨使用VR进行细胞基础实验教学的优势。 首先&#xff0c;VR技…

windows每天定时重启 Win11 Win10定时重启 windows定时重启系统 windows每天定时重启

windows每天定时重启 Win11 Win10定时重启 windows定时重启系统 windows每天定时重启 使用 Windows 的任务计划程序来设置每天自动重启计算机1. 打开 任务计划程序&#xff1a;2. 在 任务计划程序库 面板中&#xff0c;创建一个基本任务3、设置计划任务权限 使用 Windows 的任务…

布局--QT Designer

一、在我们使用Qt做界面设计时&#xff0c;为了界面的整洁美观&#xff0c;往往需要对界面中的所有控件做一个有序的排列&#xff0c;以及设置各个控件之间的间距等等&#xff0c;为此Qt为界面设计提供了基本布局功能&#xff0c;使用基本布局可以使组件有规则地分布。 1.1 基…

罗技鼠标接收器丢失或损坏后用另一个接收器配对的方法

本文介绍罗技鼠标在丢失、损坏其自身原有的接收器后&#xff0c;将另一个新的接收器与原有鼠标相互配对的方法。 在开始之前&#xff0c;大家需要首先查看两个内容&#xff1a;首先是原有的鼠标——大家需要查看自己的鼠标&#xff08;罗技键盘也是同样的操作&#xff09;底部&…

[NewStarCTF 2023] web题解

文章目录 WEEK1泄漏的秘密Begin of UploadBegin of HTTPErrorFlaskBegin of PHPR!C!E!EasyLogin WEEK2游戏高手include 0。0ez_sqlUnserialize&#xff1f;Upload again!R!!C!!E!! WEEK1 泄漏的秘密 打开题目&#xff0c;提示有敏感信息泄露 直接扫一下目录&#xff0c;发现有…

Stm32_标准库_10_TIM_显示时间日期

利用TIM计数耗费1s,启动中断&#xff0c;秒表加一 时间显示代码&#xff1a; #include "stm32f10x.h" // Device header #include "Delay.h" #include "OLED.h"uint16_t num 0; TIM_TimeBaseInitTypeDef TIM_TimeBaseInitStructure; NVIC_I…

[入门一]C# webApi创建、与发布、部署、api调用

一.创建web api项目 1.1、项目创建 MVC架构的话&#xff0c;它会有view-model-control三层&#xff0c;在web api中它的前端和后端是分离的&#xff0c;所以只在项目中存在model-control两层 1.2、修改路由 打开App_Start文件夹下&#xff0c;WebApiConfig.cs ,修改路由&…

什么是云原生?零基础学云原生难吗?

伴随着云计算的浪潮&#xff0c;云原生概念也应运而生&#xff0c;而且火得一塌糊涂&#xff0c;但真正谈起“云原生”&#xff0c;大多数非 IT 从业者的认知往往仅限于将服务应用放入云端&#xff0c;在云上处理业务。实际上&#xff0c;云原生远不止于此。 现在越来越多的企…

03在命令行环境中创建Maven版的Java工程,了解pom.xml文件的结构,了解Java工程的目录结构并编写代码,执行Maven相关的构建命令

创建Maven版的Java工程 Maven工程的坐标 数学中使用x、y、z三个向量可以在空间中唯一的定位一个点, Maven中也可以使用groupId,artifactId,version三个向量在Maven的仓库中唯一的定位到一个jar包 groupId: 公司或组织域名的倒序, 通常也会加上项目名称代表公司或组织开发的一…

Avalonia使一个弹窗弹到指定位置

1.项目下载地址&#xff1a;https://gitee.com/confusedkitten/avalonia-demo 2.UI库Semi.Avalonia&#xff0c;项目地址 https://github.com/irihitech/Semi.Avalonia 3.样式预览 4.PositionControl.axaml <UserControl xmlns"https://github.com/avaloniaui&quo…

k8s-12 存储之configmap

开启之后 先看集群是否正常 Configmap用于保存配置数据&#xff0c;以键值对形式存储configMap 资源提供了向 Pod 注入配置数据的方法旨在让镜像和配置文件解耦&#xff0c;以便实现镜像的可移植性和可复用性 典型的使用场景 填充环境变量的值 设置容器内的命令行参数 填充卷的…

机器人硬件在环仿真:解决实体开发与测试挑战,提升效率与安全性

工业机器人具备出色的灵活性和运动能力&#xff0c;广泛应用于工业制造领域。它们可以完成装配、焊接、喷涂、搬运、加工、品质检测等任务&#xff0c;提高了生产效率&#xff0c;保证了产品质量。此外&#xff0c;在医疗领域也有辅助手术等特殊应用&#xff0c;展现了其在多个…

怎么团队合作,协作开发

一、代码托管平台 我是在大一下的一个竞赛中接触到的代码托管平台 那个时候我也算是什么都不会的&#xff0c;不过不得不说这个确实比较重要&#xff0c;对我造成了一些冲击 在我看来&#xff0c;代码托管平台的作用就是在一个中转站&#xff08;仓库&#xff09;上存储我们写…

在雷电模拟器9上安装magisk并安装LSPosed模块以及其Manager管理器(一)

环境&#xff1a;win10 64&#xff0c;雷电模拟器9.0.60(9)&#xff0c;Android 9。 之前我都是用雷电模拟器版本4.0.78&#xff0c;Android版本7.1.2&#xff0c;为什么本篇要使用9了呢&#xff1f;先解答下这个问题。原因如下&#xff1a;经过我的测试&#xff0c;LSPosed不支…

Windows网络系统架构

在介绍Windows网络体系架构之前&#xff0c;我首先介绍一下Windows中的两个重要编程规范——TDI&#xff0c;NDIS.&#xff0c;然后再介绍网络体系的架构。TDI&#xff0c;Transport Driver Interface&#xff0c;传输驱动程序接口。/Windows/System32/Drivers/Tdi.sys。在实现…

微服务docker部署实战

docker基础和进阶(*已掌握的可以跳过 *) 基础 docker基础 进阶 docker进阶 准备工作 提前准备好mysql和redis的配置&#xff0c;如下 在/zzq/mysql/conf目录下配置mysql配置文件my.cnf [client] #设置客户端字符集 default_character_setutf8 [mysqld] #开启定时任务 event_s…

java springboot 通过ConfigurationProperties给第三方bean注入属性

之前我们的文章 java boot将一组yml配置信息装配在一个对象中 讲过了 通过ConfigurationProperties将配置文件中的内容默认装配进属性类 但 这建立在 bean是自己定义的 如果 这是个第三方的类呢&#xff1f; 就比如 我们在 application 中写了一套数据源的加载规则 但需要用第…