桶排序 #

将数组分到有限数量的桶里。同时对每个桶进行比较排序，最后依次把各个桶中的记录逐个输出。

基本思想 #

桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。

然后基于某种映射函数f ，将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为B[i]中的元素 (每个桶B[i]都是一组大小为N/M 的序列 )。

补充： 映射函数一般是 f = array[i] / k; k^2 = n;

n是所有元素个数

接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (可以使用快排)。然后依次枚举输出 B[0]….B[M] 中的全部内容即是一个有序序列。

尽量做到两点：

1、在额外空间充足的情况下，尽量增大桶的数量；

2、使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中；

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

复杂度分析 #

平均时间复杂度：O(n + k)
最佳时间复杂度：O(n + k)
最差时间复杂度：O(n ^ 2) ——使用O(n^2)的算法排序桶内元素 空间复杂度：O(n * k)
稳定性：稳定

n 是遍历数组的复杂度，k是遍历桶的复杂度。 假如我们用快排，时间复杂度是nlogn，n个数分到k个桶，每个桶里有m = n / k 个，k个桶复杂度就是k * (n / k)log(n / k) = nlog(n / k),当n接近k时，log(n/k)就是一个较小的常数，所以时间复杂度接近O(n)。

例题 #

• 030. 距离顺序排列矩阵单元格