package com.rao.sort; import java.util.*; /**
* @author Srao
* @className BucketSort
* @date 2019/12/10 17:42
* @package com.rao.sort
* @Description 桶排序
*/
public class BucketSort { /**
* 桶排序
* @param arr
* @return
*/
public static double[] bucketSort(double[] arr){
//1.计算出最大值和最小值,求出两者的差值
double min = arr[];
double max = arr[];
for (int i = ; i < arr.length; i++) {
if (max < arr[i]){
max = arr[i];
}
if (arr[i] < min){
min = arr[i];
}
}
double d = max - min; //2.初始化桶
int bucketNum = arr.length;
List<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
for (int i = ; i < bucketNum; i++) {
bucketList.add(new LinkedList<>());
} //3.遍历数组中的元素,把所有元素都放入对应的桶当中
for (int i = ; i < arr.length; i++) {
//计算当前元素应该放在哪个桶里面
int num = (int)((arr[i] - min) / (d / (bucketNum - )));
bucketList.get(num).add(arr[i]);
} //4.对每个桶里面的元素进行排序
for (int i = ; i < bucketNum; i++) {
Collections.sort(bucketList.get(i));
} //5.输出全部元素
int k = ;
for(LinkedList<Double> doubles : bucketList){
for (Double aDouble : doubles) {
arr[k] = aDouble;
k++;
}
} return arr;
} 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};
System.out.println(Arrays.toString(arr));
arr = bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
}
桶排序可以看作是对计数排序的改进,计数排序对于数值在一定范围的整数数组可以进行排序,但是对于小数的数组却没有办法计数,这时候就要用到桶排序。
桶排序是将数组中的数划分到不同的区间,再对每个桶中的数进行排序,这时用的排序算法一般为快速排序或者归并排序,然后再把所有桶中的数返回给原数组。
排序算法-桶排序(Java)的更多相关文章
-
使用 js 实现十大排序算法: 桶排序
使用 js 实现十大排序算法: 桶排序 桶排序 refs xgqfrms 2012-2020 www.cnblogs.com 发布文章使用:只允许注册用户才可以访问!
-
线性时间的排序算法--桶排序(以leetcode164. Maximum Gap为例讲解)
前言 在比较排序的算法中,快速排序的性能最佳,时间复杂度是O(N*logN).因此,在使用比较排序时,时间复杂度的下限就是O(N*logN).而桶排序的时间复杂度是O(N+C),因为它的实现并不是基于 ...
-
Java排序算法——桶排序
文字部分为转载:http://hxraid.iteye.com/blog/647759 对N个关键字进行桶排序的时间复杂度分为两个部分: (1) 循环计算每个关键字的桶映射函数,这个时间复杂度是O(N ...
-
计数排序和桶排序(Java实现)
目录 比较和非比较的区别 计数排序 计数排序适用数据范围 过程分析 桶排序 网络流传桶排序算法勘误 桶排序适用数据范围 过程分析 比较和非比较的区别 常见的快速排序.归并排序.堆排序.冒泡排序等属于比 ...
-
排序算法总结及Java实现
1. 整体介绍 分类 排序大的分类可以分为两种,内排序和外排序.在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序.主要需要理解的都是内排序算法: 内排序可以分为 ...
-
常见排序算法题(java版)
常见排序算法题(java版) //插入排序: package org.rut.util.algorithm.support; import org.rut.util.algorithm.Sor ...
-
八大排序算法总结与java实现(转)
八大排序算法总结与Java实现 原文链接: 八大排序算法总结与java实现 - iTimeTraveler 概述 直接插入排序 希尔排序 简单选择排序 堆排序 冒泡排序 快速排序 归并排序 基数排序 ...
-
排序算法总结(基于Java实现)
前言 下面会讲到一些简单的排序算法(均基于java实现),并给出实现和效率分析. 使用的基类如下: 注意:抽象函数应为public的,我就不改代码了 public abstract class Sor ...
-
第二章:排序算法 及其他 Java代码实现
目录 第二章:排序算法 及其他 Java代码实现 插入排序 归并排序 选择排序算法 冒泡排序 查找算法 习题 2.3.7 第二章:排序算法 及其他 Java代码实现 --算法导论(Introducti ...
随机推荐
-
Shiro-HelloWord
HelloWorld Shiro的HelloWorld不是我们写的,而是看Shiro给我们提供的一段代码.通过这段代码可以看到Shiro大致的使用方式. 1.找到Shiro的jar包 目前的最新稳定版 ...
-
Lintcode: Median
Given a unsorted array with integers, find the median of it. A median is the middle number of the ar ...
-
找出html中的图片、包括css中的图片,读出图片数据转换为base64数据
<?php echo ">> 图片的地址,css里面的要打单引号\r\n"; echo ">> 相同的图片,使用css实现图片地址只出现一次 ...
-
操作系统:cpu调度 6-25
1. 进程选择 1小时和1分钟? 进程优先1分钟,再执行1小时. 时间短的进程先执行,执行顺序也有关. 2. 遇到io操作,执行的进程先让出cpu,切换其他进程. 3.进程先来先服务,进程调度策略: ...
-
jmeter 使用聚合报告分析jtl文件
对于jmeter测试生成产生的jtl文件除了使用jemter插件来产生csv或者结果,还可以直接用聚合报告来打开,下面来介绍一下怎么操作. 1. 产生jtl文件 注意,默认情况下聚合报告插件只能分析聚 ...
-
Genymontion安装
Genymontion是什么 它提供的是Android的虚拟环境,和sdk的模拟器类似,能够支持windows,liunx,mac等操作系统,他比我们SDK的模拟器快很多,所以也是为什么很多开发人员会 ...
-
Jmeter 测试工具
Jmeter的基本概念 百度百科: Apache JMeter是Apache组织开发的基于Java的压力测试工具.用于对软件做压力测试,它最初被设计用于Web应用测试,但后来扩展到其他测试领域. 它可 ...
-
java压缩文件解压:调用WinRAR5命令强于自己写代码实现
最近,手上维护着一个几年前的系统,技术是用的JSP+Strust2,系统提供了rar和zip两种压缩格式的解压功能,后台是用java实现的 1.解压rar格式,采用的是java-unrar-0.3.j ...
-
2015-10-20 sql2
SQL SERVER(二) 三.插入,更新,删除,添加 3.1ins ...
-
三 js语句
/** * Created by Administrator on 2017/12/24. * 1.顺序语句 * 2.选择语句 if else swtich case * 3.循环语句 for whi ...