- 根据数据范围，分成若干个数据段，通过遍历数据放到对应的桶中
- 每个桶都进行快排或归并
- 时间复杂度解释
- 如果排序的数据 有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)
- 最好O(n), 最坏o(nlogn), 平均O(n)， 一般桶分越细越多复杂度就会越好
- 空间复杂度：O(n)
- 取决于每个桶的排序方式，快排就不稳定，归并就稳定
- 数据范围不大，内存紧张的情况。如磁盘的读写可以分成多个小文件并对小文件排序
- 然后直接写到大文件里，这个时候，内存消耗不再是O(n)