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

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

基数排序的概念:

什么是基数排序???基数排序是一种和快排、归并、希尔等等不一样的排序...它不需要比较和移动就可以完成整型的排序。它是时间复杂度是O(K*N),空间复杂度是O(K+M


基数排序的思想: 

  • 基数排序是一种借助多关键字的思想对单逻辑关键字进行排序的方法。
  • 基数排序根据每个位来分配桶,怎么理解呢???看下面的动图,0-9就是所分配的桶
  • 用大白话来说,基数排序就是先分发数据再回收数据,可以看看下面的动图。

181965eaa5e249518e426b17fcc6d02a.gif


  •  接下来,跟着我的思路走,你也可以实现它。如下面代码,我先定义了一个数组,然后求出来了它的个数。然后就进入基数排序。
int main()
{int arr[10] = { 278,109,63,930,589,183,505,269,83,8 };int n = sizeof(arr) / sizeof(int);for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;//基数排序RadixSrot(arr, 0, n);for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;return 0;
}

 


RadixSort函数实现:

  • 思想就是先分发再回收数据。这里的K,我是用宏来定义的,因为我所创建的arr数组最多也就是到了百位,所以其实我们分发3次数据就可以回收了。
#define K 3
void RadixSrot(int arr[],int left,int right) //[left,right)
{for (int i = 0; i < K; i++){//分发数据Distribute(arr, left, right, i);//回收数据Collect(arr);}
}

分发数据的实现:

  • 分发数据中,我用key来接受了每次分发数据后的值。
  • 下面我来演示它每一次的排序情况。
  • 桶其实就是0-9:
  •  0         1          2        3        4        5         6          7           8            9   
  •  930                         63              505                               278        109
  •                               183                                                        8       589
  •                                  83                                                                269  

然后第一次排序完就是:930  63 183 83 505 278 8 109 589 269

  •  0         1          2        3        4        5         6          7           8            9   
  •   505                         930                         63       278        183
  • 008                                                           269                  083
  • 109                                                                                    589

第二次排序完就是  505   008   109   930   63   269   278   183    038   589

第三次排序完:8   63   83   109   183   269   278   505   589   930

 

  • 它的思想就是这样,也因为它是先分发的数据先回收,所以我定义了10个int的队列,因为考虑最坏情况(如果个位数全部是一样的),得到分发过后的个位数后,我就将数字插入到对应的队列中。然后回收,因为是先分发先回收,队列特性刚好满足,就将队列中的数放到数组中,这就完成了第一次的排序。因为都是百位数,所以最多是3次,就用上面的图中的for循环来完成接下里的排序。

 

#define RADIX 10//定义基数  构造了10个int的队列
queue<int> Q[RADIX];void Distribute(int arr[],int left,int right,int k)
{for (int i = left;i < right; i++){int key = GetKey(arr[i], k);Q[key].push(arr[i]);}}
int GetKey(int value, int k)
{int key = 0;while (k >= 0){key = value % 10;value /= 10;k--;}return key;
}

 


 下面是源码:

#define  _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>
using namespace std;#define K 3
#define RADIX 10//定义基数  构造了10个int的队列
queue<int> Q[RADIX];//value : 278
//k =0 的时候 就得到8  k=1 就得到7
int GetKey(int value, int k)
{int key = 0;while (k >= 0){key = value % 10;value /= 10;k--;}return key;
}//k代表了第几次分发数据
void Distribute(int arr[],int left,int right,int k)
{for (int i = left;i < right; i++){int key = GetKey(arr[i], k);Q[key].push(arr[i]);}}void Collect(int arr[])
{int k = 0;for (int i = 0; i < RADIX; i++){while (!Q[i].empty()){arr[k++] = Q[i].front();Q[i].pop();}}
}void RadixSrot(int arr[],int left,int right) //[left,right)
{for (int i = 0; i < K; i++){//分发数据Distribute(arr, left, right, i);//回收数据Collect(arr);}
}int main()
{int arr[10] = { 278,109,63,930,589,183,505,269,83,8 };int n = sizeof(arr) / sizeof(int);for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;//基数排序RadixSrot(arr, 0, n);for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;return 0;
}

 

 

相关文章:

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

基数排序的概念&#xff1a; 什么是基数排序&#xff1f;&#xff1f;&#xff1f;基数排序是一种和快排、归并、希尔等等不一样的排序...它不需要比较和移动就可以完成整型的排序。它是时间复杂度是O&#xff08;K*N&#xff09;&#xff0c;空间复杂度是O&#xff08;KM&…...

leetcode做题笔记75颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums &#xff0c;原地对它们进行排序&#xff0c;使得相同颜色的元素相邻&#xff0c;并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决…...

聊一下互联网开源变现

(点击即可收听) 互联网开源变现其实是指通过开源软件或者开放源代码的方式&#xff0c;实现收益或盈利。这种方式越来越被广泛应用于互联网行业 在互联网开源变现的模式中&#xff0c;最常见的方式是通过捐款、广告、付费支持或者授权等方式获利。 例如&#xff0c;有些开源软件…...

PHP日期差计算器,计算两个时间相差 年/月/日

1. 计算两个日期相隔多少年&#xff0c;多少月&#xff0c;多少天示例&#xff1a;laravel框架实现 /*** 天数计算* return \Illuminate\Http\JsonResponse*/public function loveDateCal(){$start_date $this->request(start_date);$end_date $this->request(end_date…...

20230812在WIN10下使用python3将SRT格式的字幕转换为SSA格式

20230812在WIN10下使用python3将SRT格式的字幕转换为SSA格式 2023/8/12 20:58 本文的SSA格式以【Batch Subtitles Converter(批量字幕转换) v1.23】的格式为准&#xff01; 1、 缘起&#xff1a;网上找到的各种各样的字幕转换软件/小工具都不是让自己完全满意&#xff01; 【都…...

matlab使用教程(13)—稀疏矩阵创建和使用

使用稀疏矩阵存储包含众多零值元素的数据&#xff0c;可以节省大量内存并加快该数据的处理速度。sparse 是一种属性&#xff0c;可以将该属性分配给由 double 或 logical 元素组成的任何二维 MATLAB 矩阵。通过 sparse 属性&#xff0c;MATLAB 可以&#xff1a; • 仅存储矩…...

UI美工设计的主要职责(合集)

UI美工设计的主要职责1 职责&#xff1a; 1、执行公司的规章制度及专业管理办法; 2、 负责重点项目的原型设计和产品流程设计、视觉设计&#xff0c;优化网站和移动端的设计流程和规范&#xff0c;制定产品 UI/UE规范及文档编写; 3、负责使用PS、AI、illustrator、MarkMan、…...

【前端二次开发框架关于关闭eslint】

前端二次开发框架关于关闭eslint 方法一方法二方法三方法四&#xff1a;以下是若想要关闭项目中的部分代码时&#xff1a; 方法一 在vue.config.js里面进行配置&#xff1a; module.exports {lintOnSave:false,//是否开启eslint保存检测 ,它的有效值为 true || false || err…...

Scractch3.0_Arduino_ESP32_学习随记_蓝牙键盘(三)

C02蓝牙键盘 目的器材程序联系我们 目的 通过C02实现蓝牙键盘 器材 硬件: 齐护机器人C02 购买地址 软件: scratch3.0 下载地址:官网下载 程序 在P5口连接按钮模块。 蓝牙键盘组合按键动作的实现。 当对应按键按下时模拟键盘动作&#xff0c;先按下ctrl然后按下对应组合键…...

Spark2.2出现异常:ERROR SparkUI: Failed to bind SparkUI

详细错误信息如下&#xff1a; 复制代码 19/03/19 11:04:18 INFO util.log: Logging initialized 5402ms 19/03/19 11:04:18 INFO server.Server: jetty-9.3.z-SNAPSHOT 19/03/19 11:04:18 INFO server.Server: Started 5604ms 19/03/19 11:04:18 WARN util.Utils: Service ‘S…...

LeetCode 2811. Check if it is Possible to Split Array【脑筋急转弯;前缀和+动态规划或记忆化DFS】中等

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

【学习日记】【FreeRTOS】链表结构体及函数详解

写在前面 本文主要是对于 FreeRTOS 中链表相关内容的详细解释&#xff0c;代码大部分参考了野火FreeRTOS教程配套源码&#xff0c;作了一小部分修改。 一、结构体定义 主要包含三种结构体&#xff1a; 普通节点结构体结尾节点&#xff08;mini节点&#xff09;结构体链表结…...

【云原生•监控】基于Prometheus实现自定义指标弹性伸缩(HPA)

【云原生•监控】基于Prometheus实现自定义指标弹性伸缩(HPA) 什么是弹性伸缩 「Autoscaling即弹性伸缩&#xff0c;是Kubernetes中的一种非常核心的功能&#xff0c;它可以根据给定的指标&#xff08;例如 CPU 或内存&#xff09;自动缩放Pod副本&#xff0c;从而可以更好地管…...

Windows、 Linux 等操作系统的基本概念及其常见操作

Windows 和 Linux 是两种常见的操作系统&#xff0c;它们在计算机领域中广泛使用。下面我将为您介绍它们的基本概念以及一些常见的操作。 **Windows 操作系统&#xff1a;** 1. **基本概念&#xff1a;** Windows 是由微软公司开发的操作系统系列&#xff0c;旨在为个人计算机…...

【RabbitMQ】golang客户端教程5——使用topic交换器

topic交换器&#xff08;主题交换器&#xff09; 发送到topic交换器的消息不能具有随意的routing_key——它必须是单词列表&#xff0c;以点分隔。这些词可以是任何东西&#xff0c;但通常它们指定与消息相关的某些功能。一些有效的routing_key示例&#xff1a;“stock.usd.ny…...

SpringBoot对接OpenAI

SpringBoot对接OpenAI 随着人工智能技术的飞速发展&#xff0c;越来越多的开发者希望将智能功能集成到自己的应用中&#xff0c;以提升用户体验和应用的功能。OpenAI作为一家领先的人工智能公司&#xff0c;提供了许多先进的自然语言处理和语言生成模型&#xff0c;其中包括深…...

(C++)继承

目录 1.继承的概念及定义 1.1继承的概念 1.2继承定义 1.2.1定义格式 1.2.2继承方式和访问限定符 1.2.3继承基类成员访问方式的变化 2.基类和派生类对象赋值转换 3.继承中的作用域 4.派生类的默认成员函数 5.继承与友元 6.继承与静态成员 7.复杂的菱形继承及菱形虚拟…...

图像处理技巧形态学滤波之膨胀操作

1. 引言 欢迎回来&#xff0c;我的图像处理爱好者们&#xff01;今天&#xff0c;让我们继续研究图像处理领域中的形态学计算。在本篇中&#xff0c;我们将重点介绍腐蚀操作的反向效果膨胀操作。 闲话少说&#xff0c;我们直接开始吧&#xff01; 2. 膨胀操作原理 膨胀操作…...

机器学习基础之《特征工程(4)—特征降维》

一、什么是特征降维 降维是指在某些限定条件下&#xff0c;降低随机变量&#xff08;特征&#xff09;个数&#xff0c;得到一组“不相关”主变量的过程 1、降维 降低维度 ndarry 维数&#xff1a;嵌套的层数 0维&#xff1a;标量&#xff0c;具体的数0 1 2 3... …...

学生管理系统(Python版本)

class Student:def __init__(self, id, name, age):self.id idself.name nameself.age ageclass StudentManagementSystem:def __init__(self):self.students []def add_student(self, student):self.students.append(student)print("学生信息添加成功&#xff01;&qu…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...