桶排序学习
2023-09-14 09:11:22 时间
转自:https://blog.csdn.net/qq_27124771/article/details/87651495
https://www.jianshu.com/p/204ed43aec0c
1.基本过程
将待排序数组按照大小分别放入N个桶,然后对各桶内数据排序,之后合并。减小总的每次排序的规模,用空间换时间。
2.关键环节
元素值域的划分,也就是元素到桶的映射规则。映射规则需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。
排序算法的选择。桶排序算法的复杂度和稳定性,都根据选择的排序算法不同而不同。
上面两个链接中给出的映射规则不同:其中一个是min/10作为间隔大小,另一个是:(max - min) / arr.length + 1。所以可以根据数据的情况来选择不同的映射规则。
3.复杂度
O(N),//还有待我分析
4.代码
public static void bucketSort(int[] arr){ // 计算最大值与最小值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } // 计算桶的数量 int bucketNum = (max - min) / arr.length + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){ bucketArr.add(new ArrayList<Integer>()); } // 将每个元素放入桶 for(int i = 0; i < arr.length; i++){ int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } // 对每个桶进行排序 for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); } // 将桶中的元素赋值到原序列 int index = 0; for(int i = 0; i < bucketArr.size(); i++){ for(int j = 0; j < bucketArr.get(i).size(); j++){ arr[index++] = bucketArr.get(i).get(j); } } }
相关文章
- Python 学习笔记 列表 排序 xxx XXX
- Python学习笔记:几种排序算法
- RabbitMQ学习笔记(五)——RabbitMQ集群搭建&入门
- 算法学习<2>---选择排序
- 机器学习常用算法:随机森林分类
- CC2541蓝牙学习——ADC
- MySQL进阶学习之SQL优化【插入,主键,排序,分组,分页,计数】
- 算法学习之路 | 希尔排序[Php]
- 推荐系统[八]算法实践总结V2:排序学习框架(特征提取标签获取方式)以及京东推荐算法精排技术实战
- c语言设计计算器-Qt学习笔记:设计一个计算器(二)
- Java的学习笔记(16)异常处理
- 让你捷足先登的深度学习框架
- Java学习笔记之十一Java中常用的8大排序算法详解总结编程语言
- 学习Oracle OEM: 手把手教学指南(oracleoem教程)
- Linux实施机器学习:开启AI新时代(linux机器学习)
- 学习嵌入式Linux,拥抱新世界(嵌入式linux学习教程)
- 深度学习(Deep Learning)发展史
- 学习Linux如何调用函数(linux调用函数)
- 使用SQLServer实现在线教学:网上学习变得更加便捷(sqlserver网课)
- 使用SQL Server学习升序排序(sqlserver 升序)
- MySQL教程学习如何在MySQL中进行上升排序(mysql上升排序)
- 千峰谱记学习 Redis 尽在其中(千峰redis笔记)
- 谷歌研究院在化学发力:应用机器学习技术预测分子性质
- oracle触发器学习笔记
- PHP数组学习排序全接触
- python算法学习之桶排序算法实例(分块排序)