基数排序（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, ... Bk-1
对于数组a中的每一个元素e：
当e属于Bi时，将其插入Bi中
对于B中的每一个桶b：
sort b
令finalarray = {}
对于B中的每一个桶b：
finalarray = concat(finalarray, b)
时间复杂度：O(n)，最坏情况O(n * n)或者O(n * logn)取决于其对桶使用的排序算法。最坏情况下所有元素都落入同一个桶内。
其时间复杂度还与桶的大小和范围有关。如果桶的大小和范围选择不当，可能使得所有元素都落入同一个桶中。如果元素均匀的分布在各个桶内，则时间复杂度就是O(n)
空间复杂度：O(n)
桶排序还可用于对链表的排序
计数排序不可以用于对链表排序。
原文链接：http://www.quora.com/Algorithms/What-is-the-difference-between-Radix-sort-Bucket-sort-and-Counting-sort
本文链接：http://bookshadow.com/weblog/2014/12/14/what-is-the-difference-between-radix-sort-bucket-sort-and-counting-sort/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
