基数排序、桶排序和计数排序的区别

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

算法	时间复杂度	空间复杂度	适用场景
基数排序	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)会急剧增大，此时基数排序退化成了计数排序。