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

排序:基数排序算法分析

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较大(擅长:给十亿人的身份证号排序)

相关文章:

排序:基数排序算法分析

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}) (kjd−1​,kjd−2​,kjd−3​,...,kj1​,kj0​)组成&#xff0c; 其中&am…...

用go实现http服务端和请求端

一、概述 本文旨在学习记录下如何用go实现建立一个http服务器&#xff0c;同时构造一个专用格式的http客户端。 二、代码实现 2.1 构造http服务端 1、http服务处理流程 基于HTTP构建的服务标准模型包括两个端&#xff0c;客户端(Client)和服务端(Server)。HTTP 请求从客户端…...

幂级数和幂级数的和函数有什么关系?

幂级数和幂级数的和函数有什么关系&#xff1f; 本文例子引用自&#xff1a;80_1幂级数运算&#xff0c;逐项积分、求导【小元老师】高等数学&#xff0c;考研数学 求幂级数 ∑ n 1 ∞ 1 n x n \sum\limits_{n1}^{\infty}\frac{1}{n}x^n n1∑∞​n1​xn 的和函数 &#xff…...

Git多账号管理通过ssh 公钥的方式,git,gitlab,gitee

按照目前国内访问git&#xff0c;如果不科学上网&#xff0c;我们很大可能访问会超时。基于这个&#xff0c;所以我现在的git 配置已经增加到了3个了 一个公司gitlab&#xff0c;一个git&#xff0c;一个gitee. 以下基于这个环境&#xff0c;我们来说明下如何创建配置ssh公钥。…...

在nodejs常见的不良做法及其优化解决方案

在nodejs常见的不良做法及其优化解决方案 当涉及到在express和nodejs中开发应用程序时。遵循最佳实践对于确保项目的健壮性、可维护性和安全性至关重要。 在本文中&#xff0c;我们将探索开发人员经常遇到的几种常见的错误做法&#xff0c;并通过代码示例研究优化的最佳做法&…...

关于layui upload上传组件上传文件无反应的问题

最近使用layui upload组件时&#xff0c;碰到了上传文件无反应的问题&#xff0c;感到非常困惑。 因为使用layui upload组件不是一次两次了&#xff0c;之前每次都可以&#xff0c;这次使用同样的配方&#xff0c;同样的姿势&#xff0c;为什么就不行了呢&#xff1f; 照例先…...

容器网络之Flannel

​ 第一个问题位置变化&#xff0c;往往是通过一个称为注册中心的地方统一管理的&#xff0c;这个是应用自己做的。当一个应用启动的时候&#xff0c;将自己所在环境的 IP 地址和端口&#xff0c;注册到注册中心指挥部&#xff0c;这样其他的应用请求它的时候&#xff0c;到指挥…...

SVM(下):如何进行乳腺癌检测?

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ 🐴作者:秋无之地 🐴简介:CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作,主要擅长领域有:爬虫、后端、大数据开发、数据分析等。 🐴欢迎小伙伴们点赞👍🏻、收藏⭐️、…...

嵌入式Linux应用开发-第十五章具体单板的按键驱动程序

嵌入式Linux应用开发-第十五章具体单板的按键驱动程序 第十五章 具体单板的按键驱动程序(查询方式)15.1 GPIO操作回顾15.2 AM335X的按键驱动程序(查询方式)15.2.1 先看原理图确定引脚及操作方法15.2.2 再看芯片手册确定寄存器及操作方法15.2.3 编程15.2.3.1 程序框架15.2.3.2 硬…...

MySQL体系结构和四层架构介绍

MySQL体系结构图如下&#xff1a; 四层介绍 1. 连接层&#xff1a; 它的主要功能是处理客户端与MySQL服务器之间的连接(比如Java应用程序通过JDBC连接MySQL)。当客户端应用程序连接到MySQL服务器时&#xff0c;连接层对用户进行身份验证、建立安全连接并管理会话状态。它还处理…...

【产品运营】如何做好B端产品规划

产品规划是基于当下掌握的多维度信息&#xff0c;为追求特定目的&#xff0c;而制定的产品资源投入计划。 产品规划是基于当下掌握的多维度信息&#xff08;客户需求、市场趋势、竞争对手、竞争策略等&#xff09;&#xff0c;为追求特定目的&#xff08;商业增长、客户满意等&…...

ruoyi-启动

1 springboot 版本 git 地址 ruoyi-vue-pro: &#x1f525; 官方推荐 &#x1f525; RuoYi-Vue 全新 Pro 版本&#xff0c;优化重构所有功能。基于 Spring Boot MyBatis Plus Vue & Element 实现的后台管理系统 微信小程序&#xff0c;支持 RBAC 动态权限、数据权限…...

select完成服务器并发

服务器 #include <myhead.h>#define PORT 4399 //端口号 #define IP "192.168.0.191"//IP地址//键盘输入事件 int keybord_events(fd_set readfds); //客户端交互事件 int cliRcvSnd_events(int , struct sockaddr_in*, fd_set *, int *); //客户端连接事件 …...

初级篇—第四章聚合函数

文章目录 聚合函数介绍聚合函数介绍COUNT函数AVG和SUM函数MIN和MAX函数 GROUP BY语法基本使用使用多个列分组WITH ROLLUP HAVING基本使用WHERE和HAVING的对比开发中的选择 SELECT的执行过程查询的结构SQL 的执行原理 练习流程函数 聚合函数介绍 聚合函数作用于一组数据&#x…...

计算机图像处理-中值滤波

非线性滤波 非线性滤波是利用原始图像跟模版之间的一种逻辑关系得到结果&#xff0c;常用的非线性滤波方法有中值滤波和高斯双边滤波&#xff0c;分别对应cv2.medianBlur(src, ksize)方法和cv2.bilateralFilter(src, d, sigmaColor, sigmaSpace[, dst[, borderType]])方法。 …...

Golang中的包和模块设计

Go&#xff0c;也被称为Golang&#xff0c;是一种静态类型、编译型语言&#xff0c;因其简洁性和对并发编程的强大支持而受到开发者们的喜爱。Go编程的一个关键方面是其包和模块系统&#xff0c;它允许创建可重用、可维护和高效的代码。本博客文章将深入探讨在Go中设计包和模块…...

web:[极客大挑战 2019]Upload

题目 页面显示为一个上传&#xff0c;猜测上传一句话木马文件 先查看源代码看一下有没有有用的信息&#xff0c;说明要先上传图片&#xff0c;先尝试上传含有一句话木马的图片 构造payload <?php eval($_POST[123]);?> 上传后页面显示为&#xff0c;不能包含<&…...

ICMP差错包

ICMP报文分类 Type Code 描述 查询/差错 0-Echo响应 0 Echo响应报文 查询 3-目的不可达 0 目标网络不可达报文 差错 1 目标主机不可达报文 差错 2 目标协议不可达报文 差错 3 目标端口不可达报文 差错 4 要求分段并设置DF flag标志报文 差错 5 源路由…...

算法基础课第二部分

算法基础课 第四讲 数学知识AcWing1381. 阶乘(同余&#xff0c;因式分解) 质数AcWing 866. 质数的判定---试除法AcWing 868. 质数的判定---埃氏筛AcWing867. 分解质因数---试除法AcWing 197. 阶乘---分解质因数---埃式筛 约数AcWing 869. 求约数---试除法AcWing 870. 约数个数-…...

【数据结构】外部排序、多路平衡归并与败者树、置换-选择排序(生成初始归并段)、最佳归并树算法

目录 1、外部排序 1.1 基本概念 1.2 方法 2、多路平衡归并与败者树 2.1 K路平衡归并 2.2 败者树 3、置换-选择排序&#xff08;生成初始归并段&#xff09;​编辑 4、最佳归并树 4.1 理论基础​编辑 4.2 构造方法 ​编辑 5、各种排序算法的性质 1、外部排序 1.1 基本概…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...