基数排序详细图解和代码实现

迷南。 2023-07-07 04:58 54阅读 0赞

## 基数排序 ##

基数排序的步骤：  
1，首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中。  
2，接下来将这些桶子中的数值重新串接起来，成为以下的数列。  
3，接着再进行一次分配，这次是根据十位数来分配。  
4.接下来将这些桶子中的数值重新串接起来  
5，如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70]

Java代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    /**
     * 描述:基数排序
     */
    public class BaseSort {
        
        public static void main(String[] args) {
        
            int[] arr = new int[]{
        67, 85, 378, 478, 156, 9, 45, 0, 12, 7, 5};
            System.out.println(Arrays.toString(arr));
            baseSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        private static void baseSort(int[] arr) {
        
            int max = arr[0];
            //找出最大数
            for (int i = 1; i < arr.length; i++) {
        
                if (max < arr[i]) {
        
                    max = arr[i];
                }
            }
            //找出最大数是多少位
            int times = 0;
            while (max != 0) {
        
                max /= 10;
                times++;
            }
            //总共循环times次
            for (int i = 0; i < times; i++) {
        
                //创建10个 保存余数为 0~9的数
                List<ArrayList<Integer>> lists  = new ArrayList<>();
                 for (int j = 0; j < 10; j++) {
        
                    lists.add(new ArrayList<>());
                }
                for (int j = 0; j < arr.length; j++) {
        
                     //123    123   1
                    int x = arr[j] % (int) Math.pow(10,i+1)/(int)Math.pow(10,i);
                    ArrayList<Integer> tmp = lists.get(x);
                    tmp.add(arr[j]);
                }
                int count = 0;
                for (int j = 0; j < 10; j++) {
        
                    while (lists.get(j).size()>0) {
        
                        ArrayList<Integer> tmp = lists.get(j);
                        arr[count++] = tmp.get(0);
                        tmp.remove(0);
                    }
                }
            }
        }
    }

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