基数排序原理

                                                     基数排序原理

     基数排序是一种有意思的排序,在看过其它比较排序后,基数排序真的很有意思。
    基数排序(Radix Sort)属于分配式排序,又称"桶子法"(Bucket Sort或Bin Sort),将要排序的元素分配到某些"桶"中,以达到排序的作用.基数排序属于稳定的排序,其时间复杂度为nlog(r)m (其中r为的采取的基数,m为堆数),基数排序的效率有时候高于其它比较性排序.

    基数排序的方式可以采用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演算方式则都相同。 

   以LSD为例，假设原来有一串数值如下所示： 
      73, 22, 93, 43, 55, 14, 28, 65, 39, 81 
   首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中： 
      0 
　　1 81 
　　2 22 
　　3 73 93 43 
　　4 14 
　　5 55 65 
　　6 
　　7 
　　8 28 
　　9 39 
　接下来将这些桶子中的数值重新串接起来，成为以下的数列： 
　　81, 22, 73, 93, 43, 14, 55, 65, 28, 39 
　接着再进行一次分配，这次是根据十位数来分配： 
　　0 
　　1 14 
　　2 22 28 
　　3 39 
　　4 43 
　　5 55 
　　6 65 
　　7 73 
　　8 81 
　　9 93 
　接下来将这些桶子中的数值重新串接起来，成为以下的数列： 
　　14, 22, 28, 39, 43, 55, 65, 73, 81, 93 
　这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。  

本文参考：
http://www.cnblogs.com/tanky_woo/archive/2011/04/24/2026059.html