JAVA十大排序算法之桶排序详解
作者:阿粤Ayue 发布时间:2022-11-08 01:07:47
桶排序
桶排序是计数排序的升级,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过函数的某种映射关系,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序),最后将非空桶中的元素逐个放入原序列中。
桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。
代码实现
1.找出数组中的最大值max和最小值min,可以确定出数组所在范围min~max
2.根据数据范围确定桶的数量
1.若桶的数量太少,则桶排序失效
2.若桶的数量太多,则有的桶可能,没有数据造成空间浪费
所以桶的数量由我们自己来确定,但尽量让元素平均分布到每一个桶里,这里提供一个方式
(最大值 - 最小值)/每个桶所能放置多少个不同数值+1
3.确定桶的区间,一般是按照(最大值 - 最小值)/桶的数量来划分的,且左闭右开
public class BucketSort {
public static final int[] ARRAY = {35, 23, 48, 9, 16, 24, 5, 11, 32, 17};
/**
* @param bucketSize 作为每个桶所能放置多少个不同数值,即数值的类型
* 例如当BucketSize==5时,该桶可以存放{1,2,3,4,5}这几种数字,
* 但是容量不限,即可以存放100个3
*/
public static List<Integer> sort(List<Integer> array, int bucketSize) {
if (array == null || array.size() < 2)
return array;
int max = array.get(0), min = array.get(0);
// 找到最大值最小值
for (int i = 0; i < array.size(); i++) {
if (array.get(i) > max)
max = array.get(i);
if (array.get(i) < min)
min = array.get(i);
}
//获取桶的数量
int bucketCount = (max - min) / bucketSize + 1;
//构建桶,初始化
List<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
List<Integer> resultArr = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
bucketArr.add(new ArrayList<>());
}
//将原数组的数据分配到桶中
for (int i = 0; i < array.size(); i++) {
//区间范围
bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
}
for (int i = 0; i < bucketCount; i++) {
if (bucketSize == 1) {
for (int j = 0; j < bucketArr.get(i).size(); j++)
resultArr.add(bucketArr.get(i).get(j));
} else {
if (bucketCount == 1)
bucketSize--;
//对桶中的数据再次用桶进行排序
List<Integer> temp = sort(bucketArr.get(i), bucketSize);
for (int j = 0; j < temp.size(); j++)
resultArr.add(temp.get(j));
}
}
return resultArr;
}
public static void print(List<Integer> array) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println("");
}
public static void main(String[] args) {
print(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()));
System.out.println("============================================");
print(sort(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()), 2));
}
}
时间复杂度
桶排序算法遍历了2次原始数组,运算量为2N,最后,遍历桶输出排序结果的运算量为N,初始化桶的运算量为M。
对桶进行排序,不同的排序算法算法复杂度不同,冒泡排序算法复杂度为O(N^2),堆排序、归并排序算法复杂度为O(NlogN),我们以排序算法复杂度为O(NlogN)进行计算,运算量为N/M * log(N/M) * M
最终的运算量为3N+M+N/M * log(N/M) * M,即3N+M+N(logN-logM),去掉系数,时间复杂度为O(N+M+N(logN-logM))
算法稳定性
桶排序算法在对每个桶进行排序时,若选择稳定的排序算法,则排序后,相同元素的位置不会发生改变,所以桶排序算法是一种稳定的排序算法。
来源:https://blog.csdn.net/weixin_43477531/article/details/119821587
猜你喜欢
- 首先给出一段代码:public class AslistMethod { public static void main(String[]
- 一、线程的优先级别线程优先级别的使用范例:package cn.galc.test;public class TestThread6 { p
- Activiti 介绍Activiti是一个开源的工作流引擎,它实现了BPMN 2.0规范,可以发布设计好的流程定义,并通过api进行流程调
- Jackson反序列化遇到的问题最近在项目中需要使用Jackson把前台转来的字符转为对象,转换过程中发生了错误,报错如下com.faste
- 前言在阅读本文之前, 希望你可以思考一下下面几个问题, 带着问题去阅读文章会获得更好的效果。发送消息的时候, 当Broker挂掉了,消息体还
- Mybatis Plus流式查询mybatis plus 中自定义如下接口,就可以实现流式查询,mybatis 中同样适用。@Select(
- 本文实例讲述了C++实现的链表类。分享给大家供大家参考。具体如下:#include <iostream>using namesp
- 一、堆排序1、什么是堆排序(1)堆排序:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构
- 前言在上网的时候我们常常遇到文件上传的情况,例如上传头像、上传资料等;当然除了上传,遇见下载的情况也很多,接下来看看我们 servlet 中
- SpringBoot分离打Jar包的两种方式方式一:基于maven-jar-plugin此方式基于这个小伙伴的配置改的:https://ww
- MD5加密简介哈希算法又称散列算法,是将任何数据转换成固定长度的算法的统称。 从本质上讲,MD5也是一种哈希算法,其输出是生成12
- 推荐阅读idea官网下载链接(对应版本号下载):https://www.jetbrains.com/idea/download/other.
- 本篇紧接上一篇内容继续,还是从继承里的细节开始1.代码块初始化关于代码块的定义和使用因为之前已经进行过介绍,所以这里就不再赘述,我们所关注的
- 一、问题描述在使用idea Jrebel续期的时候,修改idea激活服务器地址时,遇到报错:Cannot reactivate, offli
- 本文实例讲述了Java设计模式之抽象工厂模式。分享给大家供大家参考,具体如下:具体工厂类:生产创建某一类具体产品对象。抽象产品类可以使用接口
- 本文实例为大家分享了android TextView跑马灯效果的具体代码,供大家参考,具体内容如下一、要点设置四个属性android:sin
- 本文实例为大家分享了java音乐播放器的具体代码,供大家参考,具体内容如下源码:package baidu;import java.awt.
- this:this理解为:当前对象 或 当前正在创建的对象可以调用的结构:属性、方法;构造器this调用属性、方法:先了解一下形参:形参的意
- 首先对于一个SpringBoot工程来说,最明显的标志的就是 @SpringBootApplication它标记了这是一个SpringBoo
- 1.idea新建Maven项目Mybatis-study 将项目里的src文件夹删掉 依次将此项目作为父项目2.在Mybatis-study