当前位置: 首页 > 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…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...