数据结构与算法之基数排序

墨蓝 2023-07-09 08:25 2阅读 0赞

\*\*

## 算法思想： ##

**基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。**\*\*

**图解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70]

**代码**

package com.yg.sort;/*
    @author  Mu_Mu
    @date    2020/2/28  13:15
    */
    
    import java.util.Arrays;
    
    public class RadixSort {
        
        public static void main(String[] args) {
        
            int []arr={
        5,4,8,65,98,7,2,1,24454,5,5};
            radixSort(arr);
        }
    
        public static void radixSort(int[] arr) {
        
            //创建10个桶，按照个位，十位，百位...对arr进行排序
            int[][] bucket = new int[10][arr.length];
            //存放每个桶的元素数量
            int []buckelElementCount=new int [10];
            //获取数组最大数的位数
            int maxLength = getArrayMaxNumberDigit(arr);
            //依次按照个位，十位，百位...的数值将元素放入对应的桶中
            for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
        
                for (int j = 0; j <arr.length ; j++) {
        
                int digitElement = arr[j] / n % 10;
                bucket[digitElement][buckelElementCount[digitElement]]=arr[j];
                buckelElementCount[digitElement]++;
                }
                //用于遍历arr
                int index=0;
                //按照顺序将桶中的元素放入arr中
                for (int k = 0; k < buckelElementCount.length; k++) {
        
                    if(buckelElementCount[k]!=0){
        
                        for (int l = 0; l < buckelElementCount[k]; l++) {
        
                            arr[index]=bucket[k][l];
                            index++;
                        }
                    }
                    buckelElementCount[k]=0;
                }
                System.out.println("第"+(i+1)+"轮排序处理arr="+ Arrays.toString(arr));
            }
        }
    
        //获取数组最大数的位数
        private static int getArrayMaxNumberDigit(int[] arr) {
        
            int max = arr[0];
            int maxLength = 0;
            for (int i = 1; i < arr.length; i++) {
        
                if (max < arr[i]) {
        
                    max = arr[i];
                }
            }
            maxLength = (max + "").length();
            return maxLength;
        }
    
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200228135631567.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk=,size_16,color_FFFFFF,t_70