数据结构——排序算法——桶排序
桶排序的思想是:
1.将区间划分为 n 个相同大小的子区间,每个子区间称为一个桶
2.遍历数组,将每个数字装入桶中
3.对每个桶内的数字单独排序,这里需要采用其他排序算法,如插入、归并、快排等
4.最后按照顺序将所有桶内的数字合并起来
桶排序在实际工作中的应用较少,不仅因为它需要借助于其他排序算法,还因为桶排序算法基于一个假设:所有输入数据都服从均匀分布,也就是说输入数据应该尽可能地均匀分布在每个桶中。只有这个假设成立时,桶排序运行效率才比较高。
在最差的情况下,所有数据都会被装入同一个桶中,此时桶排序算法只会徒增一轮遍历。
使用桶排序算法时,我们需要考虑两个因素
1.设置多少个桶比较合适
2.桶采用哪种数据结构
这两个因素会直接影响到桶排序的内存和效率
1.桶的数量:桶的数量过少,会导致单个桶内的数字过多,桶排序的时间复杂度就会在很大程度上受桶内排序算法的影响。桶的数量过多,占用的内存就会较大,并且会出现较多的空桶,影响遍历桶的效率。具体设置多少个桶需要根据实际情况决定。
2.桶的数据结构: 如果将桶的数据结构设置为数组,那么每个桶的长度必须设置为待排序数组的长度,因为我们需要做好最坏的打算,即所有的数字都被装入了同一个桶中,所以这种方案的空间复杂度会很高。那么是不是将桶的数据结构设置为链表就更好呢?使用链表有一个好处,即所有桶的总长度刚好等于待排序数组的长度,不会造成内存浪费。但使用链表也会有一些问题,我们待会一一分析。
// 桶排序函数
void bucketSort(std::vector<int>& arr) {int max = *std::max_element(arr.begin(), arr.end()); // 找到数组中的最大值int min = *std::min_element(arr.begin(), arr.end()); // 找到数组中的最小值int range = max - min + 1; // 确定桶的范围// 创建链表桶std::vector<std::list<int>> buckets(range);// 将元素分布到桶中for (int num : arr) {buckets[num - min].push_back(num);}// 对每个桶中的元素进行排序(使用数组排序)for (std::list<int>& bucket : buckets) {if (!bucket.empty()) {std::vector<int> temp(bucket.begin(), bucket.end()); // 将链表元素复制到临时数组std::sort(temp.begin(), temp.end()); // 对临时数组进行排序std::copy(temp.begin(), temp.end(), bucket.begin()); // 将排序后的结果复制回链表}}// 合并排序后的桶内容以获得最终结果int index = 0;for (const std::list<int>& bucket : buckets) {for (int num : bucket) {arr[index++] = num;}}
}
相关文章:
数据结构——排序算法——桶排序
桶排序的思想是: 1.将区间划分为 n 个相同大小的子区间,每个子区间称为一个桶 2.遍历数组,将每个数字装入桶中 3.对每个桶内的数字单独排序,这里需要采用其他排序算法,如插入、归并、快排等 4.最后按照顺序将所有桶内的…...
Kafka消息发送可靠性分析
Apache Kafka是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者和生产者之间的所有实时数据。Kafka的主要特性包括:高吞吐量、可扩展性、持久性、分布式、可容错等。这些特性使得Kafka成为大规模数据处理和实时数据分析的理想选择。然而…...
如何将一个字符串转换为驼峰命名法(camel case)?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 思路⭐ 示例⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领…...
牛客网项目-第一章-笔记
牛客网项目-第一章 环境配置 java maven idea Spring Intializr 搜索jar包的网站:https://mvnrepository.com/ https://start.spring.io/ 缺少的aop包,手动在pom.xml中加入依赖 <dependency><groupId>org.springframework.boot</gro…...
CISP汇总
0x00 前言 CTF 加解密合集CTF Web合集网络安全知识库溯源相关 文中工具皆可关注 皓月当空w 公众号 发送关键字 工具 获取 本文用来整理相关CISP知识笔记 0x01 汇总...
KALILINUX MSF中kiwi(mimikatz)模块的使用
一、简介: kiwi模块: mimikatz模块已经合并为kiwi模块;使用kiwi模块需要system权限,所以我们在使用该模块之前需要将当前MSF中的shell提升为system。 二、前权: 提权到system权限: 1.1 提到system有…...
hive 中正则表表达式使用
一 概念 概念:正则表达式(Regular Expression),又称规则表达式,是记录文本规则的代码。通常被用来检索、替换那些符合某个模式(规则)的文本。 特性:最初是由Unix中的工具软件(例如sed和grep&a…...
mssql ,数据库还原BAK命令行方式
如果数据库存在,离线断开 ALTER DATABASE [数据库名] SET OFFLINE WITH ROLLBACK IMMEDIATE --断开其他用户与数据库的连接正式开始还原数据库: USE MASTER --这里注意要使用MASTER,以免出现待还原库被占用的情况 RESTORE DATABASE [数据库名…...
uniapp微信小程序《隐私保护协议》弹窗处理流程
背景 《关于小程序隐私保护指引设置的公告》 《小程序隐私协议开发指南》 流程 1.第一步 必须设置且审核通过!!! 2.第二步 uniapp在manifest.json中添加!!! /* 在 2023年9月15号之前,在 ap…...
RK3568 CAN驱动更新说明
RK3568 CAN问题:同时收发数据一段时间(几秒钟)can出现错误收发功能异常,必须重新down、up恢复正常 内核更新rockchip_canfd.c、iopoll.h,配置Networking support --->CAN bus subsystem support --->CAN Devic…...
day47:C++ day7,异常处理、using的第三种用法、类型转换、lambda表达式、STL标准模板库
my_vectoers.h: #ifndef MY_VECTORS_H #define MY_VECTORS_H #include <iostream>using namespace std;template<typename TYPE> class my_vectors { private:TYPE* ptr;int num;int cnum;TYPE* start_ptrNULL;TYPE* end_ptrNULL; public://无参构造my_vectors(){…...
function—— Verilog的函数
文章目录 前言function写法语法举例说明调用 前言 function用法说明。 提示:以下是本篇文章正文内容,下面案例可供参考 function写法 function的标准写法如下: function <返回值的类型或范围>(函数名);<端口说明语句> // in…...
runtime过程中,常见jar问题解决
io.netty java.lang.NoSuchMethodError: io.netty.buffer.PooledByteBufAllocator.<init>此类问题报错,主要是io.netty 多个jar 冲突导致。、 使用以下命令查看同一个jar 有哪些版本 mvn dependency:resolve -Dclassifiersources对一些不愿意引入的依赖加上…...
ElementPlus· banner轮播图实现
功能,①通用型,三方组件完成(如,elementPlus) ②自己写 轮播图 本文使用vue3中的UI框架——elementPlus——三方组件中的 <el-carousel> 实现轮播图 // 组件静态模板 <template><div class"hom…...
Linux自动化构建项目工具——Makefile/makefile
目录 一,背景知识 二,makefile/Makefile的编写 1.创建makefile/Makefile文件 2.在Makefile文件里写编译代码 3.伪目标——.PHONY 1.伪目标的特点 2.怎样实现总是被执行 4.Makefile/makefile文件的不同编写风格 1.背景知识 2.改写 一,背…...
第11章 字符串和字符串函数
本章介绍以下内容: 函数:gets()、gets_s()、fgets()、puts()、fputs()、strcat()、strncat()、strcmp()、strncmp()、strcpy()、strncpy()、sprintf()、strchr() 创建并使用字符串 使用C库中的字符和字符串函数,并创建自定义的字符串函数 使用…...
TypeScript项目配置
前言 我们需要建立tsconfig.json 作用 用于标识 TypeScript 项目的根路径; 用于配置 TypeScript 编译器; 用于指定编译的文件。 重要字段 files - 设置要编译的文件的名称; include - 设置需要进行编译的文件,支持…...
【Spring面试】二、BeanFactory与IoC容器的加载
文章目录 Q1、BeanFactory的作用是什么?Q2、BeanDefinition的作用是什么?Q3、BeanFactory和ApplicationContext有什么区别?Q4、BeanFactory和FactoryBean有什么区别?Q5、说下Spring IoC容器的加载过程(※)Q…...
Android嵌套事务
这时候旋转设备还是会重置秒表。旋转设备时Android会重新创建活动。如果你的活动包含一个 < fragment >元素,每次重新创建活动时,它会重新插入片段的一个新版本。老片段被丢掉,所有实例变量会设置其初始值。在这个特定的例子中…...
如何让项目准时上线?
项目为什么容易延期? 1、软件研发是一项创造性工作 项目延期是一种普遍现象,管理者最为头疼的一个问题。但是外人并不理解。明明是你们自己做的计划,怎么总会出现这么多问题。说到底,这是由于我们的工作特性决定的。我们做的是一…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
