计数排序的缺点很明显，需要额外的空间C来作为计数数组，虽然时间复杂度为O(n+k)，但当输入序列里元素取值很大的时侯，如k=O(n2)，时，此时时间复杂度已经达到n2数量级了，空间的消耗也是让人无法承受的。这里介绍一种另一种线性排序算法——基数排序，可以应对数值很大的情况。
基数排序，即一个数位一个数位地进行排序，平常生活中我们经常使用的一种算法思想：如要对一个日期进行排序，日期中由年、月、日组成的，对于这个问题，我们经常使用的是先比较年份，如果相同再比较月份，如果还相同就比较日。
同理，我们比较一组数，也可以采取这种思想。例如我们使用这种思想对下面四个数进行排序：123、312、245、531，第一次按百位排序：123、245、312、531；第二次按十位排序：312、123、531、245；第三次按个位数排序：531、312、123、245。咦？为什么最后排出来的结果并不是预期的那样？原因是我们从高位开始排序，已经差不多整体有序之后，再到低位时，又全部被打乱了。如果我们之后这样做就不会乱了：高位相同的数，再将它们的低位进行排序….不过这个实现一起比较困难一些。
这里，我们换成从最低有效位到最高有效位进行排序，那么还是上面那个例子：
个位 =>
十位 =>
百位
531 312 123
312 123 245
123
531
312
245 245 531
可以看到结果正确。通俗地讲，之所以先排低位再排高位，是因为越是后排的数位，其对结果次序的影响越大，很显然是高位比低位对数的大小影响大！
这里再给出一个简单的证明过程：
假定一组序列低t-1位已经排序好了，现在我们按照第t位进行排序。我们只需证明对于任意两个数来说，按照第t位排序之后其相对位置正确。任意两个数这时有两种情况：
1）它们第t位相同，那么此时如果我们保持它们位置的稳定性，那么它们最后仍然有序；
2）它们第t位不同，按照第t位排序之后就有序了。
所以，即证明了基数排序的正确性。从这里我们可以看出非常关键的一点——排序必需要稳定！很快就想到使用前面说过的计数排序算法！
那么可以得出计数排序的伪代码为:
可以得到时间复杂度为O(d(n+k)); 当d为常数、k=O(n)时，基数排序有线性的运行时间的。
更具体更普遍一点的算法：
/* n为待排序数组A的元素个数，B为按位计数排序后暂存数据的辅助数组，C则是计数数组，b为最大元素的长度（bit位数），r为每个数位的长度（即计数排序以2r进制） */
注：代码中2r是指2r!
基数排序比较适合对取值很大的数进行排序，也可用来对字符串进行排序。
但基数排序的缺点是不呈现时空局部性，因为在按位对每个数进行排序的过程中，一个数的位置可能发生巨大的变化，所以不能充分利用现代机器缓存提供的优势。同时计数排序作为中间稳定排序的话，不具有原地排序的特点，当内存容量比较宝贵的时候，还是有待商榷。
源代码下载地址：
参考文献：
[1] 算法之道.
邹恒明. 机械工业出版社，2010.
[2] 算法导论.
Cormen ,T.H. 等著，潘金贵等译. 机械工业出版社，2006.
版权申明：版权所有，翻版不究！欢迎学习交流。如发现BUG，恳请批评指正！