基数排序

维基百科，自由的百科全书

基数排序（Radix Sort）是一种排序算法，它是这样实现的：
假设需排序数列的取值范围从1...k,我们于是建一个K+1元的数组 a[]，并赋初值为0，然后便开始排序工作：

1. 按输入顺序读入数列，如果所读的元素为i(1<=i<=k),我们就将a[i]的值加一，这样直到读完所有的元素。
   
2. 读出元素并排序：我们遍历整个数组，如果a[i]=j(j>=0),我们就输出j次i(表示元素i在原先数列中出现了j次),这样输出的序列就是已排序的。
3. 由于一般排序算法涉及到元素之间的比较，如果化成比较树可以知道，这样的排序算法复杂度的下限是O(N*lnN),而计数排序没有比较元素，所以所需排序时间就少了，我们可以看到计数排序的复杂度为O(n+k)，其中k（k的定义同上）为合并排列所需的时间，是个常数。
   
4. 此算法适合所需排列的元素取值范围不大的情况下，否则会造成空间的消耗，比如，一共100个元素，其取值范围从1-100000，显然这个时候用基数排序是不合适的。