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

数据结构之基数排序

  基数排序的思想是按组成关键字的各个数位的值进行排序,它是分配排序的一种。在该排序方法中把一个关键字 Ki看成一个 d 元组,即
      K1i,K2i,···,Kdi
其中,0≤ Kji<r,i=1~ n,j=1~d。这里的r 称为基数。若关键字是十进制的,则r=10; 若关键字是八进制的,则r=8。d是关键字的位数,d 值取所有待排序的关键字位数的最大值,其他不足d位的关键字在前面补零。
  在“K1i,K2i,···,Kdi”中,K1i称为最高有效位,K2i称为次高有效位,Kdi称为最低有效位。基数排序可以从最高有效位开始,也可以从最低有效位开始。
  基数排序的基本思想是: 设立r个队列,队列的编号分别为 0、1、2、···、r-1。首先按最低有效位的值把 n 个关键字分配到这个队列中;然后按照队列编号从小到大将各队列中的关键字依次收集起来;接着再按次低有效位的值把刚收集起来的关键字分配到r个队列中。重复上述分配和收集过程,直到按照最高有效位分配和收集。这样就得到了一个从小到大有序的关键字序列。为了减少记录移动的次数,队列可以采用链式存储分配。每个链队列设两个指针,分别指向队头和队尾。
  基数排序是一种稳定的排序方法。对于 n 个记录,执行一次分配和收集的时间为 O(n+r)。如果关键字有 d位,则要执行 d遍。所以总的运算时间为 O(d(n+r))。可见,对于不同的基数r,所用的时间是不同的。当r或d 较小时,这种排序方法较为节省时间。另外,基数排序适用干链式分配的记录的排序,其要求的附加存储量是r个队列的头、尾指针,所以附加存储量为 2r个存储单元。由于待排序记录是以链表方式存储的,相对于顺序分配而言,还增加了n 个指针域的空间。

相关文章:

数据结构之基数排序

基数排序的思想是按组成关键字的各个数位的值进行排序&#xff0c;它是分配排序的一种。在该排序方法中把一个关键字 Ki看成一个 d 元组&#xff0c;即       K1i,K2i,,Kdi 其中&#xff0c;0≤ Kji<r&#xff0c;i1~ n&#xff0c;j1~d。这里的r 称为基数。若关键字是…...

区间dp 笔记

区间dp一般是先枚举区间长度&#xff0c;再枚举左端点&#xff0c;再枚举分界点&#xff0c;时间复杂度为 环形石子合并 将 n 堆石子绕圆形操场排放&#xff0c;现要将石子有序地合并成一堆。 规定每次只能选相邻的两堆合并成新的一堆&#xff0c;并将新的一堆的石子数记做该…...

MySQL-SQL优化

文章目录 1. SQL性能分析1.1 SQL执行频率1.2 慢查询日志1.3 profile详情1.4 explain 2. SQL优化2.1 Insert 优化2.2 Group By 优化2.3 Order By 优化2.4 Limit 优化2.5 Count() 优化2.6 Update 优化 3. 拓展3.1 请你说一下MySQL中的性能调优的方法&#xff1f;3.2 执行 SQL 响应…...

详细了解ref和reactive.

这几天看到好多文章标题都是类似于&#xff1a; 不用 ref 的 xx 个理由不用 reactive 的 xx 个理由历数 ref 的 xx 宗罪 我就很不解&#xff0c;到底是什么原因导致有这两批人&#xff1a; 抵触 ref 的人抵触 reactive 的人 看了这些文章&#xff0c;我可以总结出他们的想法…...

使用Linux docker方式快速安装Plik并结合内网穿透实现公网访问

文章目录 1. Docker部署Plik2. 本地访问Plik3. Linux安装Cpolar4. 配置Plik公网地址5. 远程访问Plik6. 固定Plik公网地址7. 固定地址访问Plik 本文介绍如何使用Linux docker方式快速安装Plik并且结合Cpolar内网穿透工具实现远程访问&#xff0c;实现随时随地在任意设备上传或者…...

Redis Centos7 安装到启动

文章目录 安装Redis启动redis查看redis状况连接redis服务端 安装Redis 1.下载scl源 yum install centos-release-scl-rh2.下载redis yum install rh-redis5-redis 3. 创建软连接 1.cd /usr/bin 2. In -s /opt/rh/rh-redis5/root/usr/bin/redis-server ./redis-server 3. …...

「数据结构」二叉搜索树1:实现BST

&#x1f387;个人主页&#xff1a;Ice_Sugar_7 &#x1f387;所属专栏&#xff1a;Java数据结构 &#x1f387;欢迎点赞收藏加关注哦&#xff01; 实现BST &#x1f349;二叉搜索树的性质&#x1f349;实现二叉搜索树&#x1f34c;插入&#x1f34c;查找&#x1f34c;删除 &am…...

可达鸭二月月赛——基础赛第六场(周五)题解,这次四个题的题解都在这一篇文章内,满满干货,含有位运算的详细用法介绍。

姓名 王胤皓 T1 题解 T1 题面 T1 思路 样例输入就是骗人的&#xff0c;其实直接输出就可以了&#xff0c;输出 Hello 2024&#xff0c;注意&#xff0c;中间有一个空格&#xff01; T1 代码 #include<bits/stdc.h> using namespace std; #define ll long long int …...

ELFK日志采 - QuickStart

文章目录 架构选型ELKEFLK ElasticsearchES集群搭建常用命令 Filebeat功能介绍安装步骤Filebeat配置详解filebeat常用命令 Logstash功能介绍安装步骤Input插件Filter插件Grok Filter 插件Mutate Filter 插件常见的插件配置选项&#xff1a;Mutate Filter配置案例&#xff1a; O…...

微信小程序的图片色彩分析,窃取网络图片的主色调

1、安装 Mini App Color Thief 包 包括下载包&#xff0c;简单使用都有&#xff0c;之前写了&#xff0c;这里就不写了 网址&#xff1a;微信小程序的图片色彩分析&#xff0c;窃取主色调&#xff0c;调色板-CSDN博客 2、 问题和解决方案 问题&#xff1a;由于我们的窃取图片的…...

Leetcode 121 买卖股票的最佳时机

题意理解&#xff1a; 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交…...

SQL语言复习-----1

1&#xff0c;前言 SQL是计算机的一门基础语言&#xff0c;无论在开发还是数据库管理上都是非常重要&#xff0c;最近总结归纳了一下相关知识&#xff0c;记录如下。 2&#xff0c;归纳 SQL是结构化查询语言。 关系数据库有三级模式结构。 基本表和视图一样都是关系。 举例…...

爬虫2—用爬虫爬取壁纸(想爬多少张爬多少张)

先看效果图&#xff1a; 我这个是爬了三页的壁纸60张。 上代码了。 import requests import re import os from bs4 import BeautifulSoupcount0 img_path "./壁纸图片/"#指定保存地址 if not os.path.exists(img_path):os.mkdir(img_path) headers{ "User-Ag…...

学习Android的第九天

目录 Android Button 按钮 基本的按钮 StateListDrawable 范例 使用颜色值绘制圆角按钮 自制水波纹效果 Android ImageButton 图片按钮 ImageButton 不同状态下的 ImageButton Android RadioButton 单选按钮 RadioButton 获得选中的值 Android Button 按钮 在 And…...

课时21:内置变量_脚本相关

2.4.1 脚本相关 学习目标 这一节&#xff0c;我们从 基础知识、简单实践、小结 三个方面来学习 基础知识 脚本相关的变量解析 序号变量名解析1$0获取当前执行的shell脚本文件名2$n获取当前执行的shell脚本的第n个参数值&#xff0c;n1…9&#xff0c;当n为0时表示脚本的文…...

ubuntu22.04@laptop OpenCV Get Started: 006_annotating_images

ubuntu22.04laptop OpenCV Get Started: 006_annotating_images 1. 源由2. line/circle/rectangle/ellipse/text 应用Demo3 image_annotation3.1 C应用Demo3.2 Python应用Demo3.3 重点过程分析3.3.1 划线3.3.2 画圆3.3.3 矩形3.3.4 椭圆3.3.5 文字 4. 总结5. 参考资料 1. 源由 …...

【制作100个unity游戏之23】实现类似七日杀、森林一样的生存游戏10(附项目源码)

本节最终效果演示 文章目录 本节最终效果演示系列目录前言快捷栏绘制UI代码控制快捷列表信息 源码完结 系列目录 前言 欢迎来到【制作100个Unity游戏】系列&#xff01;本系列将引导您一步步学习如何使用Unity开发各种类型的游戏。在这第23篇中&#xff0c;我们将探索如何制作…...

uniapp vue3怎么调用uni-popup组件的this.$refs.message.open() ?

vue2代码 <!-- 提示信息弹窗 --><uni-popup ref"message" type"message"><uni-popup-message :type"msgType" :message"messageText" :duration"2000"></uni-popup-message></uni-popup>typ…...

【深度学习:语义分割】语义分割简介

【深度学习&#xff1a;语义分割】语义分割简介 什么是图像分割&#xff1f;了解语义分割数据采集语义分割的深度学习实现全卷积网络上采样跳跃连接U-NetDeepLab多尺度物体检测金字塔场景解析网络&#xff08;PSPNet&#xff09; 语义分割的应用医学影像自动驾驶汽车农业图片处…...

前端开发_AJAX基本使用

AJAX概念 AJAX是异步的JavaScript和XML(Asynchronous JavaScript And XML)。 简单点说&#xff0c;就是使用XMLHttpRequest对象与服务器通信。 它可以使用JSON&#xff0c;XML&#xff0c;HTML和text文本等格式发送和接收数据。 AJAX最吸引人的就是它的“异步"特性&am…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...