基数排序

基数排序 (Radix Sort) 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年在上的贡献。

排序过程：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

运行时间：对算法事件代价的分析依赖于所使用的稳定的排序算法。当每位数字在0~k-1区间内且k值不是很大时候，基数排序是一个好的选择。对n个d位数来说，每一轮排序耗时  @（n+k），因此总时间是@(d(n+k))   d位就是d轮
演示动画  ：  ~galles/visualization/RadixSort.html
两个问题:

• 为什么要从低位开始向高位排序?（http://www.cnblogs.com/sun/archive/2008/06/26/1230095.html）

        如果要从高位排序, 那么次高位的排序会影响高位已经排好的大小关系. 在数学中, 数位越高,数位值对数的大小的影响就越大.从低位开始排序,就是对这种影响的排序. 数位按照影响力从低到高的顺序排序, 数位影响力相同则比较数位值.

• 为什么同一数位的排序子程序要使用稳定排序? 要确保数字从容器中取出时不改变顺序，即使一个容器中的所有数字在该位都是相同的数字也要保证这一点。

        稳定排序的意思是指, 待排序相同元素之间的相对前后关系,在各次排序中不会改变.比如实例中具有十位数字5的两个数字58和356, 在十位排序之前356在58之前,在十位排序之后, 356依然在58之前.

        稳定排序能保证,上一次的排序成果被保留,（这样，在高位相同的前提下，低位的相对大小不会改变）十位数的排序过程能保留个位数的排序成果,百位数的排序过程能保留十位数的排序成果.