排序算法之——桶排序

作者:神秘网友 发布时间:2020-09-13 00:22:07

排序算法之——桶排序

排序算法之——桶排序

概念:桶排序是将数组中的元素放到一个一个的桶中,每个桶(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)

排序算法之——桶排序相关教程

  1. 算法 有向无环图 拓扑排序
  2. 归并排序和快速排序
  3. 排序算法之——计数排序
  4. 深入理解KMP算法(13. 字符串查找)
  5. 算法小白--1.排序算法
  6. 遗传算法 与旅行商问题
  7. 用Python实现几种简单的排序
  8. 选择排序