sorting/summary
优质
小牛编辑
128浏览
2023-12-01
基数排序、桶排序和计数排序的区别
先比较时间复杂度和空间复杂度。
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 基数排序 | 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)会急剧增大，此时基数排序退化成了计数排序。