JAVA语言编程开发基数排序解析
小标 2019-01-18 来源 : 阅读 708 评论 0

摘要:本文主要向大家介绍了JAVA语言编程开发基数排序解析,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。

本文主要向大家介绍了JAVA语言编程开发基数排序解析,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。

1.桶式排序概念


    有限个数字m,每个数字的大小都在1与n之间,则我们可以假设有n个桶,遍历m个数字,

    将其存入对应的桶中(如数字的值为3,就存入3号桶,桶的值对应存入数字的个数)


   



2.基数排序概念


    基于桶式排序,将要排序的数字一位一位的比较,经历多次桶式排序,得出最终的序列

    如果要排序的元素可以分成多位,并且每一位都在一个固定的范围内,则可以用这种排序方法,如对10进制数字的排序


   



3.代码实现


/**

 * 桶式排序

 * max是最大数字

 * @param arr

 * @param max

 */

public  void bucketSort(int[] arr,int max){

    //声明一个数组,这就是桶,编号从0到max的桶,一共max+1个

    int[] count = new int[max + 1];

    //遍历数组,用桶计数

    for(int i = 0;i < arr.length;i++){

        count[arr[i]]++;

    }

 

    int k = 0;

    for(int i = 0;i <=max ;i++){

        while(count[i] > 0){

            arr[k++] = i;

            count[i]--;

        }

    }

    System.out.println("排序后");

    printArr(arr);

}

 

 

/*

 * 基数排序  稳定的排序算法

 * array    代表数组

 * radix    代表基数

 * d        代表排序元素的位数

 */

public int[] radixSort1(int[] arr, int radix, int d){

    //第一维radix表示一共有radix个桶

    //第二维arr.length表示每个桶最多可能存放a.length个数字

    int[][] temp = new int[radix][arr.length];

    // count用于记录待排序元素的信息,用来表示该位是i的数的个数

    int[] count = new int[radix];

    // 定义每一轮的除数,1,10,100...

    int rate = 1;

    for (int i = 0; i < d; i++) {

 

        System.out.println("第"+(i+1)+"次排序前");

        printArr(arr);

        System.out.println("除数 :"+rate);

 

        //遍历要排序的数组,将其存入temp数组中(按照第n位上的数字将数字放入桶中)

        for (int j = 0; j < arr.length; j++) {

            //取余

            int subKey = (arr[j] / rate) % 10;

            //System.out.println("sub : count "+ subKey+" : "+count[subKey]);

            temp[subKey][count[subKey]++] = arr[j];

        }

 

        int m = 0;//arr数组下标

        //把每趟整理的数值按整理后的顺序放到原数组中, 进行下次循环排序

        for (int j = 0; j < radix; j++) {

            //该号桶个数大于0

            if(count[j] != 0){

                System.out.println("桶号:"+j+" 第"+j+"号桶的个数"+count[j]);

                for (int k = 0; k < count[j]; k++) {

                    arr[m++] = temp[j][k];

                }

                //把相应位上的个数置空,下次使用

                count[j] = 0;

            }

        }

        rate =  rate * 10;

        System.out.println("第"+(i+1)+"次排序后");

        printArr(arr);

        System.out.println();

    }

    return arr;

}

   



4.测试


@Test

public void test(){

    //int arr[] = {0,1,1,2,3,3,4,8,7,6,12,22,65};

    int arr[] = { 1200, 292, 121, 72, 233, 44, 12 };

    //int arr[] = {6,3,8,2,9,1};

    System.out.println("排序前");

    printArr(arr);

 

    int[] data = radixSort1(arr,10,4);

 

    System.out.println("排序后");

    printArr(data);

}

 

public void printArr(int[] arr){

    for (int i = 0; i < arr.length; i++) {

        System.out.print(arr[i]+" ");

    }

    System.out.println();

}

   



5.总结


算法特点:

    1.是稳定排序

    2.可用于链式结构,也可用于顺序结构

    3.时间复杂度可以突破基于关键字比较一类方法的下界O(nlog2n),达到O(n)

    4.基数排序使用条件有严格的要求:需要知道各级关键字的主次关系和各级关键字的取值范围。


   



          

本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注编程语言JAVA频道!

本文由 @小标 发布于职坐标。未经许可,禁止转载。
喜欢 | 1 不喜欢 | 0
看完这篇文章有何感觉?已经有1人表态,100%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:z_zhizuobiao
小职老师的微信号:z_zhizuobiao

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    

©2015 www.zhizuobiao.com All Rights Reserved

208小时内训课程