基数排序（Radix Sort）、桶排序（Bucket Sort）和计数排序（Counting Sort）都是非比较排序算法。也就是说，它们并不是通过比较元素之间的大小关系来进行排序的。
首先，让我们看看三种排序算法的时间复杂度：
基数排序：O(dn) (d次调用桶排序)，空间复杂度 O(k) (稍后详解)
桶排序：O(n)时间复杂度，O(n)空间复杂度
计数排序：O(n)时间复杂度，O(k)空间复杂度，每一个元素都是整数，并且位于0到k - 1之间
计数排序
假设：数组中的每一个元素都位于[0, k-1]的区间内
算法：此处不做详细描述
它是一种稳定排序：
时间复杂度：O(n)
空间复杂度：O(k)
基数排序
假设：它基于下面的假设：
k1 k2 k3 ... kd，其中对于每一个元素ki均位于[0, k-1]的范围内，ki是数字。k是键(key)的基(base)。如果k=10，则键就是一个十进制数。
算法过程如下：
对于每一个数位，按照这一位对数组执行计数排序。
算法假设每一次调用计数排序时，结果都是一次稳定的排序。否则基数排序就行不通了。
时间复杂度：O(dn)
空间复杂度：O(k)
显然，你可以通过增加k值减少d，同时牺牲一部分空间。
桶排序
假设:它使用了具有固定范围的“桶”。它假设每一个元素都会落在这些桶内。每一个桶的范围是固定的。如果桶的范围是1，则该算法就与计数排序很相似了，唯一的不同之处是，它存储的是元素本身而不是它们的计数。
算法：
假设有k个桶：B0, B1, ... ...