排序:基数排序算法分析

1.算法思想

假设长度为n的线性表中每个结点aj的关键字由d元组 ( k j d − 1 , k j d − 2 , k j d − 3 , . . . , k j 1 , k j 0 ) (k_{j}^{d-1},k_{j}^{d-2},k_{j}^{d-3},... ,k_{j}^{1} ,k_{j}^{0}) (kjd1,kjd2,kjd3,...,kj1,kj0)组成,
其中, 0 < = k j i < = r − 1 ( 0 < = j < n , 0 < = i < = d − 1 ) 0<=k_{j}^{i}<=r-1(0<=j<n,0<=i<=d-1) 0<=kji<=r1(0<=j<n,0<=i<=d1),r称为“基数”。

在这里插入图片描述

基数排序得到递减序列的过程如下:

  1. 初始化︰设置r个空队列, Q r − 1 , Q r − 2 , . . . , Q 0 Q_{r-1},Q_{r-2,}...,Q_0 Qr1Qr2,...Q0
  2. 按照各个关键字位权重递增的次序(个、十、百),对d个关键字位分别做“分配”和“收集”
  3. 分配:顺序扫描各个元素,若当前处理的关键字位,则将元素插入Qx队尾,一趟分配耗时O(n)
  4. 收集:把 Q r − 1 , Q r − 2 , . . . , Q 0 Q_{r-1},Q_{r-2},...,Q_0 Qr1,Qr2,...Q0各个队列中的结点依次出队并链接,一趟收集耗时O(r)

例如:收集:得到一个按“百位”递减排列的序列,若“百位”相同则按“十位"递减排列,若“十位”还相同则按“个位”递减排列。

基数排序不是基于“比较”的排序算法

2.算法效率分析

基数排序通常基于链式存储实现:

typedef struct LinkNode {ElemType data;struct LinkNode *next;
} LinkNode, *LinkList;

链式队列设计:

typedef struct {//链式队列LinkNode *front, *rear;//队列的队头和队尾指针
} LinkQueue;
1.空间复杂度

需要r个辅助队列,空间复杂度= O(r)。

2.时间复杂度

一趟分配O(n),一趟收集O(r),总共d趟分配、收集,总的时间复杂度=O(d(n+r))

3.稳定性

基数排序是稳定的。

3.基数排序的应用

1.学生年龄排序

某学校有10000学生,将学生信息按年龄递减排序
生日可拆分为三组关键字:年(1991-2005)、月(1-12)、日(1-31)

权重:年>月>日,年、月、日越大,年龄越小。

  1. 第一趟分配、收集(按“日"递增)
  2. 第二趟分配、收集(按“月”递增)
  3. 第三趟分配、收集(按“年”递增)

若采用基数排序,时间复杂度= O(d(n+r)),约等于 O(30000)
若采用 O ( n 2 ) O(n^2) O(n2)的排序,约等于 O ( 1 0 8 ) O(10^8) O(108)
若采用 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)的排序,约等于O(140000)

可以看到这里采用基数排序时间复杂度会更低。

2.基数排序适合解决的问题
  • ①数据元素的关键字可以方便地拆分为d组,且d较小(反例:给5个人的身份证号排序)
  • ②每组关键字的取值范围不大,即r较小(反例:给中文人名排序)
  • ③数据元素个数n较大(擅长:给十亿人的身份证号排序)

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

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

相关文章

缓存一致性(cache coherency)解决方案:MESI 协议状态转换详解

MESI 协议 一&#xff0c;MESI状态释义二&#xff0c;MESI状态转换1 Invalid after Reset2, Invalid > Exclusive3, Exclusive > Modified4 Modified > Shared, Invalid > Shared5 Shared > Invalid, Shared > Modified 三&#xff0c;状态转换场景总结Inval…

Linux常见指令2

Linux常见指令[2] 一.Linux常见指令1.man补充知识:nano 2.cp3.mv4.cat补充知识:echo输出重定向追加重定向回到catcat其他用法 5.less和more补充内容回到less 6.head和tail补充知识:命令行管道 一.Linux常见指令 前言:为了方便我们在Linux中写指令 介绍一下: 1.clear指令: 清屏…

【每日一题】2769. 找出最大的可达成数字

2769. 找出最大的可达成数字 - 力扣&#xff08;LeetCode&#xff09; 给你两个整数 num 和 t 。 如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等&#xff0c;则称其为 可达成数字 &#xff1a; 每次操作将 x 的值增加或减少 1 &#xff0c;同时可以选择将 …

红黑树是如何实现的?

文章目录 一、红黑树的概念二、红黑树的性质三、红黑树和AVL树对比四、红黑树的插入1. 红黑树的结点定义2. 父亲的颜色3. 叔叔的颜色为红色4. 叔叔不存在5. 叔叔存在且为黑6. 插入的抽象图 五、红黑树的验证1. 检查平衡2. 计算高度与旋转次数3. 验证 六、 红黑树与AVL树的比较 …

基于SSM+Vue的医院住院综合服务管理系统的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用Vue技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

ROS系统读取USB相机图像数据

ROS系统读取USB相机图像数据 前言usb_cam 功能包下载与编译摄像头选择连接摄像头可配置参数 前言 usb_cam功能包简介 为了丰富机器人与外界的交互方式&#xff0c;已经增加了与机器人的语音交互方式&#xff0c;不仅使机器人能够说话发声&#xff0c;还能听懂我们说的话&#…

Windows中实现将bat或exe文件作为服务_且实现命令行安装、配置、启动、删除服务

一、背景描述 在Windows环境下进行日常的项目开发过程中&#xff0c;有时候需要将bat文件或exe文件程序注册为Windows的服务实现开机自己运行&#xff08;没有用户登陆&#xff0c;服务在开机后也可以照常运行&#xff09;、且对于那些没有用户交互界面的exe程序来说只要在后台…

STL upper_bound和lower_bound函数

声明&#xff1a; 首先包含头文件#include<algorithm> 这里的两个函数所运用的对象必须是非递减的序列&#xff08;也就是数组&#xff0c;数组必须是非递减的&#xff09;&#xff0c;只有这样才可以使用upper_bound和lower_bound这两个函数。 还有一点&#xff0c;就…

Python入门教程48:Pycharm永久镜像源的pip配置方法

国内几个好用的Python镜像服务器地址&#xff1a; 清华大学镜像站&#xff1a;https://pypi.tuna.tsinghua.edu.cn/simple/阿里云镜像站&#xff1a;https://mirrors.aliyun.com/pypi/simple/中科大镜像站&#xff1a;https://pypi.mirrors.ustc.edu.cn/simple/中国科技大学镜…

HTML5福利篇--使用Canvas画图

目录 一.Canvas元素 1.Canvas元素定义 2.使用JavaScript获取页面中的Canvas对象 二.绘制图形 1.绘制直线 2.绘制矩形 &#xff08;1&#xff09;rect() &#xff08;2&#xff09;strokeRect() &#xff08;3&#xff09;fillRect()和clearRect()函数 3.绘制圆弧 4.…

ElementUI之首页导航+左侧菜单->mockjs,总线

mockjs总线 1.mockjs 什么是Mock.js 前后端分离开发开发过程当中&#xff0c;经常会遇到以下几个尴尬的场景&#xff1a; - 老大&#xff0c;接口文档还没输出&#xff0c;我的好多活干不下去啊&#xff01; - 后端小哥&#xff0c;接口写好了没&#xff0c;我要测试啊&#x…

opencv: 解决保存视频失败的问题

摘要&#xff1a;opencv能读取视频&#xff0c;但保存视频时报错。 一、首先要确保已经下载了openh264.dll文件&#xff0c;否则保存的视频无法打开&#xff0c;详细可以浏览这个&#xff1a;opencv&#xff1a;保存视频。 二、保存视频时出现一下问题&#xff1a; OpenCV:…

COCO 数据集 人体关键点格式

图片与标注数据在 COCO官网 均提供下载 标注格式 COCO 的标注中包含 4 个部分/字段&#xff0c;"info" 描述数据集&#xff0c;"licenses" 描述图片来源&#xff0c;"images" 和 "annotations" 是主体部分 "images" 部分…

一文带你全面解析postman工具的使用

写在前面&#xff1a;本文转自今日头条作者雨滴测试&#xff0c;感兴趣可点击下方链接查看原文 基础篇效率篇高级篇 一文带你全面解析postman工具的使用 文章目录 一文带你全面解析postman工具的使用基础篇一、postman安装说明1.下载与安装2.界面导航说明3.发送第一个请求 二、…

3 OpenCV两张图片实现稀疏点云的生成

前文&#xff1a; 1 基于SIFT图像特征识别的匹配方法比较与实现 2 OpenCV实现的F矩阵RANSAC原理与实践 1 E矩阵 1.1 由F到E E K T ∗ F ∗ K E K^T * F * K EKT∗F∗K E 矩阵可以直接通过之前算好的 F 矩阵与相机内参 K 矩阵获得 Mat E K.t() * F * K;相机内参获得的方式…

87、Redis 的 value 所支持的数据类型(String、List、Set、Zset、Hash)---->List相关命令

本次讲解要点&#xff1a; List相关命令&#xff1a;是指value中的数据类型 启动redis服务器&#xff1a; 打开小黑窗&#xff1a; C:\Users\JH>e: E:>cd E:\install\Redis6.0\Redis-x64-6.0.14\bin E:\install\Redis6.0\Redis-x64-6.0.14\bin>redis-server.exe redi…

Java编码技巧:验证码

目录 1.1、EasyCaptcha&#xff08;优选&#xff0c;支持种类多&#xff0c;样式多&#xff0c;使用简单&#xff09;1.1.1、作用1.1.2、官方信息1.1.3、使用案例1.1.4、依赖1.1.5、代码1.1.6、效果1.1.7、拓展 1.2、kaptcha1.2.1、作用1.2.2、官方信息1.2.3、使用案例1.2.4、依…

DE0开发板交通灯十字路口红绿灯VHDL

名称&#xff1a;基于DE0开发板的交通灯十字路口红绿灯 软件&#xff1a;Quartus 语言&#xff1a;VHDL 要求&#xff1a; 设计一个十字路口交通信号灯的控制电路。分为两种情况&#xff0c;正常状态和报警状态。 1.正常状态&#xff1a;要求红、绿灯按一定的规律亮和灭&a…

触觉智能 PurPle Pi OH(OpenHarmony)开发板

资料汇总 内容预览 产品介绍 PurPle-Pi OH 规格书​​​​​​ 系统编译 Purple-Pi-OH Linux SDK编译 Purple-Pi-OH OHOS SDK编译 使用手册 Purple-Pi-OH Ubuntu系统使用手册 常见FAQ 常见问题 官网 官网地址 Purple Pi OH介绍 Purple Pi OH作为一款兼容树莓派的开…

多个pdf合并成一个文件,3个方法合并pdf

如何把多个pdf合并成一个文件&#xff1f;在我们日常的工作中&#xff0c;经常会遇到一些需要处理的文件&#xff0c;其中包括PDF文件。特别是当我们需要将多个PDF文件合并成一个PDF文件时&#xff0c;会面临一些困难。这样的情况下&#xff0c;我们的阅读能力会受到限制&#…