博客

排序算法

基数排序

基数排序法是属于稳定性的排序

，思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。（从低位比较到高位）

将数字长度统一，将最长的数字的最大位数取出，位数比较短的前面位数补0，从个位开始比较，直到比较最高位。

代码实现

/**
 * 基数排序
 */
public class CardinalitySort {
    public static void main(String[] args) {
        int[] array = new int[]{53,542,3,63,14,214,154,748,616};
        sort(array);
    }

    /**
     * 排序
     * @param array  进行排序的数组
     */
    public static void sort(int[] array){
        //找最大值
        int max = 0;
        for (int i =0;i< array.length;i++){
            if (array[i] > max){
                max = array[i];
            }
        }

        //拿到最高位
        int maxLength = (""+max).length();

        //定义十个桶，放0-9的数
        int buck[][] = new int[10][array.length];

        //定义辅助桶，存放桶中有效数据的个数
        int[] buckHelper = new int[10];

        //循环取数组中的数
        for (int i = 0;i < array.length;i++){
            int locationEle = array[i]%10; //模10取余，个位数
            //放入桶中
            buck[locationEle][buckHelper[locationEle]] =  array[i];
            buckHelper[locationEle]++;
        }

        //遍历辅助桶，将值取出来放入原数组中（为什么不用二维数组桶，是因为二维数组桶里面的数据可能会和0重合，导致分不清楚哪些是有效数据）
        int index = 0;
        for (int i =0;i<buckHelper.length;i++){
            //有数据的辅助桶
            if (buckHelper[i] != 0){
                //将数据取出来放入数组中
                for (int j = 0;j<buckHelper[i];j++){
                    array[index++] = buck[i][j];
                }
            }
            //数值取出来以后，将值赋为0
            buckHelper[i] = 0;
        }

        /**
         * 个位数排序
         */
        for (int i = 0;i < array.length;i++){
            int locationEle = array[i]/1%10; //模10取余，个位数
            //放入桶中
            buck[locationEle][buckHelper[locationEle]] =  array[i];
            buckHelper[locationEle]++;
        }

        //遍历辅助桶，将值取出来放入原数组中（为什么不用二维数组桶，是因为二维数组桶里面的数据可能会和0重合，导致分不清楚哪些是有效数据）
        index = 0;
        for (int i =0;i<buckHelper.length;i++){
            //有数据的辅助桶
            if (buckHelper[i] != 0){
                //将数据取出来放入数组中
                for (int j = 0;j<buckHelper[i];j++){
                    array[index++] = buck[i][j];
                }
            }
            //数值取出来以后，将值赋为0
            buckHelper[i] = 0;
        }

        /**
         * 十位数排序
         */
        for (int i = 0;i < array.length;i++){
            int locationEle = array[i]/10%10; //模10取余，个位数
            //放入桶中
            buck[locationEle][buckHelper[locationEle]] =  array[i];
            buckHelper[locationEle]++;
        }

        //遍历辅助桶，将值取出来放入原数组中（为什么不用二维数组桶，是因为二维数组桶里面的数据可能会和0重合，导致分不清楚哪些是有效数据）
        index = 0;
        for (int i =0;i<buckHelper.length;i++){
            //有数据的辅助桶
            if (buckHelper[i] != 0){
                //将数据取出来放入数组中
                for (int j = 0;j<buckHelper[i];j++){
                    array[index++] = buck[i][j];
                }
            }
            //数值取出来以后，将值赋为0
            buckHelper[i] = 0;
        }

        /**
         * 百位数排序
         */
        for (int i = 0;i < array.length;i++){
            int locationEle = array[i]/100%10; //模10取余，个位数
            //放入桶中
            buck[locationEle][buckHelper[locationEle]] =  array[i];
            buckHelper[locationEle]++;
        }

        //遍历辅助桶，将值取出来放入原数组中（为什么不用二维数组桶，是因为二维数组桶里面的数据可能会和0重合，导致分不清楚哪些是有效数据）
        index = 0;
        for (int i =0;i<buckHelper.length;i++){
            //有数据的辅助桶
            if (buckHelper[i] != 0){
                //将数据取出来放入数组中
                for (int j = 0;j<buckHelper[i];j++){
                    array[index++] = buck[i][j];
                }
            }
            //数值取出来以后，将值赋为0
            buckHelper[i] = 0;
        }

        //是Arrays   import java.util.Arrays;
        System.out.println(Arrays.toString(array));

    }
}