数据结构(Java)-排序算法-基数排序(带负数)

数据结构(Java)-排序算法-基数排序(带负数),第1张

基数排序(桶排序)介绍: 1) 基数排序 radix sort )属于“分配式排序”( distribution sort ),又称“桶子法”( bucket sort )或 bin sort ,顾名思义,它是通过键值的各个 的值,将要排序的 元素分配 至某些“桶”(一般是10个,表示0~9)中,达到排序的作用 2) 基数排序法是属于 稳定性 的排序,基数排序法的是效率高的稳定排序法 3) 基数排序 (Radix Sort) 桶排序 的扩展 4) 基数排序是 1887 年赫尔曼 · 何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个 位数 分别比较。

 

基数排序基本思想 1) 将所有待比较数值统一为同样的数位长度,数位较短的数前面 补0 。然后,从 最低位 开始,依次进行一次排序。比如序列中最高位为3,那就循环3次,即个、十、百位分别比较。这样从最低位排序一直到最高位排序完成以后 , 数列就变成一个有序序列。 2) 这样说明,比较难理解,下面我们看一个图文解释,理解基数排序的步骤

 

代码思路

        1.首先定义一个二维数组代表,然后定义一个一维数组记录每个桶中的元素数量

        2.准备工作

                2.1 计算序列中绝对值最大值的位数,以确定排序要执行多少次

                2.2 取序列的最小值,从而实现对负数的桶排序

        3.入、出桶 *** 作(根据最大值位数确定循环次数,每次循环时取不同的位)

                3.1 遍历序列,根据元素某位的值决定它入哪个桶

                3.2 记录每个桶中元素数量,方便出桶

                3.3 将每个桶中的元素取出放回序列中

                3.4 计数清零

                3.5 重复上面 *** 作,直到每一位都比较过了

代码演示 
 public static Integer[] RadixSort(Integer[] arr){
        Integer[][] bucket=new Integer[10][arr.length];//10个桶,放(0-9)对应位的元素
        int[] bucketEleCount=new int[10];//统计每个桶放了多少元素

        //1.1先看一下序列中最大值的位数,以确定排序要执行多少次,利用绝对值可以对负数长度进行计算
        int max=arr[0];
        int maxlength;
        for(Integer e:arr){
            if(Math.abs(e)>max) max=e;
        }
        maxlength=(Math.abs(max)+"").length();
        //1.2取最小值,在后面的 *** 作中加上最小值的绝对值,从而实现对负数的桶排序
        int min=arr[0];
        for(Integer e:arr){
            if(e

 

总结 1)  基数排序是对传统桶排序的扩展,速度很快 . 2)  基数排序是经典的空间换时间的方式,占用内存很大 , 当对海量数据排序时,容易造成 OutOfMemoryError 3) 基数排序是稳定的。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/922932.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-16
下一篇 2022-05-16

发表评论

登录后才能评论

评论列表(0条)