排序——桶排序¶

桶排序是一种稳定的排序方法，其是非比较类排序中最简单的一种。

其基本思想是：假设待排序记录的值都在 0~m-1 之间，设置 m 个桶，将值为 i 的记录分配到第 i 个桶中，然后再将各个桶中的距离依次收集起来。

最好的情况下，每个桶只有一个数据，那么最好时间复杂度为 O(N)

假设 C 为桶内排序所花费的时间，那么平均时间复杂度：O(N+C)

此外，假设 M 为桶排所需的辅助空间大小，那么空间复杂度为为：O(M)

典型题目¶