简介

桶排序(Bucket Sort)的基本思路是：

1. 将待排序元素划分到不同的痛。先扫描一遍序列求出最大值maxV和最小值minV，设桶的个数为k，则把区间[minV, maxV]均匀划分成k个区间，每个区间就是一个桶。将序列中的元素分配到各自的桶。
2. 对每个桶内的元素进行排序。可以选择任意一种排序算法。
3. 将各个桶中的元素合并成一个大的有序序列。

假设数据是均匀分布的，则每个桶的元素平均个数为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。当k接近于n时，桶排序的时间复杂度就可以金斯认为是O(n)的。即桶越多，时间效率就越高，而桶越多，空间就越大。