桶排序（Bucket Sort）
一、概念
- 执行流程
- 创建一定数量的桶（比如用数组，链表作为桶）。
- 按照一定的规则（不同类型的数据，规则不同），将序列中的元素均匀分配到对应的桶。
- 分别对每个桶进行单独排序。
- 将所有非空桶的元素合并成有序序列。
二、实际操作
- 首先有如下一个数组：
image
- 数组中有
8个元素，那么创建8个桶。 - 元素在桶中的索引：
元素值 * 元素数量。
image
- 对每个桶中的元素进行排序：
image
- 依次将桶中元素存入数组即可：
image
三、代码实现
image
- 空间复杂度：
O(n + m)，m是桶的数量。
image
四、十大排序算法
image
- 冒泡，选择，插入，归并，快速，希尔，堆排序，属于
比较排序。 - 比较排序无法突破
O(nlogn)的效率。
