排序-02-桶排序

参考博客 ： https://www.cnblogs.com/skywang12345/p/3603935.html

1. 桶排序思想

• 一句话总结：划分多个范围相同的区间，每个子区间进行自排序，最后合并
• 桶排序是计数排序的扩展版本
  • 计数排序可以看成每个桶只存储相同的元素
  • 而桶排序每个桶存储的是一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。

2. Java实现代码

public class BucketSort {
    public static void bucketSort(int[] arr){

        // 计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; 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<Integer>());
        }

        // 将每个元素放入桶
        for(int i = 0; i < arr.length; 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));
        }

        // 将桶中的元素赋值到原序列
        int index = 0;
        for(int i = 0; i < bucketArr.size(); i++){
            for(int j = 0; j < bucketArr.get(i).size(); j++){
                arr[index++] = bucketArr.get(i).get(j);
            }
        }
    }

}

测试用例：

class Test{
    public static void main(String[] args) {
        BucketSort.bucketSort(new int[]{18,11,28,45,23,50});
    }
}

3. 复杂度分析

• 时间复杂度：O(N+K)
  • N 次循环，将每个元素装入对应的桶中
  • M 次循环，对每个桶中的数据进行排序（平均每个桶有 N/M 个元素）

• 空间复杂度： O( N + M )

• 稳定性分析
  • 桶排序的稳定性取决于桶内排序使用的算法

打赏