欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基数排序(桶排序)

程序员文章站 2022-03-24 15:29:12
...

1。什么是基数排序(radix sort)?
基数排序 属于分配式排序(distribution sort),又称“桶排序”(bucket sort),它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用。

2.它和归并一样,属于稳定型算法。

public void radixSort(int []arr) {

        //1.得到数组中最大的数的位数
        int max=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>max){
                max=arr[i];
            }
        }
        //判断最大数是几位数
        int maxLength=(max+"").length();

        //定义一个二维数组,表示10个桶,每个桶就是一个一位数组
        /*
        说明:
        1.二维数组包含10个一维数组;
        2.为了防止一位数组在存放数时溢出,大小定位arr.length
        3.明确:基数排序是以时间换空间的经典算法
         */

        int [][]bucket=new int[10][arr.length];

        //使用一个一维数组,来确定桶里世纪放了多少个数
        int []bucketCount=new int[10];

        for(int i=0,n=1;i<maxLength;i++,n*=10){
            //针对每个元素对应的位进行排序处理
            for(int j=0;j<arr.length;j++){
                //取出每个元素对应的位数
                int digitOfElem=arr[j]/n%10;

                //放入到对应的桶中
                bucket[digitOfElem][bucketCount[digitOfElem]]=arr[j];
                bucketCount[digitOfElem]++;
            }

            //按照桶的顺序,(一维数组的下标一次取出,放入到原数组中)
            int index=0;
            for(int k=0;k<bucket.length;k++){
                //如果桶中没有数据,不放
                if(bucketCount[k]!=0){
                    //取出元素放入到桶
                    for(int l=0;l<bucketCount[k];l++){
                        //最大长度是确定的,所以点length不出来
                        arr[index++]=bucket[k][l];
                    }
                }

                //第i+1轮处理完后,将每个bucketCount[k]=0!!
                bucketCount[k]=0;
            }

        }
       // System.out.println(Arrays.toString(arr));

    }
相关标签: 排序