排序算法之基数排序

逃离我推掉我的手 2023-07-13 05:57 21阅读 0赞

**基数排序(桶排序)介绍**

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

**基数排序基本思想**

将所有待排序元素统一为同样的位数长度，位数较短的数前面补零，然后，从最低位开始，依次进行一轮排序，这样从最低位排序一直到最高位排序完成以后, 序列就变成一个有序序列

**基数排序说明**

（1）基数排序是对传统桶排序的扩展，速度很快  
（2）基数排序是经典的空间换时间的方式，占用内存很大，当对海量数据排序时，容易造成OutOfMemoryError  
（3）基数排序时稳定的\[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r\[i\]=r\[j\]，且 r\[i\]在 r\[j\]之前，而在排序后的序列中，r\[i\]仍在 r\[j\]之前，则称这种排序算法是稳定的，否则称为不稳定的\]  
（4）有负数的数组，不用基数排序来进行排序

**基数排序图解过程**

将数组 \{53, 3, 542, 748, 14, 214\} 使用基数排序, 进行升序排序

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70][]

**代码实现**

package com.zzb.sort;
    
    import java.util.Arrays;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/3/10 22:25
     * @Description: 基数排序
     */
    public class RadixSort {
        public static void main(String[] args) {
            int[] array = {53, 3, 542, 748, 14, 214};
    
            radixSort(array);
            System.out.println(Arrays.toString(array));
            /*[3, 14, 53, 214, 542, 748]*/
        }
    
        /**
         * 基数排序算法
         * @param array 待排序数组
         */
        private static void radixSort(int[] array) {
            // 求出数组中的最大值，确定基数排序要进行几轮数组元素的装桶操作
            int maxValue = array[0]; // 默认第一个元素为最大值
            for(int i = 1; i < array.length; i++) {
                if(maxValue < array[i]) {
                    maxValue = array[i];
                }
            }
            // 求出最大值的字符串形式的长度
            int length = String.valueOf(maxValue).length();
            // 定义一个二维数组，二维数组中的每一个一维数组表示一个桶，由于有0-9不同的数字10个，所以需要10个桶，即10个一维数组
            // 一维数组的长度为待排序数组的长度，保证存储空间足够
            int[][] buckets = new int[10][array.length];
            // 定义一个一维数组，来记录每个桶中实际存储的元素个数，一维数组的下标对应二维数组中每一个一维数组（桶）的索引，即索引为几就对应第几个桶
            // 初始化为每一个桶中实际存储的元素个数为0，有10个则长度为10
            int[] bucketElementCounts = new int[10];
            // 根据最大值的字符串形式的长度来确定基数排序要进行几轮数组元素的装桶操作
            // 对每个元素的对应位进行排序处理，第一次是个位，第二次是十位，第三次是百位..
            int count; // 每一个桶中实际存储元素个数的计数器 并且 也作为二维数组的列索引
            for(int j = 0, n = 1; j < length; j++, n *= 10) {
                // 每一轮中数组中的所有元素都要进行装桶操作
                for(int k = 0; k < array.length; k++) {
                    // 得出每个元素对应位置上的值 并且 值即为二维数组中对应的一维数组（即桶）
                    int digitOfElement = array[k] / n % 10; // 获取正整数各个位上的值的小算法
                    // 元素装桶
                    count = bucketElementCounts[digitOfElement];
                    buckets[digitOfElement][count] = array[k];
                    // 桶中实际存储元素的个数加1
                    bucketElementCounts[digitOfElement] = count + 1;
                }
                // 按照桶的顺序把各个桶中的若干元素放到array数组中，完成一轮基数排序的装桶操作
                int index = 0; // 数组array的开始索引
                for(int l = 0; l < buckets.length; l++) {
                    // 取出每一个桶中的元素放到array数组中
                    int[] bucket = buckets[l];
                    for(int m = 0; m < bucketElementCounts[l]; m++) {
                        array[index] = bucket[m];
                        index ++;
                    }
                    // 取完元素之后要把每一个桶中实际存储的个数重置为0
                    bucketElementCounts[l] = 0;
                }
            }
        }
    }

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