排序----基数排序

public class ArraySortUtils {

    /**
     * 返回数组的字符串
     * @param array
     * @return
     */
    public static String arrayToString(int[] array){
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < array.length; i++) {
            if( i != (array.length - 1)){
                sb.append(array[i] + ",");
            }else{
                sb.append(array[i] + "]");
            }
        }
        return sb.toString();
    }


    /**
     * 基数排序---使用二维数组进行实现
     * @param array
     */
    public static void radixSort(int[] array){
        //获取数组中最大值的长度
        int MAX = array[0];
        for(int i = 1; i < array.length; i++){
            if(array[i] > MAX){
                MAX = array[i];
            }
        }
        int length = (MAX + "").length();

        //创建一个二维数组,用于存放每次按照位数进行排序的数据
        int[][] temp = new int[10][array.length];
        //创建一个数组用于记录每一个对应角标存放了多少数据
        int[] counts = new int[10];

        //进行基数排序
        for(int i = 0,n = 1; i < length; i++,n *= 10){
            //遍历原数组,将原数组数据放入二维数组
            for(int j = 0; j < array.length; j++){
                //获取指定位数上的数据值
                int baseIndex = array[j]/n%10;
                //将数组存放到二维数组的指定位置
                temp[baseIndex][counts[baseIndex]++] = array[j];
            }
            //创建一个索引,用于记录要添加到元素组的位置
            int index = 0;
            //将二维数组按照顺序放入原数组
            for(int j = 0; j < temp.length; j++){
                for(int k = 0; k < counts[j]; k++){
                    array[index++] = temp[j][k];
                }
            }
            //将counts数组清空
            counts = new int[10];
            System.out.println("第" + (i+1) + "次排序的结果：" + arrayToString(array));
        }
    }

    /**
     * 基数排序---使用队列进行实现
     * @param array
     */
    public static void radixSortUseQuene(int[] array){
        //获取数组中最大值的长度
        int MAX = array[0];
        for(int i = 1; i < array.length; i++){
            if(array[i] > MAX){
                MAX = array[i];
            }
        }
        int length = (MAX + "").length();

        //创建一个大小为10的队列数组
        MyQuene<Integer>[] quenes = new MyQuene[10];
        for(int i = 0; i < 10; i++){
            quenes[i] = new MyQuene<Integer>();
        }

        //进行基数排序
        for(int i = 0,n = 1; i < length; i++,n *= 10){
            //遍历原数组,将原数组数据放入队列中
            for(int j = 0; j < array.length; j++){
                //获取指定位数上的数据值
                int baseIndex = array[j]/n%10;
                //将数组队列中
                quenes[baseIndex].add(array[j]);
            }
            //创建一个索引,用于记录要添加到元素组的位置
            int index = 0;
            //将二维数组按照顺序放入原数组
            for(int j = 0; j < quenes.length; j++){
                //若队列不为空就出队
                while (!quenes[j].isEmpty()){
                    array[index++] = quenes[j].poll();
                }
            }
            System.out.println("第" + (i+1) + "次排序的结果：" + arrayToString(array));
        }
    }
}

public class ArraySortUtilsDemo {

    public static void main(String[] args) {
        int[] array = new int[]{8,4,7,10,6,5,4,8};
        array = new int[]{86,4,746,10,60,5,45,85};
        System.out.println("排序前：" + ArraySortUtils.arrayToString(array));
        //ArraySortUtils.bubbleSort(array);
        //ArraySortUtils.quickSort(array);
        //ArraySortUtils.insertSort(array);
        //ArraySortUtils.shellSort(array);
        //ArraySortUtils.selectSort(array);
       // ArraySortUtils.mergeSort(array);
        // ArraySortUtils.radixSort(array);
        ArraySortUtils.radixSortUseQuene(array);
        System.out.println("排序后：" + ArraySortUtils.arrayToString(array));
    }
}