桶排序（Bucket sort）
将要排序的数据分到几个有序的桶里，每个桶里的数据单独排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出。
时间复杂度：O(n)
如果要排序的数据有 n 个，均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k logk)。m 个桶排序的时间复杂度就是 O(m k _logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n\_log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。
使用场景：
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。 可以将大规模的数据尽量均匀地划分到多个文件（桶）中，每个文件进行快速排序。当每个文件内部都有序后，将分割的文件依次写入到最终文件中。
缺点
- 要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
- 数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。