桶排序

一、基本思路

a、将数组中元素划分到不同的桶中。先对遍历数组找到最大值元素（maxNum）和最小值元素（minNum），然后设定用的个数为x个，然后把【maxNum,minNum】均匀划分成 x个区间，每个区间就是一个桶。将数组中的元素分配到各相应的桶中；

b、对桶内的元素进行排序，任意选择一种排序算法；

c、将各个桶中的元素合并成一个大的有序序列（数组）；

d、假设数据是均匀分布的，则每个桶的元素平均个数为 n/k 。假设选择用快速排序对每个桶内的元素进行排序，那么每次排序的时间复杂度为 O(n/klog(n/k)) 。总的时间复杂度为O(n)+O(m)O(n/klog(n/k)) = O(n+nlog(n/k)) = O(n+nlogn-nlogk 。所以桶排序的时间复杂度和空间复杂度都为：O(n+k)；当 k 接近于 n 时，桶排序的时间复杂度就可以认为是 O(n)的。即桶越多，时间效率就越高，而桶越多，空间就越大。

桶排序在什么时候最快呢？-> 当输入的数据可以均匀的分配到每一个桶中。

桶排序在什么时候最慢呢？->当输入的数据被分配到了同一个桶中。

二、代码实现

➕关注微信公众号【疯狂1024】