[数据结构与算法]桶排序动态图与代码

感谢：https://www.geeksforgeeks.org/fundamentals-of-algorithms/?ref=shm#SearchingandSorting
计数排序不能解决当数字有，小数的情况，但是桶排序算法做出了弥补，适用于小数排序。

一言以蔽之：分成多个子区间，每个子区间排序，然后根据索引顺序合并。

步骤

步骤实现：

1. 创建桶
2. 将元素放入桶
3. 每个桶里的元素，做好排序
4. 遍历所有桶，放入到结果数组中

步骤实现的关键点

• 通常情况下被排序的数组有几个元素我们就建几个桶
• 元素怎么确定放入第几个桶，通过元素值*桶数 例如： arr[i] 放入桶里哪个同理？ index = arr[i]*n ，index 为要放入那个桶的序号

图解

代码

 @Test
    public void bucketSort() {
        float arr[] = {(float) 0.897, (float) 0.565,
                (float) 0.656, (float) 0.1234,
                (float) 0.665, (float) 0.3434};

        bucketSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    private void bucketSort(float[] arr) {
        int n = arr.length;
        // 1 create bucket
        List<List> buckets = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            buckets.add(new ArrayList<>());
        }
        // 2 put into bucket
        for (int i = 0; i < n; i++) {
            buckets.get((int) arr[i] * n).add(arr[i]);
        }
        for (int i = 0; i < buckets.size(); i++) {
            Collections.sort(buckets.get(i));
        }
        int index = 0;
        for (int i = 0; i < buckets.size(); i++) {
            for (int j = 0; j < buckets.get(i).size(); j++) {
                arr[index++] = (float)buckets.get(i).get(j);
            }
        }
        
    }

复杂度

假设桶为 K个，数组长度N

1. 遍历一次N ,放入对于的桶里-------------O(N)
2. K个桶都要排序，排序算法使用一种复杂度?为：? O（NlogN）的算法，K次循环，每个桶的元素个数平均 N/K 个----------------O(K * (N / K *log(N/K)))

总体复杂度：
*O(N) + O (K * (N / K log(N/K)))
去分母K提前公因子N：
O ( N * ( log( N / M )+1 ) )
而我所写代码是,以数组长度来建桶的个数，所以即：
N=M 时 复杂度为： O（N）

但是桶排序并不是稳定的，在某些情况下如果，桶元素分配极度不均匀，例如 一个桶有 N-1 个元素，这时排序复杂度，完全取决于当前桶的复杂了，也就是 O(nlogn),而且还浪费了许多没有用到的桶。

赠人玫瑰，手有余香，你的点赞，备受鼓舞！

如果你能看到这里了，不如点赞关注一波，我会认真分享每一篇博文。大家共同成长。

我的公众号：茄子的笔记

更多分享可见：