经典排序算法之基数排序

经典排序算法之基数排序

1. 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

2. LSD 基数排序动图演示

3.排序思路

想一下平时对比两个时间大小是如何进行比较的。一般都是先对比年份，如果年份大的肯定就大。接下来再对比月份，然后日。为什么这么比较呢，因为权重不一样权重顺序是：年>月>日

而基数排序的思路跟这个有点类似。将每一个数分成一位数一位数的方式进行排序。例如

4.代码演示

package com.ma.sort;

import java.util.Arrays;

//基数排序
public class BasicSort {
    public static void main(String[] args) {
        int[] array = new int[]{42,58,155,45,36,35,492};
        basicSort(array);
    }

    public static void basicSort(int[] array){
        //1.得到数组中最大的位数
        int max = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max){
                max = array[i];
            }
        }

        //得到最大数是几位
        int length = (max+"").length();



        /*
         * 定义一个二维数组，表示十个桶
         * 说明：
         * 1.二维数组包含十个一维数组
         * 2.为了防止在放入数的时候，数据溢出，则每一个一维数组，大小定义为 arr.length()
         * 3.基数排序是空间换时间的经典算法
         * */

        int[][] bucket = new int[10][array.length];
        //为了记录每个桶中存放了多少个数据。我们定义一个一维数组来记录各个桶中每次放入数据的个数
        //比如 bucketElementCount[1]  就表示bucket[1]桶中的数据个数
        int[] bucketElementCount = new int[10];

        //这里我们使用循环将代码进行处理
        for (int i = 0, n = 1; i < length; i++, n *= 10) {
            //针对每个元素的对应位进行排序处理，第一次是个位，第二次是十位，第三次是百位。。。。
            for (int j = 0; j < array.length; j++) {
                //取出每个元素对应位的值
                int digitOfElement = array[j] / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCount[digitOfElement]] = array[j];
                bucketElementCount[digitOfElement]++;
            }

            //按照这个桶的顺序，（一维数组的下标，依此取出数据放到原数组）
            int index = 0;
            //遍历每一桶，并将每一桶的数据，放入到原数组
            for (int k = 0; k < bucketElementCount.length; k++) {
                //如果桶中有数据，我们取出，然后放回原数组
                if (bucketElementCount[k] != 0){
                    //循环该桶（即第k个一维数组）,放入
                    for (int l = 0; l < bucketElementCount[k]; l++) {
                        array[index++] = bucket[k][l];
                    }
                }
                //当把每个桶中数据取出后，需要将每个 bucketElementCounts[k] = 0 !!!!
                bucketElementCount[k] = 0;
            }
            System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(array));

        }

    }
}

ntln(“第”+(i+1)+“轮，对个位的排序处理 arr =” + Arrays.toString(array));

    }

}

}