计数排序

计数排序（counting sort）的思路很简单，就是确定比x小的数有多少个。加入有10个，那么x就排在第11位。

严谨来讲，在计算机科学中，计数排序是一个根据比较键值大小的排序算法，它也是一个整数排序算法。它通过比较对象的数值来操作，并通过这些计数来确定它们在即将输出的序列中的位置。它的运行时间是线性的且取决于最大值和最小值之间的差异，当值的变化明显大于数目时就不太适用了。而它也可以作为基排序的子程序。

第2-3步，C数组的元素被全部初始化为0，此时耗费Θ(k)时间。

第4-5步，也许不太好想象，其实就是在C数组中来计数A数组中的数。比如说，A数组中元素”3”有4个，那么C[3]=4。此时耗费Θ(n)时间。

第7-8步，也是不太好想象的计算，也就是说如果C[0]=1、C[1]=4，那么计算后的C[0]不变，C[1]=5。此时耗费Θ(k)时间。

第10-12步，把每个元素A[j]放到它在输出数组B中的合适位置。比如此时的第一次循环，先找到A[8]，然后找到C[A[8]]的值，此时C[A[8]]的意义就在于A[8]应在B数组中的位置。完成这一步后将C[A[8]]的值减一，因为它只是一个计数器。这里耗费的时间为Θ(n)。

当k=O(n)时，计数排序的运行时间为Θ(n)。

基数排序

基数排序（radix sort）是一个古老的算法，它用于卡片排序机上。说来也巧，写这篇博客的前一天晚上还在书上看到这种机器，它有80列，每一列都有12个孔可以打。

它可以使用前面介绍的计数排序作为子程序，然而它并不是原址排序；相比之下，很多运行时间为Θ(nlgn)的比较排序却是原址排序。因此当数据过大而内存不太够时，使用它并不是一个明智的选择。

关键在于依次对从右往左每一列数进行排序，其他的列也相应移动。

桶排序

这倒是一个有趣的算法了，它充分利用了链表的思想。

桶排序（bucket sort）在平均情况下的运行时间为O(n)。

计数排序假设n个输入元素中的每一个都在0和k之间，桶排序假设输入数据是均匀分布的，所以他们的速度都非常快。但并不能因为这些是假设就说它们不实用不准确，真正的意义在于你可以根据情况选择合适的算法。比如说，输入的n个元素并不是均匀分布的，但它们都在0到k之间，那么就可以用计数排序。

说到桶，我想到的是装满葡萄酒的酒桶以及装满火药的火药桶。这里是桶是指的算法将[0,1)区域划分为了n个相同大小的空间，它们被称为桶。

既然有了这个划分，那么就要用到它们。假设输入的是n个元素的数组A，且对于所有的i都有0≤A[i]<1。你也许会觉得怎么可能输入的数组元素都凑巧满足呢，当然不会这么凑巧，但是你可以人为地改造它们呀。比如<10,37,31,87>，你可以将它们都除以100，得到<0.10,0.37,0.31,0.87>。

还需要一个临时的数组B[0…n-1]来保存这些桶（也就是链表），而链表支持搜索，删除和插入。关于链表的部分后面的博客中会有详细介绍。

总结自：http://blog.csdn.net/nomasp/article/details/50359787