桶排序java

骑猪看日落 2022-06-06 08:07 137阅读 0赞

桶排序

*  把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并
 *  计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
 *  思路：
    
    1.找出待排序数组中的最大值max、最小值min
    
    2.我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length + 1
    
    3.遍历数组 arr，计算每个元素 arr\[i\] 放的桶（根据商相等取得相近元素放入一个桶中）
    
    4.每个桶各自排序
    
    5.遍历桶数组，把排序好的元素放进输出数组

java代码：

public class BucketSort {
        public static void bucketSort(int[] arr) {
            // 大的当小的，小的当大的
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            // 找出最小最大值
            for (int i=0, len=arr.length; i<len; 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<>());
            }
            for (int i=0, len=arr.length; i<len; 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));
            }
            System.out.println(bucketArr.toString());
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关 java 桶排序

-------------------- java 桶排序 \\\\\\\\\\\\\\\\\\\\\\\ 桶排序

灰太狼/ 2022年11月21日 09:44/ 0 赞/ 114 阅读

相关桶排序java

桶排序把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况

骑猪看日落/ 2022年06月06日 08:07/ 0 赞/ 138 阅读

相关桶排序

期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有 5个同学，这 5个同学分别考了 5分、3分、 5分、2分和 8分，哎考得真是惨不忍睹（满分是 10分）

ゝ一纸荒年。/ 2022年06月02日 06:10/ 0 赞/ 209 阅读

相关桶排序

桶排序是最快最简单的排序，但是它有点浪费空间，是牺牲空间来节约时间的一种方法如果是0~1999，那么则需要申请2000个变量，不说了，附上代码望大家有所启发 incl

你的名字/ 2022年05月30日 05:40/ 0 赞/ 171 阅读

相关桶排序

桶排序算法描述： ![20180326135310487][] 桶排序的思想近乎彻底的分治思想。假设现在需要对一百个数进行排序。我们可以将其等长地分到10

╰+攻爆jí腚メ/ 2022年05月28日 00:09/ 0 赞/ 196 阅读

相关桶排序

从《[基于比较的排序结构总结][Link 1] 》中我们知道：全依赖“比较”操作的排序算法时间复杂度的一个下界O(N\logN)。但确实存在更快的算法。这些算法并不是不用“比较

╰+哭是因爲堅強的太久メ/ 2022年05月24日 06:29/ 0 赞/ 154 阅读

相关 Java实现桶排序

桶排序：使用额外空间，以空间换时间思想，，因此时间复杂度为O(n+m) 1.1 基本思想桶排序是所有排序算法中最快、也是最简单的排序算法。基本思想是在知道所有待排元素的

绝地灬酷狼/ 2022年05月09日 13:40/ 0 赞/ 145 阅读

相关桶排序

include <stdio.h> void swap(int a, int b) { int temp

叁歲伎倆/ 2022年04月23日 01:34/ 0 赞/ 205 阅读

相关桶排序

适用范围桶排序可用于最大最小值相差较大的数据情况，比如\[9012,19702,39867,68957,83556,102456\]。但桶排序要求数据的分布必须均匀

╰半夏微凉°/ 2022年04月18日 03:11/ 0 赞/ 187 阅读

相关桶排序

如我这几天的风格一样，概念不多说，直接正题： >: 桶排序不是基于比较的排序，最好的时间复杂度可以达到O(n)，例如：9个数 10,20,30,40,50,60,70

女爷i/ 2022年03月20日 01:42/ 0 赞/ 258 阅读