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

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

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

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/sorting/summary.html