思路

桶排序是计数排序的升级版,与计数排序的区别是计数排序需要开辟一个与待排序数组的数值范围相当大小的空间,而桶排序只需要开辟有限的多个「桶」(即 bucket),每个桶负责一定范围的数字,然后将桶内排序,再串联起来。

分析

  • 桶排序的时间复杂度分为 2 个部分,分别是
    1. 计算每个数字的桶映射,时间复杂度为 $O(n)$;
    2. 对每个桶内的数据进行排序,时间复杂度为 $O(n_i \log n_i)$,其中 $n_i$ 为第 $i$ 个桶的序列大小。
  • 其中的第 1 部分是省不了的,而第 2 部分的排序也是省不了的,那么提高桶排序的速度的关键就在于如何分桶,它又可以从两方面进行增强:
    1. 尽量多分桶,分得越多,桶内排序就越快,相当于空间换时间;
    2. 尽量均匀分桶,越均匀,则总时间越短。
  • 其平均时间复杂度为 $O(n + k)$,最好时间复杂度为 $O(n + k)$(分桶到极致,等同于计数排序),最坏时间复杂度为 $O(n^2)$。
  • 空间复杂度为 $O(n + k)$。
  • 算法稳定。

实现

见《🔢 排序算法 00. 代码实现》(本博客)。