排序算法之桶排序

news/2024/5/28 2:58:58/文章来源:https://blog.csdn.net/qq_45649553/article/details/137933450

目录

  • 一、简介
  • 二、代码实现
  • 三、应用场景


一、简介

算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度排序方式稳定性
桶排序O(n+k )O(n+k)O(n^2)O(n+k)Out-place稳定

稳定:如果A原本在B前面,而A=B,排序之后A仍然在B的前面;
不稳定:如果A原本在B的前面,而A=B,排序之后A可能会出现在B的后面;
时间复杂度: 描述一个算法执行所耗费的时间;
空间复杂度:描述一个算法执行所需内存的大小;
n:数据规模;
k:“桶”的个数;
In-place:占用常数内存,不占用额外内存;
Out-place:占用额外内存。

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,需要做到这两点:

在额外空间充足的情况下,尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。
什么时候最快?
当输入的数据可以均匀的分配到每一个桶中。
什么时候最慢?
当输入的数据被分配到了同一个桶中。

算法步驟:

  • 1.确定桶的数量:根据输入数据的范围和数量确定需要多少个桶。
    首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中,那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn;
    根据mx和mn确定每个桶所装的数据的范围 size,有
    size = (mx - mn) / n + 1,n为数据的个数,需要保证至少有一个桶,故而需要加个1;
    求得了size即知道了每个桶所装数据的范围,还需要计算出所需的桶的个数cnt,有
    cnt = (mx - mn) / size + 1,需要保证每个桶至少要能装1个数,故而需要加个1;
  • 2.将数据分配到各个桶中:遍历输入数据,根据数据的值将数据分配到对应的桶中。
    求得了size和cnt后,即可知第一个桶装的数据范围为 [mn, mn + size),第二个桶为 [mn + size, mn + 2 * size),…,以此类推,因此步骤2中需要再扫描一遍数组,将待排序的各个数放进对应的桶中。
  • 3.对每个桶内的数据进行排序:对每个非空的桶内的数据进行排序,可以使用插入排序等方法。
  • 4.合并各个桶的数据:按照桶的顺序将各个桶内的数据合并为最终的排序结果。

示意图
元素分布在桶中:
在这里插入图片描述
然后,元素在每个桶中排序:
在这里插入图片描述


二、代码实现

 public void bucketSort(int[] nums) {int n = nums.length;int mn = nums[0], mx = nums[0];// 找出数组中的最大最小值for (int i = 1; i < n; i++) {mn = Math.min(mn, nums[i]);mx = Math.max(mx, nums[i]);}int size = (mx - mn) / n + 1; // 每个桶存储数的范围大小,使得数尽量均匀地分布在各个桶中,保证最少存储一个int cnt = (mx - mn) / size + 1; // 桶的个数,保证桶的个数至少为1List<Integer>[] buckets = new List[cnt]; // 声明cnt个桶for (int i = 0; i < cnt; i++) {buckets[i] = new ArrayList<>();//每一个桶都是一个集合}// 扫描一遍数组,将数放进桶里for (int i = 0; i < n; i++) {int idx = (nums[i] - mn) / size;buckets[idx].add(nums[i]);}// 对各个桶中的数进行排序,这里用库函数快速排序for (int i = 0; i < cnt; i++) {buckets[i].sort(null); // 默认是按从小打到排序}// 依次将各个桶中的数据放入返回数组中int index = 0;for (int i = 0; i < cnt; i++) {for (int j = 0; j < buckets[i].size(); j++) {nums[index++] = buckets[i].get(j);}}}

demo示例一下

public class BucketSort {public static void bucketSort(int[] nums) {int n = nums.length;int mn = nums[0], mx = nums[0];// 找出数组中的最大最小值for (int i = 1; i < n; i++) {mn = Math.min(mn, nums[i]);mx = Math.max(mx, nums[i]);}int size = (mx - mn) / n + 1; // 每个桶存储数的范围大小,使得数尽量均匀地分布在各个桶中,保证最少存储一个System.out.println("每个桶的储存数量大小 " + size);int cnt = (mx - mn) / size + 1; // 桶的个数,保证桶的个数至少为1System.out.println("桶的个数 " + cnt);List<Integer>[] buckets = new List[cnt]; // 声明cnt个桶for (int i = 0; i < cnt; i++) {buckets[i] = new ArrayList<>();//每一个桶都是一个集合}for (int i = 0; i < n; i++) {int number1 = mn + i * size;int number2 = mn + (i + 1) * size;System.out.println("第" + i + "个桶存理应存放数据范围 " + number1 + "----" + number2);}// 扫描一遍数组,将数放进桶里for (int i = 0; i < n; i++) {int idx = (nums[i] - mn) / size;buckets[idx].add(nums[i]);System.out.println("第" + idx + "个桶存放了" + nums[i]);}// 对各个桶中的数进行排序,这里用库函数快速排序for (int i = 0; i < cnt; i++) {buckets[i].sort(null); // 默认是按从小打到排序}// 依次将各个桶中的数据放入返回数组中int index = 0;for (int i = 0; i < cnt; i++) {for (int j = 0; j < buckets[i].size(); j++) {nums[index++] = buckets[i].get(j);}}}public static void bucketSort2(int[] nums) {int n = nums.length;int mn = nums[0], mx = nums[0];// 找出数组中的最大最小值for (int i = 1; i < n; i++) {mn = Math.min(mn, nums[i]);mx = Math.max(mx, nums[i]);}int size = (mx - mn) / n + 1; // 每个桶存储数的范围大小,使得数尽量均匀地分布在各个桶中,保证最少存储一个int cnt = (mx - mn) / size + 1; // 桶的个数,保证桶的个数至少为1List<Integer>[] buckets = new List[cnt]; // 声明cnt个桶for (int i = 0; i < cnt; i++) {buckets[i] = new ArrayList<>();}// 扫描一遍数组,将数放进桶里for (int i = 0; i < n; i++) {int idx = (nums[i] - mn) / size;buckets[idx].add(nums[i]);}// 对各个桶中的数进行排序,这里用库函数快速排序for (int i = 0; i < cnt; i++) {buckets[i].sort(new Comparator<Integer>() {@Overridepublic int compare(Integer a, Integer b) {return b - a; // 从大到小排序}});}// 依次将各个桶中的数据放入返回数组中int index = 0;for (int i = cnt - 1; i >= 0; i--) {for (int j = 0; j < buckets[i].size(); j++) {nums[index++] = buckets[i].get(j);}}}public static void main(String[] args) {int[] nums = {12, 11, 15, 50, 7, 65, 3, 99};System.out.println("排序前 :" + Arrays.toString(nums));bucketSort(nums);System.out.println("桶排序从小到大排序后 :" + Arrays.toString(nums));bucketSort2(nums);System.out.println("桶排序从大到小排序后 :" + Arrays.toString(nums));}
}

在这里插入图片描述

三、应用场景

桶排序适用于数据量较大且分布较均匀的情况,可以在一定程度上提高排序的效率。

  • 排序整数或浮点数: 桶排序适用于排序整数或浮点数,特别是在这些数的范围不是很大的情况下。通过将数分配到不同的桶中,可以在每个桶内使用其他排序算法(如插入排序、快速排序)来对桶内的数进行排序,最终将桶中的数合并得到有序序列。
  • 均匀分布的数据: 如果输入数据是均匀分布的,即数据在不同的范围内基本均匀分布,那么桶排序的效果会很好。因为桶排序将数据分配到不同的桶中,可以保证数据在各个桶中基本均匀分布,从而减少排序的复杂度。
  • 外部排序: 桶排序也适用于外部排序,即当数据量非常大,无法一次性加载到内存中进行排序时。在外部排序中,可以将数据分成若干块,每块数据可以加载到内存中进行桶排序,然后将排序后的数据写回磁盘,最终将所有块合并得到有序序列。
  • 计数排序的扩展: 桶排序是计数排序的一种扩展,适用于更大范围的数据。当计数排序不适用于数据范围很大的情况时,桶排序可以更好地处理这种情况。

桶排序的关键点:

  • 确定桶的数量和大小:在进行桶排序之前,需要确定桶的数量和大小。桶的数量可以根据待排序数据的范围来确定,而桶的大小可以根据数据的分布情况来选择。通常情况下,桶的数量可以取数据个数的平方根或者数据范围的大小。
  • 数据分配到桶中:一旦确定了桶的数量和大小,接下来需要将待排序数据分配到对应的桶中。这通常涉及到计算每个数据在哪个桶内,可以根据数据的大小和桶的范围来确定。
  • 对每个非空桶内的数据进行排序:在桶排序中,每个非空桶内的数据需要进行排序。这可以使用任意一种排序算法,如插入排序、快速排序等。在实际应用中,通常选择适合桶内数据规模的排序算法。
  • 合并各个桶的数据:最后一步是将各个桶内的数据按照顺序合并为最终的排序结果。这通常涉及遍历所有桶,按照桶的顺序将数据合并起来。
  • 处理边界情况:在实现桶排序时,需要考虑处理一些边界情况,例如空桶的情况、数据分布不均匀的情况等。这些情况可能会影响桶排序的性能和正确性。

参考链接:
十大经典排序算法(Java实现)

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

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

相关文章

STM32F103ZET6 封装 LQFP-144 ST意法 单片机芯片

STM32F103ZET6 是意法半导体&#xff08;STMicroelectronics&#xff09;生产的一款基于 ARM Cortex-M3 内核的 32 位微控制器。它具有高性能、低功耗的特点&#xff0c;广泛应用于各种嵌入式系统和工业应用中。STM32F103ZET6 的主要特点如下&#xff1a; 内核&#xff1a;ARM…

Ubuntu 自己写的程序如何创建快捷方式

在Ubuntu中创建程序的快捷方式通常是通过将一个指向程序可执行文件的.desktop文件放入/usr/share/applications/或用户的~/.local/share/applications/目录来实现的。以下是创建快捷方式的基本步骤和示例&#xff1a; 创建一个新的.desktop文件。 在文件中填写必要的信息&…

Topaz Photo AI 3.0.0 (macOS Universal) - AI 图片修复工具

Topaz Photo AI 3.0.0 (macOS Universal) - AI 图片修复工具 Maximize Image Quality with AI 请访问原文链接&#xff1a;Topaz Photo AI 3.0.0 (macOS Universal) - AI 图片修复工具&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;sy…

基于SpringBoot的宠物领养网站管理系统

基于SpringBootVue的宠物领养网站管理系统的设计与实现~ 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBootMyBatis工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 主页 宠物领养 宠物救助站 宠物论坛 登录界面 管理员界面 摘要 基于Spr…

高中数学:三角函数之考点精华-单调性问题

一、解题方法 1、换元 2、画图 3、反向求解 参考&#xff1a;整体换元法 二、练习 例题1 解析&#xff1a; 这一题&#xff0c;比较简单&#xff0c;是标准的换元法应用题。 这里稍微注意下第二小问的对称中心&#xff0c;因为&#xff0c;B1&#xff0c;所以&#xff0c;对…

Git 分支管理

Git 分支管理 | CoderMast编程桅杆Git 分支管理 在 Git 中&#xff0c;分支是指向提交对象&#xff08;commits&#xff09;的可变指针。它们是一系列提交的引用&#xff0c;其中的每个提交都包含了一组文件的状态以及指向其父提交的指针。主要的分支通常是 master 或 main&…

1.C++入门

目录 1.C关键字 2.命名空间 作用域方面的优化 a.命名空间定义 b.命名空间使用 3.C 输入&输出 1.C关键字 C有63个关键字&#xff0c;C语言有32个关键字&#xff0c;存在重叠如荧光笔标出 2.命名空间 作用域方面的优化 如果变量&#xff0c;函数和类的名称都存在于全…

近年数一,数二难度如何,听说24是像张宇那样的题?

直接上分数&#xff01; “估分一百零几&#xff0c;平时李林130-140&#xff0c;张八110-125的样子&#xff0c;超越做的分数也是100出头。” 24学长说&#xff1a; “远离李林张八&#xff01;张四没做不评价。” “李林张八暑假前做完当作打基础即可。超越才是真题难度”…

要养生也要时尚,益百分满足你的所有需求

要养生也要时尚&#xff0c;益百分满足你的所有需求 艾灸是个好东西&#xff0c;尤其是在近几年的时候&#xff0c;艾灸就像一阵浪潮席卷进了人们的日常生活之中&#xff0c;我们可以在街边看到大大小小的艾灸馆&#xff0c;有些评价比较高的艾灸馆门前甚至还排起了长长的队伍…

数据库服务类--Redis--未授权访问终端Getshell

免责声明:本文仅做技术交流与学习. 目录 前提条件: windows上开启redis服务: Linux上创建&开启redis服务: 操作: 1-连接靶机redis 2-写入webshell 3-访问后门 redis--->webshell Redis未授权访问漏洞复现与利用 - 知乎 (zhihu.com) 前提条件: 端口开放(6379) 目录…

51单片机之DS1302实时时钟

1.DS1302时钟芯片介绍 DS1302是由美国DALLAS公司推出的具有涓细电流充电能力的低功耗实时时钟芯片。它可以对年、月、日、周、时、分、秒进行计时&#xff0c;且具有闰年补偿等多种功能RTC(Real Time Clock)&#xff1a;实时时钟&#xff0c;是一种集成电路&#xff0c;通常称…

【ARM 裸机】C 语言 led 驱动

前面刚学习了汇编 led 驱动的编写和验证&#xff0c;现在开始就要进入 C 语言 led 驱动编写与验证了 ! 1、C 语言运行环境构建 1.1、设置处理器模式 使 6ULL 处于 SVC 模式下&#xff0c;之前已经提到了处理器的九种模式&#xff0c;参考&#xff1a;【ARM 裸机】汇编 led 驱…

关基网络战时代,赛宁网安电力网络攻防靶场全面提升电网安全防护力

随着网络空间成为与陆地、海洋、天空、太空同等重要的人类活动新领域&#xff0c;自网络空间向物理电网发起攻击&#xff0c;破坏电力等国家关键基础设施成为当前大国博弈、大规模战争的重要手段和常态进攻形式。同时&#xff0c;新型电力系统建设发展驱动电力系统形态和控制方…

Linux开机启动流程

Linux开机启动流程详细步骤如下图&#xff1a; 其中&#xff1a; POST:Power On Self Test --加电自检 BIOS: Basic Input Output System --基础输入输出系统 MBR: Master Boot Record --主引导记录 GRUB: GRand Uni…

基于SSM+Vue的护工预约服务小程序和后台管理系统

1、系统演示视频&#xff08;演示视频&#xff09; 2、需要请联系

NLP大模型的训练

NLP模型的训练主要分成两步&#xff1a; 1.先进行通用任务的训练&#xff1b;无监督的样本是无穷无尽的&#xff1b; 这里列举两种&#xff1a;MLM和NSP,NSP由于在某些论文中被证明是无效的&#xff0c;所以用的少&#xff1b; MLM: 接下来会在特定任务上进行finetune>su…

如何使用 ArcGIS Pro 快速为黑白地图配色

对于某些拍摄时间比较久远的地图&#xff0c;限于当时的技术水平只有黑白的地图&#xff0c;针对这种情况&#xff0c;我们可以通过现在的地图为该地图进行配色&#xff0c;这里为大家讲解一下操作方法&#xff0c;希望能对你有所帮助。 数据来源 教程所使用的数据是从水经微…

pytorch-过拟合欠拟合

目录 1. 函数表达能力2. 模型表达能力3. 欠拟合4. 过拟合5 总结 1. 函数表达能力 如下图&#xff1a;不同次方的函数的复杂度是不一样的&#xff0c;越复杂的函数表达能力越强 2. 模型表达能力 如下图&#xff1a;有三种复杂度的模型&#xff0c;分别是8层、19层和152层&am…

OpenHarmony开发实例:【 待办事项TodoList】

简介 TodoList应用是基于OpenHarmony SDK开发的安装在润和HiSpark Taurus AI Camera(Hi3516d)开发板标准系统上的应用&#xff1b;应用主要功能是以列表的形式&#xff0c;展示需要完成的日程&#xff1b;通过本demo可以学习到 JS UI 框架List使用&#xff1b; 运行效果 样例…