排序算法丨桶排序

前言

当数列元素不是整数或非负数时,计数排序将不适用了。
例如:统计高考分数的排名,考生的满分是 750分,最低是 0分,这个数据的范围不算大,但是分数不可能都是整数,所以如果考生成绩精确到小数后一位,我们就需要将所有的分数都先乘以 10,转化成整数,然后再放到一个长度为 7510 的数组中,再使用计数排序。
再例如,如果要排序的数据中有负数,数据的范围是[-1000, 1000],那我们就需要先对每个数据都加 1000,转化成非负整数。
计数排序的局限比较多,在排序之前需要解决负数和小数的问题,而桶排序不需要考虑这些。

桶排序(Bucket Sort),顾名思义,会用到“桶”,每一个桶(bucket)代表一个区间范围,里面可以装载一个或多个元素(也可以不装)。
核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。

排序思路

  1. 设定合适数量的分桶;
  2. 遍历待排序序列,将每个元素放入到对应的桶中;
  3. 对每个非空桶进行合适的排序算法;
  4. 按顺序访问桶,将桶中的元素依次放回到原序列中对应的位置。

至于如何设置合适数量的分桶,如何确定桶的区间跨度,有很多不同的方式。
一般来说,简单分桶的话,桶的个数为 count(等于数列的元素数量),知道数列的最大值 max、最小值 min、长度 len,那么桶的区间跨度 range = (max - min) / (count - 1)。

代码实现

public class BucketSort {
  private static void bucketSort(int[] arr) {
      // 数组中最大值
      int max = max(arr);
      // 数组中最小值
      int min = min(arr);

      // 桶的数量
      int numberOfBuckets = max - min + 1;
      // 所有的桶保存在 ArrayList集合当中,这样便于在尾部插入元素
      List<List<Integer>> buckets = new ArrayList<>(numberOfBuckets);

      /* 初始化桶 */
      for (int i = 0; i < numberOfBuckets; ++i) {
          buckets.add(new ArrayList<>());
      }

      /* 将元素存储到桶中 */
      for (int value : arr) {
          int hash = hash(value, min, numberOfBuckets);
          buckets.get(hash).add(value);
      }

      /* 桶中的元素排序 */
      for (List<Integer> bucket : buckets) {
          // 使用了JDK的集合工具类 Collections.sort来为桶内部的元素进行排序
          Collections.sort(bucket);
      }

      /* 排序好的元素填充到原数组 */
      int index = 0;
      for (List<Integer> bucket : buckets) {
          for (int value : bucket) {
              arr[index++] = value;
          }
      }
  }

  /**
   * 获取将元素放入其中的桶的索引
   */
  private static int hash(int elem, int min, int numberOfBucket) {
      return (elem - min) / numberOfBucket;
  }

  /**
   * 获取数组中最大值
   */
  public static int max(int[] arr) {
      int max = arr[0];
      for (int value : arr) {
          if (value > max) {
              max = value;
          }
      }
      return max;
  }

  /**
   * 获取数组中最小值
   */
  public static int min(int[] arr) {
      int min = arr[0];
      for (int value : arr) {
          if (value < min) {
              min = value;
          }
      }
      return min;
  }
}

动画演示

演示动画来自于Data Structure Visualizations


桶排序

复杂度分析

如果要排序的数据有 n 个,我们把它们均匀地划分到 m 个桶内,每个桶里就有 k=n/m 个元素。
每个桶内部使用快速排序,时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk),因为 k=n/m,所以整个桶排序的时间复杂度就是 O(n * log(n/m))。
当桶的个数 m 接近数据个数 n 时,log(n/m) 就是一个非常小的常量,这个时候桶排序的时间复杂度接近 O(n)

当然,桶排序的空间复杂度为空桶占用的空间 + 数列在桶中占用的空间 = O(n+m),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。

此外,桶排序是稳定的。

局限性

尽管桶排序看起来很优秀,但是实际上,桶排序对要排序数据的要求是非常苛刻的,所以应用不是非常广泛。
首先,要排序的数据需要很容易就能划分成 m 个桶,并且,桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后,桶与桶之间的数据不需要再进行排序。
其次,数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后,有些桶里的数据非常多,有些非常少,很不平均,那桶内数据排序的时间复杂度就不是常量级了。在极端情况下,如果数据都被划分到一个桶里,那就退化为 O(nlogn) 的排序算法了,还浪费了很多空桶。

参考

程序员小灰
Java 全栈知识体系
Github-TheAlgorithms

是时候准备秋招了

打赏
评论区
头像
文章目录