物理

基础算法之桶排序

桶排序

〇、返回

一、概述

桶排序是使用桶统计元素个数以达到排序目的的排序方式，类似离散化的思想，优点是容易实现且复杂度较优秀，缺点是不稳定及时空复杂度与值域挂钩

下文中 $V$ 表示待排序元素的值域范围，即上界-下界

二、算法步骤

1. 遍历待排序数列，统计每个元素出现的个数

2. 从小到大（如果降序排就是从大到小）遍历值域，按顺序将每个元素加入到数列中

容易发现，这样得到的数列是严格不降的。

三、时空复杂度

时间复杂度：$O(n+V)$，即最开始遍历数组一次+遍历值域

空间复杂度：$O(V)$

显然，值域是时空复杂度的瓶颈且没办法优化掉。

四、代码