排序算法丨桶排序

前言

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

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

排序思路

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

至于如何设置合适数量的分桶，如何确定桶的区间跨度，有很多不同的方式。
一般来说，简单分桶的话，桶的个数为 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