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

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

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

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

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

  • 计数排序本质上是一种特殊的桶排序,当桶的个数取最大(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