桶排序(bucket Sort)

10大排序算法.png

桶排序是一套方法论，是通过制定合适的规则把一组数据放进桶里， 对加入进去的元素进行排序后重新放回原数组的一套逻辑

执行流程：
1.创建一定数量的桶(比如用数组、链表作为桶)
2.按照一定的规则(不同类型的数据，规则不同)，将序列中的元素均匀分配到对应的桶
3.分别对每个桶进行单独排序
4.将所有非空桶的元素合并成有序序列

• 有多少个元素就创建多少个桶
• 每个元素要放到那个桶里是按照制定的规则来放的，比如元素都是[0,1)的，此时就可以按元素值 * 元素数量 来得出应该放哪个桶

示例实现.png

示例复杂度分析：
空间复杂度：O(n+m) ，m是桶的数量， 桶的数量有时候是不确定色
时间复杂度：O(n+nlogn-nlogm), 因此可以简化为 O(n+k), k为nlogn-nlogm

示例复杂度分析.png