网站首页 > java教程 正文
Java排序算法之桶排序详解
概念:桶排序是将数组中的元素放到一个一个的桶中,每个桶(bucket)代表一个区间,里面可以承载一个或者多个元素。然后将桶内的元素进行排序,再按顺序遍历桶,输出桶内元素。
时间复杂度:O(n+m+n(logn-logm)) (n代表数组长度,m代表桶数,当n=m时,时间复杂度为O(n))
空间复杂度:O(m+n)
缺点:如果数组中除了最后一个元素全部都在第一个桶中,那么查询的时间复杂度会退化为O(nlogn),而且中间白白创建了许多空桶。
代码实现(java)
public static void main(String[] args) {
double[] arr = new double[]{4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09};
bucketSort(arr);
for (double v : arr) {
System.out.println(v);
}
}
public static void bucketSort(double[] arr) {
//1.取出数组中的最大值和最小值
double max = Double.MIN_VALUE;
double min = Double.MAX_VALUE;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
//2.初始化桶
//桶的数量
int bucketNum = arr.length;
//每个桶的区间跨度
double span = (max - min + 1) / bucketNum;
ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);
//在桶列表中添加元素个数的空桶
for (int i = 0; i < bucketNum; i++) {
bucketList.add(new LinkedList<Double>());
}
//3.遍历原始数组,将每个元素放入桶中
for (int i = 0; i < arr.length; i++) {
//获取桶的下标
int num = (int) Math.floor((arr[i] - min) / span);//这里计算的结果是第几个桶,用Math.floor取到桶的下标,比如计算结果是2.5,说明应该放到第三个桶中,下标为2
bucketList.get(num).add(arr[i]);
}
//4.对桶内元素进行排序
for (int i = 0; i < bucketList.size(); i++) {
Collections.sort(bucketList.get(i));
}
//5.输出全部元素
double[] sortArray = new double[arr.length];
int index = 0;
for (LinkedList<Double> list : bucketList) {
for (Double aDouble : list) {
sortArray[index] = aDouble;
index++;
}
}
}
时间复杂度:假设数组长度为n,桶数为m
- 第一步求数列最大最小值,运算量为n。
- 第二步创建空桶,运算量为m。
- 第三步遍历原始数列,运算量为n。
- 第四步在每个桶内部做排序,由于使用了O(nlogn)的排序算法,所以运算量为 n/m* log(n/m ) * m。
- 第五步输出排序数列,运算量为n。加起来,总的运算量为 3n+m+n/m* log(n/m ) * m = 3n+m+n(logn-logm) 。
去掉系数,时间复杂度为:O(n+m+n(logn-logm)) 当n=m时,时间复杂度可以达到O(N)
空间复杂度:空桶占用的空间 + 数列在桶中占用的空间 = O(m+n)
- 上一篇: Java算法合集:Java数组之冒泡排序
- 下一篇: java数组元素排序,冒泡排序和选择排序
猜你喜欢
- 2024-10-22 Java几种排序方式(java排序的方法有哪些)
- 2024-10-22 Java排序算法——归并排序(Merge Sort)
- 2024-10-22 Java 集合中的排序算法浅析(java集合排序工具类)
- 2024-10-22 数组排序与二分查找法(二分查找排序树)
- 2024-10-22 LeetCode基础算法题第85篇:求有序数组的平方再排序
- 2024-10-22 Java中Arrays的两种排序方法(sort和parallelSort)比较
- 2024-10-22 深入理解Java中Comparable和Comparator排序
- 2024-10-22 Java常见知识之冒泡排序#冒泡排序
- 2024-10-22 Java数组之Arrays方法(java array数组)
- 2024-10-22 常用集合的排序方法——Java进阶知识讲义系列(七)
你 发表评论:
欢迎- 最近发表
- 标签列表
-
- java反编译工具 (77)
- java反射 (57)
- java接口 (61)
- java随机数 (63)
- java7下载 (59)
- java数据结构 (61)
- java 三目运算符 (65)
- java对象转map (63)
- Java继承 (69)
- java字符串替换 (60)
- 快速排序java (59)
- java并发编程 (58)
- java api文档 (60)
- centos安装java (57)
- java调用webservice接口 (61)
- java深拷贝 (61)
- 工厂模式java (59)
- java代理模式 (59)
- java.lang (57)
- java连接mysql数据库 (67)
- java重载 (68)
- java 循环语句 (66)
- java反序列化 (58)
- java时间函数 (60)
- java是值传递还是引用传递 (62)
本文暂时没有评论,来添加一个吧(●'◡'●)