排序算法之桶排序


title: 桶排序
date: 2024-7-25 18:58:19 +0800
categories:

  • 排序算法
    tags:
  • 排序
  • 算法
  • 桶排序
    description: 桶排序(bucket sort)是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶,每个桶对应一个数据范围,将数据平均分配到各个桶中;然后,在每个桶内部分别执行排序;最终按照桶的顺序将所有数据合并。
    math: true

桶排序

桶排序(Bucket Sort)是一种基于分配的排序算法。它将元素分散到不同的桶中,然后对每个桶分别进行排序,最后将桶中的元素合并起来。

桶排序的原理

桶排序适用于均匀分布在一定范围内的数值。其主要思想是:

  1. 创建若干桶:将要排序的数据分到若干个桶中。
  2. 对每个桶内的数据进行排序:桶内的排序可以使用任意排序算法。
  3. 合并所有桶中的数据:将排好序的桶中的数据合并,得到最终的有序数据。

桶排序的步骤

  1. 创建桶:根据数据范围和桶的数量,创建若干个桶。
  2. 分配数据:将数据分配到对应的桶中。
  3. 桶内排序:对每个桶中的数据进行排序。
  4. 合并数据:将所有桶中的数据按顺序合并,得到排序后的结果。

图示

桶排序

示例

以下是一个桶排序的示例,假设我们有一个浮点数数组:[0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]。

第一步:创建桶

假设我们创建10个桶,每个桶对应范围是[0, 0.1),[0.1, 0.2),[0.2, 0.3)等。

第二步:分配数据

将每个数据分配到对应的桶中:

  • 0.42 -> 桶4
  • 0.32 -> 桶3
  • 0.23 -> 桶2
  • 0.52 -> 桶5
  • 0.25 -> 桶2
  • 0.47 -> 桶4
  • 0.51 -> 桶5

第三步:桶内排序

对每个桶中的数据进行排序:

  • 桶2: [0.23, 0.25]
  • 桶3: [0.32]
  • 桶4: [0.42, 0.47]
  • 桶5: [0.51, 0.52]

第四步:合并数据

将所有桶中的数据合并:[0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

复杂度分析

桶排序适用于处理体量很大的数据。例如,输入数据包含 100 万个元素,由于空间限制,系统内存无法一次性加载所有数据。此时,可以将数据分成 1000 个桶,然后分别对每个桶进行排序,最后将结果合并。

  • 时间复杂度为 O ( n + k ) O(n + k) O(n+k) :假设元素在各个桶内平均分布,那么每个桶内的元素数量为 n k \frac{n}{k} kn 。假设排序单个桶使用 O ( n k log ⁡ n k ) O(\frac{n}{k} \log\frac{n}{k}) O(knlogkn) 时间,则排序所有桶使用 O ( n log ⁡ n k ) O(n \log\frac{n}{k}) O(nlogkn) 时间。当桶数量 k k k 比较大时,时间复杂度则趋向于 O ( n ) O(n) O(n) 。合并结果时需要遍历所有桶和元素,花费 O ( n + k ) O(n + k) O(n+k) 时间。
  • 自适应排序:在最差情况下,所有数据被分配到一个桶中,且排序该桶使用 O ( n 2 ) O(n^2) O(n2) 时间。
  • 空间复杂度为 O ( n + k ) O(n + k) O(n+k)、非原地排序:需要借助 k k k 个桶和总共 n n n 个元素的额外空间。
  • 桶排序是否稳定取决于排序桶内元素的算法是否稳定。

时间复杂度

  • 最佳情况 O ( n ) O(n) O(n)
  • 最坏情况 O ( n 2 ) O(n^2) O(n2)
  • 平均情况 O ( n + k ) O(n+k) O(n+k)

空间复杂度

  • 空间复杂度 O ( n ⋅ k ) O(n \cdot k) O(nk)

如何实现平均分配

桶排序的时间复杂度理论上可以达到 O ( n ) O(n) O(n)关键在于将元素均匀分配到各个桶中,因为实际数据往往不是均匀分布的。若将区间平均划分为 10 个,各个桶中的数据的数量差距会非常大。

为实现平均分配,我们可以先设定一条大致的分界线,将数据粗略地分到 3 个桶中。分配完毕后,再将数据较多的桶继续划分为 3 个桶,直至所有桶中的元素数量大致相等

平均分配
这种方法本质上是创建一棵递归树,目标是让叶节点的值尽可能平均。当然,不一定要每轮将数据划分为 3 个桶,具体划分方式可根据数据特点灵活选择。

如果我们提前知道数据的概率分布,则可以根据数据概率分布设置每个桶的价格分界线。值得注意的是,数据分布并不一定需要特意统计,也可以根据数据特点采用某种概率模型进行近似。

概率分配

Java代码实现

/* 桶排序 */
void bucketSort(float[] nums) {// 初始化 k = n/2 个桶,预期向每个桶分配 2 个元素int k = nums.length / 2;List<List<Float>> buckets = new ArrayList<>();for (int i = 0; i < k; i++) {buckets.add(new ArrayList<>());}// 1. 将数组元素分配到各个桶中for (float num : nums) {// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]int i = (int) (num * k);// 将 num 添加进桶 ibuckets.get(i).add(num);}// 2. 对各个桶执行排序for (List<Float> bucket : buckets) {// 使用内置排序函数,也可以替换成其他排序算法Collections.sort(bucket);}// 3. 遍历桶合并结果int i = 0;for (List<Float> bucket : buckets) {for (float num : bucket) {nums[i++] = num;}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/398119.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Qt—Qtcreator中自定义类时,下拉菜单中没有出现要继承的Qt类

问题描述&#xff1a;Qtcreator中自定义类时&#xff0c;下拉菜单中没有出现要继承的Qt类 这里我想要继承 QLineEdit 类&#xff0c;但是在这个下拉菜单中没有找到 我认为这个是qtcreator版本的问题&#xff0c;因为我直接去 #include 是可以找到这个类的 直接创建出来的类中…

Python Flask 与 Node.js Express

我的新书《Android App开发入门与实战》已于2020年8月由人民邮电出版社出版&#xff0c;欢迎购买。点击进入详情 构建 Web 应用程序时&#xff0c;选择正确的框架对于性能和可扩展性至关重要。Python 的 Flask 和 Node.js 的 Express 是两种流行的选择&#xff0c;它们根据项目…

重启人生计划-勇敢者先行

&#x1f973;&#x1f973;&#x1f973; 茫茫人海千千万万&#xff0c;感谢这一刻你看到了我的文章&#xff0c;感谢观赏&#xff0c;大家好呀&#xff0c;我是最爱吃鱼罐头&#xff0c;大家可以叫鱼罐头呦~&#x1f973;&#x1f973;&#x1f973; 如果你觉得这个【重启人生…

Go语言 Defer(延迟)

本文主要内容为Go语言中defer(延迟)介绍及应用文件读取使用defer的示例。 目录 定义 应用场景 代码示例 改为匿名函数 总结 定义 延迟&#xff1a;关键字&#xff0c;可以用于修饰语句、函数&#xff0c; 确保这条语句可以在当前栈退出的时候执行。 应用场景 1.一般用于…

SQL Server端口设置完整详细步骤

​ 大家好&#xff0c;我是程序员小羊&#xff01; 前言&#xff1a; 前面是对SQLserver服务器一些介绍&#xff0c;不想了解的可直接点击目录跳入正题&#xff0c;谢谢&#xff01;&#xff01;&#xff01; SQL Server 是由微软公司开发的关系数据库管理系统 (RDBMS)。它主要…

c++33 一级指针 字符串

拿到buf5 内存的首地址来释放内存 所以buf5不可改变 为了保证局部变量内存的局部性 字符串指针1级 如果没有拷入\0 则b还为一个数组 字符串拷贝函数 主调函数分配到内存 把g后面的内存变成\ 0 所以就改变了内存空间 考虑&#xff1a;主调用函数分配内存供被调用函数…

Python爬虫开发:BeautifulSoup、Scrapy入门

在现代网络开发中&#xff0c;网络爬虫是一个非常重要的工具。它可以自动化地从网页中提取数据&#xff0c;并且可以用于各种用途&#xff0c;如数据收集、信息聚合和内容监控等。在Python中&#xff0c;有多个库可以用于爬虫开发&#xff0c;其中BeautifulSoup和Scrapy是两个非…

FL Studio 24.1.1.4239中文破解版的安装激活详细教程

在数字音乐制作领域&#xff0c;FL Studio一直以其强大的功能和用户友好的界面而备受赞誉。随着技术的不断进步和音乐制作需求的日益增长&#xff0c;FL Studio 21.2.3的发布无疑为音乐创作者们带来了更为广阔的创作空间和更高效的制作工具。本文旨在深入探讨FL Studio 21.2.3的…

关于k8s的pvc存储卷

目录 1.PVC 和 PV 1.1 PV 1.2 PVC 1.3 StorageClass 1.4 PV和PVC的生命周期 2.实战演练 2.1 创建静态pv 2.2 创建动态pv 3.总结 1.PVC 和 PV 1.1 PV PV 全称叫做 Persistent Volume&#xff0c;持久化存储卷。它是用来描述或者说用来定义一个存储卷的&#xff0c;…

2024 年 7 月公链行业研报:市场波动中 Solana 表现抢眼,Layer 2 竞争白热化

作者&#xff1a;Stella L (stellafootprint.network) 数据来源&#xff1a;Footprint Analytics 公链 Research 页面 7 月份&#xff0c;加密货币市场表现活跃&#xff0c;波动幅度较大&#xff0c;这一现象映射了全球金融市场的整体趋势。现货以太坊 ETP 在美国的上市&…

k8s 部署RuoYi-Vue-Plus之minio搭建

1.直接部署一个pod 需要挂载存储款, 可参考 之前文章设置 https://blog.csdn.net/weimeibuqieryu/article/details/140183843 2.部署yaml 创建部署文件 minio-deploy.yaml apiVersion: v1 kind: PersistentVolume metadata:name: minio-pvnamespace: ruoyi #使用ns ruoyi s…

无字母数字webshell之命令执行

目录 1.源码 2.题目解析 3.利用方法 3.1 PHP7下如何实现 3.2PHP5下如何实现 3.2.1 shell下可以利用. 来执行任意脚本 3.2.2 Linux文件名支持用glob通配符代替 1.题目源码 <?php if(isset($_GET[code])){$code $_GET[code];if(strlen($code)>35){die(&q…

本地phpstudy部署算命系统,用户端是H5页面,支持微信支付宝支付,支持微信支付宝登录

算命系统本地部署教程 0. 技术架构1. 启动Apache、MySQL服务2. 创建前台和后台两个网站3. Navicat连接数据库4. 登录后台是长这个样子5. 登录前台登录样子6. 代码结构是 0. 技术架构 前端&#xff1a;HTMLCSSJquery 后端&#xff1a;PHP 数据库&#xff1a;MySQL 1. 启动Ap…

C# OnnxRuntime部署LivePortrait实现快速、高质量的人像驱动视频生成

目录 效果 说明 项目 模型信息 代码 下载 效果 LivePortrait实现快速、高质量的人像驱动视频生成 说明 官网地址&#xff1a;https://github.com/KwaiVGI/LivePortrait 代码实现参考&#xff1a;https://github.com/hpc203/liveportrait-onnxrun 模型下载&#xff1a;…

Haproxy简介及配置详解

一、Haproxy简介 官网&#xff1a; 企业版网站: https://www.haproxy.com 社区版网站: http://www.haproxy.org github: https://github.com/haprox Haproxy是法国人Willy Tarreaus开发的一款开源软件&#xff0c;能够提供高性能、负载均衡以及基于HTTP和TCP应用个代理&…

python-flask-上传多个文件并存储

本地环境&#xff1a;win10 / centos6 &#xff0c; python3 flask入门看这里&#xff1a; ↓ python-flask结合bootstrap实现网页小工具实例-半小时速通版_bootstrap flask-CSDN博客 https://blog.csdn.net/pxy7896/article/details/137854455 动态添加和删除表格中的行&…

【实用工具】Stirling-PDF: 优质开源的PDF处理工具/编辑工具-含入门安装教程

文章目录 项目简介功能展示Page Operations 页面操作Conversion Operations 转换操作Security & Permissions 安全与权限Other Operations 其他业务 如何安装并使用Docker RunDocker Compose 项目简介 这是一款使用 Docker 的基于本地托管网络的强大 PDF 操作工具。它能让…

头狼择校小程序

综述介绍 头狼择校&#xff0c;是头狼择™高校的简称&#xff0c;我们专注高校、大学的择校。倡导先嗅就业再择校&#xff0c;是预约工具和对话平台。帮您嗅招办、嗅教授、嗅学姐&#xff0c;预约择校有关的老师、顾问&#xff0c;助力考大学和考研的“双考”学生及家长了解就…

「OC」暑假第二周——3Gshared的仿写与学生管理系统

「OC」暑假第二周——3Gshared的仿写与学生管理系统 文章目录 「OC」暑假第二周——3Gshared的仿写与学生管理系统3Gshared登陆注册页面首页搜索推荐和活动我的我的推荐和我推荐的我的信息 设置 学生管理系统登陆注册界面主页面增删改查以及排序 总结 3Gshared 登陆注册页面 这…

【NetTopologySuite类库】创建可变距离的缓冲区

介绍 API地址 沿直线在每个顶点处创建具有不同缓冲区距离的缓冲区多边形。 只支持线作为输入&#xff0c;因为缓冲区宽度通常需要为每条线单独指定。 示例 var wkt "linestring(0 0,1 0, 2 0,3 1,4 1,5 1,6 -1,7 -1,8 -1)"; var r new WKTReader(); var g r.…