[算法详解][桶排序]Bucket Sort

• 基本思想
• 步骤
• 实例分析
• 伪代码
• 代码实现JAVA
• 性能分析
• 应用：常见面试题目

【基本思想】

将数组分到有限数量的桶子里，然后对每个桶子再分别排序

【步骤】

1. 假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
2. 将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序
3. 将各个桶中的数据有序的合并起来

【实例分析】

现有一组数组 array = [29, 25, 3, 49, 9, 37, 21, 43]
先设置 5 个桶，那么每个桶可存放数的范围为：09、1019、2029、3039、40~49，然后分别将这些数放人自己所属的桶.
分别对每个桶里面的数进行排序，或者在将数放入桶的同时用插入排序进行排序。

【伪代码】

function bucket-sort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

【JAVA代码实现】

【性能分析】

桶越多，时间效率就越高，而桶越多，空间却就越大
1. 最优
时间复杂度为O(n)
在最好情况下，若输入已排序，插入排序的时间复杂度在O(n)，即线性时间上完成排序。
2. 最坏
时间复杂度为O(n)
N次循环，每一个数据装入桶
然后M次循环，每一个桶中的数据进行排序(每一个桶中有N/M个数据)，假设为使用比较先进的排序算法进行排序O(NlogN)
O(N)+O(M(N/M)log(N/M))=O(N(log(N/M)+1))
当M=N时，有一个最小值为O(N)

3. 平均
O(n)
平均情况和最坏情况差不多，复杂度也在O(n)
4. 空间复杂度
O(n+m)
需要创建M个桶的额外空间，以及N个元素的额外空间
所以桶排序的空间复杂度为 O(N+M)
5. 稳定性
相等元素的前后顺序没有改变，稳定排序

【应用：常见面试题目】

Leetcode 274. H-Index

参考：常见排序算法 - 桶排序)