跳到主要内容

简介

桶排序(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)的。即桶越多,时间效率就越高,而桶越多,空间就越大。