排序算法篇（基数排序）

基本解法
第一步
以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
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
Java实现代码：   
package com.algorithm.sort; 
     
    import java.util.Arrays; 
     
    public class RadixSort { 
     
        //基于计数排序的基数排序算法 
        private static void radixSort(int[] array,int radix, int distance) { 
            //array为待排序数组 
            //radix，代表基数 
            //代表排序元素的位数 
             
            int length = array.length; 
            int[] temp = new int[length];//用于暂存元素 
            int[] count = new int[radix];//用于计数排序 
            int divide = 1; 
             
            for (int i = 0; i < distance; i++) { 
                 
                System.arraycopy(array, 0,temp, 0, length); 
                Arrays.fill(count, 0); 
                 
                for (int j = 0; j < length; j++) { 
                    int tempKey = (temp[j]/divide)%radix; 
                    count[tempKey]++; 
                } 
                 
                for (int j = 1; j < radix; j++) { 
                    count [j] = count[j] + count[j-1]; 
                } 
                 
                //个人觉的运用计数排序实现计数排序的重点在下面这个方法             
                for (int j = length - 1; j >= 0; j--) { 
                    int tempKey = (temp[j]/divide)%radix; 
                    count[tempKey]--; 
                    array[count[tempKey]] = temp[j]; 
                } 
                 
                divide = divide * radix;                 
                 
            } 
                     
        } 
         
         
        /**
         * @param args
         */ 
        public static void main(String[] args) { 
         
            int[] array = {3,2,3,2,5,333,45566,2345678,78,990,12,432,56}; 
            radixSort(array,10,7); 
            for (int i = 0; i < array.length; i++) { 
                System.out.print("  " + array[i]); 
            } 
             
     
        } 
     
    }