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

数据结构——排序算法——桶排序

桶排序的思想是:
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;}}
}

相关文章:

数据结构——排序算法——桶排序

桶排序的思想是&#xff1a; 1.将区间划分为 n 个相同大小的子区间&#xff0c;每个子区间称为一个桶 2.遍历数组&#xff0c;将每个数字装入桶中 3.对每个桶内的数字单独排序&#xff0c;这里需要采用其他排序算法&#xff0c;如插入、归并、快排等 4.最后按照顺序将所有桶内的…...

Kafka消息发送可靠性分析

Apache Kafka是一种高吞吐量的分布式发布订阅消息系统&#xff0c;它可以处理消费者和生产者之间的所有实时数据。Kafka的主要特性包括&#xff1a;高吞吐量、可扩展性、持久性、分布式、可容错等。这些特性使得Kafka成为大规模数据处理和实时数据分析的理想选择。然而&#xf…...

如何将一个字符串转换为驼峰命名法(camel case)?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 思路⭐ 示例⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领…...

牛客网项目-第一章-笔记

牛客网项目-第一章 环境配置 java maven idea Spring Intializr 搜索jar包的网站&#xff1a;https://mvnrepository.com/ https://start.spring.io/ 缺少的aop包&#xff0c;手动在pom.xml中加入依赖 <dependency><groupId>org.springframework.boot</gro…...

CISP汇总

0x00 前言 CTF 加解密合集CTF Web合集网络安全知识库溯源相关 文中工具皆可关注 皓月当空w 公众号 发送关键字 工具 获取 本文用来整理相关CISP知识笔记 0x01 汇总...

KALILINUX MSF中kiwi(mimikatz)模块的使用

一、简介&#xff1a; kiwi模块&#xff1a;   mimikatz模块已经合并为kiwi模块&#xff1b;使用kiwi模块需要system权限&#xff0c;所以我们在使用该模块之前需要将当前MSF中的shell提升为system。 二、前权&#xff1a; 提权到system权限&#xff1a; 1.1 提到system有…...

hive 中正则表表达式使用

一 概念 概念&#xff1a;正则表达式&#xff08;Regular Expression&#xff09;&#xff0c;又称规则表达式&#xff0c;是记录文本规则的代码。通常被用来检索、替换那些符合某个模式(规则)的文本。 特性&#xff1a;最初是由Unix中的工具软件&#xff08;例如sed和grep&a…...

mssql ,数据库还原BAK命令行方式

如果数据库存在&#xff0c;离线断开 ALTER DATABASE [数据库名] SET OFFLINE WITH ROLLBACK IMMEDIATE --断开其他用户与数据库的连接正式开始还原数据库&#xff1a; USE MASTER --这里注意要使用MASTER&#xff0c;以免出现待还原库被占用的情况 RESTORE DATABASE [数据库名…...

uniapp微信小程序《隐私保护协议》弹窗处理流程

背景 《关于小程序隐私保护指引设置的公告》 《小程序隐私协议开发指南》 流程 1.第一步 必须设置且审核通过&#xff01;&#xff01;&#xff01; 2.第二步 uniapp在manifest.json中添加&#xff01;&#xff01;&#xff01; /* 在 2023年9月15号之前&#xff0c;在 ap…...

RK3568 CAN驱动更新说明

RK3568 CAN问题&#xff1a;同时收发数据一段时间&#xff08;几秒钟&#xff09;can出现错误收发功能异常&#xff0c;必须重新down、up恢复正常 内核更新rockchip_canfd.c、iopoll.h&#xff0c;配置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用法说明。 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 function写法 function的标准写法如下&#xff1a; function <返回值的类型或范围>(函数名);<端口说明语句> // in…...

runtime过程中,常见jar问题解决

io.netty java.lang.NoSuchMethodError: io.netty.buffer.PooledByteBufAllocator.<init>此类问题报错&#xff0c;主要是io.netty 多个jar 冲突导致。、 使用以下命令查看同一个jar 有哪些版本 mvn dependency:resolve -Dclassifiersources对一些不愿意引入的依赖加上…...

ElementPlus· banner轮播图实现

功能&#xff0c;①通用型&#xff0c;三方组件完成&#xff08;如&#xff0c;elementPlus&#xff09; ②自己写 轮播图 本文使用vue3中的UI框架——elementPlus——三方组件中的 <el-carousel> 实现轮播图 // 组件静态模板 <template><div class"hom…...

Linux自动化构建项目工具——Makefile/makefile

目录 一&#xff0c;背景知识 二&#xff0c;makefile/Makefile的编写 1.创建makefile/Makefile文件 2.在Makefile文件里写编译代码 3.伪目标——.PHONY 1.伪目标的特点 2.怎样实现总是被执行 4.Makefile/makefile文件的不同编写风格 1.背景知识 2.改写 一&#xff0c;背…...

第11章 字符串和字符串函数

本章介绍以下内容&#xff1a; 函数&#xff1a;gets()、gets_s()、fgets()、puts()、fputs()、strcat()、strncat()、strcmp()、strncmp()、strcpy()、strncpy()、sprintf()、strchr() 创建并使用字符串 使用C库中的字符和字符串函数&#xff0c;并创建自定义的字符串函数 使用…...

TypeScript项目配置

前言 我们需要建立tsconfig.json 作用 用于标识 TypeScript 项目的根路径&#xff1b; 用于配置 TypeScript 编译器&#xff1b; 用于指定编译的文件。 重要字段 files - 设置要编译的文件的名称&#xff1b; include - 设置需要进行编译的文件&#xff0c;支持…...

【Spring面试】二、BeanFactory与IoC容器的加载

文章目录 Q1、BeanFactory的作用是什么&#xff1f;Q2、BeanDefinition的作用是什么&#xff1f;Q3、BeanFactory和ApplicationContext有什么区别&#xff1f;Q4、BeanFactory和FactoryBean有什么区别&#xff1f;Q5、说下Spring IoC容器的加载过程&#xff08;※&#xff09;Q…...

Android嵌套事务

这时候旋转设备还是会重置秒表。旋转设备时Android会重新创建活动。如果你的活动包含一个 < fragment >元素&#xff0c;每次重新创建活动时&#xff0c;它会重新插入片段的一个新版本。老片段被丢掉&#xff0c;所有实例变量会设置其初始值。在这个特定的例子中&#xf…...

如何让项目准时上线?

项目为什么容易延期&#xff1f; 1、软件研发是一项创造性工作 项目延期是一种普遍现象&#xff0c;管理者最为头疼的一个问题。但是外人并不理解。明明是你们自己做的计划&#xff0c;怎么总会出现这么多问题。说到底&#xff0c;这是由于我们的工作特性决定的。我们做的是一…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...