算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	排序方式	稳定性
桶排序	O(n+k )	O(n+k)	O(n^2)	O(n+k)	Out-place	稳定

稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；
不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；
时间复杂度： 描述一个算法执行所耗费的时间；
空间复杂度：描述一个算法执行所需内存的大小；
n：数据规模；
k：“桶”的个数；
In-place：占用常数内存，不占用额外内存；
Out-place：占用额外内存。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
什么时候最快?
当输入的数据可以均匀的分配到每一个桶中。
什么时候最慢?
当输入的数据被分配到了同一个桶中。

算法步驟：

• 1.确定桶的数量：根据输入数据的范围和数量确定需要多少个桶。
  首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中，那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn；
  根据mx和mn确定每个桶所装的数据的范围 size，有
  size = (mx - mn) / n + 1，n为数据的个数，需要保证至少有一个桶，故而需要加个1；
  求得了size即知道了每个桶所装数据的范围，还需要计算出所需的桶的个数cnt，有
  cnt = (mx - mn) / size + 1，需要保证每个桶至少要能装1个数，故而需要加个1；
• 2.将数据分配到各个桶中：遍历输入数据，根据数据的值将数据分配到对应的桶中。
  求得了size和cnt后，即可知第一个桶装的数据范围为 [mn, mn + size)，第二个桶为 [mn + size, mn + 2 * size)，…，以此类推，因此步骤2中需要再扫描一遍数组，将待排序的各个数放进对应的桶中。
• 3.对每个桶内的数据进行排序：对每个非空的桶内的数据进行排序，可以使用插入排序等方法。
• 4.合并各个桶的数据：按照桶的顺序将各个桶内的数据合并为最终的排序结果。

示意图
元素分布在桶中：

然后，元素在每个桶中排序：

---