桶排序(Bucket Sort)的基本思路是:
- 将待排序元素划分到不同的痛。先扫描一遍序列求出最大值
maxV
和最小值minV
,设桶的个数为k
,则把区间[minV, maxV]
均匀划分成k
个区间,每个区间就是一个桶。将序列中的元素分配到各自的桶。 - 对每个桶内的元素进行排序。可以选择任意一种排序算法。
- 将各个桶中的元素合并成一个大的有序序列。
假设数据是均匀分布的,则每个桶的元素平均个数为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)
的。即桶越多,时间效率就越高,而桶越多,空间就越大。