当前位置: 首页 > 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;这是由于我们的工作特性决定的。我们做的是一…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

Modbus RTU与Modbus TCP详解指南

目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...

使用python进行图像处理—图像滤波(5)

图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值&#xff0c;以达到平滑&#xff08;去噪&#xff09;、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算&#xff0c;…...

标注工具核心架构分析——主窗口的图像显示

&#x1f3d7;️ 标注工具核心架构分析 &#x1f4cb; 系统概述 主要有两个核心类&#xff0c;采用经典的 Scene-View 架构模式&#xff1a; &#x1f3af; 核心类结构 1. AnnotationScene (QGraphicsScene子类) 主要负责标注场景的管理和交互 &#x1f527; 关键函数&…...

Redis专题-实战篇一-基于Session和Redis实现登录业务

GitHub项目地址&#xff1a;https://github.com/whltaoin/redisLearningProject_hm-dianping 基于Session实现登录业务功能提交版本码&#xff1a;e34399f 基于Redis实现登录业务提交版本码&#xff1a;60bf740 一、导入黑马点评后端项目 项目架构图 1. 前期阶段2. 后续阶段导…...