您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

数据结构与算法-排序-基数排序(桶排序)JAVA版

1.算法流程:

基本思想(这个借鉴的是尚硅谷的数据结构资料)

在这里插入图片描述

排序过程

在这里插入图片描述
在这里插入图片描述在这里插入图片描述

算法思路:

(1)相当于先求出数组中元素中,位数最多的元素的位数howMany,然后进行howMany轮(最外层循环)的桶排序。
(2)在每轮桶排序中,10个桶里面都是干净的(所以要注意清除上轮桶排序剩的东西,干脆每轮循环就初始化)。
为了在每轮桶排序中,取出每个桶里面的元素,由于每个桶里面不止一个元素,所以用二维数组表示桶。第一维表示第几个桶,第二维表示放的元素的索引(从0开始)。
另外,由于我们要对每个桶内遍历取数据,所以需要再建立一个数组order来标记每个桶里具体放了几个元素。
!!order数组也要每轮桶排序之后置null。
这个算法里面涉及一些如何判断个位或者十位数字为多少,就是将求余和除法结合,注意JAVA中平方公式求出来的是double

package Sort;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {542, 53, 3, 14, 214, 748};
        //int result = howMany(arr);
        //System.out.println(result);
        radixSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void radixSort(int[] arr) {
        //1.先算出该输入数组中位数最多的是几位
        int maxLength = howMany(arr);
        int length = arr.length;

        //桶排序轮数和最多位数是相等的
        for (int i = 0; i < maxLength; i++) {

            //非常需要注意的是:每轮桶排序都需要把桶和标识个数的数组置为空,所以干脆初始化放进里面了
            //二维数组,第一维代表十个桶,第二维表示每个桶最多放数组长度的元素
            int[][] buckets = new int[10][length];
            //定义一个数组,标识每个桶里面实际放了几个元素
            int[] order = new int[10];
            int temp = 0;

            //放进桶里
            for (int j = 0; j < arr.length; j++) {
                temp = (int) (arr[j] % (10 * Math.pow(10, i)) / Math.pow(10,i));
                order[temp]++;
                buckets[temp][order[temp] - 1] = arr[j];
            }

            //从桶里取出,更新arr,新的arr进行下次桶排序
            int k = 0;
            while (k < arr.length) {
                for (int m = 0; m < 10; m++) {
                    for (int n = 0; n < order[m]; n++) {
                        arr[k] = buckets[m][n];
                        k++;
                    }

                }
            }

        }

    }

    /**
     * 输入一个数组,判断数组中位数最多是多少位
     *
     * @param arr
     * @return
     */
    public static int howMany(int[] arr) {
        int sum = 0;
        int max = 0;

        for (int i = 0; i < arr.length; i++) {
            //注意此处要强转一下,因为pow函数计算出来的是double
            while ((arr[i] / (int) Math.pow(10, sum)) > 0) {
                sum++;
            }
            //sum是记录每个数组元素位数,max总是记录最大的数
            if (sum > max) {
                max = sum;
            }
            sum = 0;
        }
        return max;
    }
}

最近发现一个问题,算法这种,听别人讲很难管用,不是自己的思想,不如自己先找个博客看下算法的思想,然后自己好好捋一下,自己写代码,这样认识更深刻,有问题的话通过debug调试下看看问题在哪。


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进