八大排序算法之基数排序

飞熊 • 2023年4月17日上午11:03 • 后端漫谈 • 阅读 246

01

—

基数排序

1，基数排序又称为“分配式排序”，又称”桶子法“。他是通过键值各个位置的值，将要排序的元素分配至某些桶中，达到排序作用。
2，基数排序是桶排序的扩展。
3，基数排序是1887年赫尔曼.何乐礼发明的：将整数按位数切割成不同数字，然后按个位数分别比较。
4，基本思想：将所有待排序的数值统一为同样长度，位数较短的数前面补零，然后从最低位开始，依次进行一次排序。这样最低位排序一直到最高位排序完成后，数列就是一个有序数列。

02

—

演绎过程

03

—

时间复杂度

时间复杂度：O(d(r+n)) r代表关键字的基数，d代表长度，n代表关键字个数。

稳定性：稳定。

04

—

代码实现

//基数排序
    public static void redisSort(int[] arr) {

        //查找数组中最大数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

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

        //定义二维数组，用空间换时间的算法
        int[][] bucket = new int[10][arr.length];

        //记录每一个桶中实际存放啦多少条数据，
        // 如bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数。
        int[] bucketElementCounts = new int[10];

        for (int i = 0,n = 1; i < maxLength; i++,n*=10) {
            //针对每个元素的对应位进行排序处理，第一次是个位，十位，百位。
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的对应位的值
                int digitOfElement = arr[j] / n % 10;
                //放到对应桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }

            //按照这个桶的顺序
            int index = 0;

            //遍历每一遍桶，并将桶中数据，放到原数组
            for (int j = 0; j < bucketElementCounts.length; j++) {
                //如果桶中有数据，我们才放到原数组
                if (bucketElementCounts[j] != 0) {
                    //循环该桶，放入
                    for (int k = 0; k < bucketElementCounts[j]; k++) {
                        //取出元素放入arr
                        arr[index++] = bucket[j][k];
                    }
                }
                //第i+1轮处理后，需要将每个bucketElementCounts【j】 = 0
                bucketElementCounts[j] = 0;
            }
//            System.out.println("第"+(i + 1) +"轮"+ Arrays.toString(arr));
        }


    }