原创： 小灰

————— 第二天 —————

————————————

让我们先来回顾一下计数排序：

计数排序需要根据原始数列的取值范围，创建一个统计数组，用来统计原始数列中每一个可能的整数值所出现的次数。

原始数列中的整数值，和统计数组的下标是一一对应的，以数列的最小值作为偏移量。比如原始数列的最小值是90， 那么整数95对应的统计数组下标就是 95-90 = 5。

那么，桶排序当中所谓的“桶”，又是什么概念呢？

每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。桶排序的第一步，就是创建这些桶，确定每一个桶的区间范围：

具体建立多少个桶，如何确定桶的区间范围，有很多不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除了最后一个桶只包含数列最大值，前面各个桶的区间按照比例确定。

区间跨度 = （最大值-最小值）/ （桶的数量 – 1）

第二步，遍历原始数列，把元素对号入座放入各个桶中：

第三步，每个桶内部的元素分别排序（显然，只有第一个桶需要排序）：

第四步，遍历所有的桶，输出所有元素：

0.5，0.84，2.18，3.25，4.5

到此为止，排序结束。

代码中，所有的桶保存在ArrayList集合当中，每一个桶被定义成一个 链表 （LinkedList<Double>），这样便于在尾部插入元素。

定位元素属于第几个桶，是按照比例来定位：

(array[i] – min) * (bucketNum-1) / d

同时，代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort，小伙伴们可以简单地把它们当做是一种 时间复杂度 O（nlogn）的排序。

假设原始数列有n个元素，分成m个桶（我们采用的分桶方式 m=n），平均每个桶的元素个数为n/m。

下面我们来逐步分析算法复杂度：

第一步求数列最大最小值，运算量为n。

第二步创建空桶，运算量为m。

第三步遍历原始数列，运算量为n。

第四步在每个桶内部做排序，由于使用了O（nlogn）的排序算法，所以运算量为 n/m * log(n/m ) * m。

第五步输出排序数列，运算量为n。

加起来，总的运算量为 3n+m+ n/m * log(n/m ) * m = 3n+m+n(logn-logm) 。

去掉系数，时间复杂度为：

O(n+m+n(logn-logm)）

至于空间复杂度就很明显了：

空桶占用的空间 + 数列在桶中占用的空间 = O（m+n） 。