采用比较的排序算法至少具有O(nlgn)的时间复杂度。而对于整数序列来说，在满足一定的条件下，可以达到O(n)的时间复杂度
主要有计数排序和基数排序，下面分别介绍这两种算法。
一、计数排序(Counting Sort)
问题:对于一个n个整数元素的数组A[1...n]，如果每个元素的都在1~k的范围内
解决这个问题的想法很简单：如果元素a在统计中<=a的元素个数为j，则排序后的数组中a放在第j个位置没错。
伪代码：
第7行中采用反向遍历是为了保证计数排序算法的稳定性。
这个算法的时间复杂度为O(n+k)，空间复杂度为O(k)
一般来说,当K=O(n)时，时间复杂度为O(n)
二、基数排序(Radix Sort)
问题：对于一个n个整数元素的数组A[1...n]，如果每个元素都可以用b bit表示
想法很简单，我们可以对整数序列从低位到高位逐步排序，这是计数排序的一种扩展
如果我们每次比较r bits，则需要进行b/r趟，每趟进行计数排序需要O(n+2^r)
则总的时间复杂度为O(b/r(n+2^r))
基数排序时计数排序的扩展，r取越大，空间复杂度就越高，当r=b时，就成了计数排序。
一般来说，取r=lgn,此时时间复杂度为O(bn/lgn)
三、例子
问题：How to sort n integers int the range 0 to n^2-1 in O(n) time
对于这个经典问题，我们可以采用基数排序
取b=log(n^2），取r=logn，则时间复杂度为O(2*(n+n))，即O(n)的时间复杂度