算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
### 基数排序、桶排序和计数排序的区别

先比较时间复杂度和空间复杂度。

| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|:--------|:--------------:|:-----------:|---------------------------------------|
| 基数排序 | O(nd) | O(n+k) |1.非负整数 2.`maxV`和`minV`差距尽可能小|
| 桶排序 | O(n+k) | O(n+k) | 元素尽可能均匀分布 |
| 计数排序 | O(n+maxV-minV)| O(maxV-minV)| `maxV`和`minV`差距尽可能小 |

其中, `d`表示位数,`k`在基数排序中表示`k`进制,在桶排序中表示桶的个数,`maxV` 和 `minV` 表示元素最大值和最小值。

首先,基数排序和计数排序都可以看作是桶排序。

* 计数排序本质上是一种特殊的桶排序,当桶的个数取最大(`maxV-minV+1`)的时候,就变成了计数排序。
* 基数排序也是一种桶排序。桶排序是按值区间划分桶,基数排序是按数位来划分;基数排序可以看做是多轮桶排序,每个数位上都进行一轮桶排序。
* 当用最大值作为基数时,基数排序就退化成了计数排序。

当使用2进制时,`k=2`最小,位数`d`最大,时间复杂度`O(nd)`会变大,空间复杂度`O(n+k)`会变小。当用最大值作为基数时,`k=maxV`最大,`d=1`最小,此时时间复杂度`O(nd)`变小,但是空间复杂度`O(n+k)`会急剧增大,此时**基数排序退化成了计数排序**。