排序算法-基数排序

基数排序（Radix Sort）是一种非比较型整数排序算法，它通过逐位比较数字的每一位（个位、十位、百位等）进行排序。

基数排序的核心思想是：

1. 按最低位优先（LSD, Least Significant Digit） 或 按最高位优先（MSD, Most Significant Digit） 进行排序。

2. 每次排序都基于某一位（比如先排个位，再排十位，依此类推）。

3. 使用稳定的排序算法（如计数排序）作为子排序过程。

基数排序步骤（LSD）

1. 找到数组中的最大数字，确定最大位数（决定排序轮数）。

2. 构建桶，0到9的桶

3. 从最低位（个位）开始，到最高位：

   • 按位入桶

   • 桶中的数据写回原数组，清除桶，准备下一轮排序

4. 重复步骤 3，直到所有位数处理完毕，数组有序。

代码实现

package Sort;

import java.util.ArrayList;

public class RadixSort {
    public static void main(String[] args) {
        int[] res = getRadixSort(new int[]{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48});
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i]+" ");
        }
    }
    //基数排序：LSD（按低位优先）
    //步骤：
    //1.找出最大数，根据最大数计算其位数，用于决定进行几轮排序
    //2.构建桶
    //3.按位轮询
    // 3.1 按位入桶（LSD低位优先）
    // 3.2 桶中的数据写回原数组，清除桶，准备下一轮排序
    public static int[] getRadixSort(int[] nums){
        if (nums == null || nums.length < 2) return nums;
        //1.找出最大数，根据最大数计算其位数，用于决定进行几轮排序
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) max = nums[i];
        }
        //计算出最大数的位数
        int maxDigit = 0;
        while (max != 0){
            max /= 10;
            maxDigit++;
        }

        //2.构建0~9个桶
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            bucketList.add(new ArrayList<>());
        }
        //3.按位轮询
        //按照从右到左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组进行排序
        //每一轮排序都是基于上一轮排序后的结果
        int mod = 10, div = 1;
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            //3.1 按位入桶（LSD低位优先）
            //遍历原数组，投入桶中
            for (int j = 0; j < nums.length; j++) {
                int num = (nums[j] % mod) / div; //获取位数的值，根据该值入桶
                bucketList.get(num).add(nums[j]);
            }

            //3.2 桶中的数据写回原数组，清除桶，准备下一轮排序
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int k = 0; k < bucketList.get(j).size(); k++) {
                    nums[index++] = bucketList.get(j).get(k);
                }
                bucketList.get(j).clear();
            }
        }
        return nums;
    }
}

复杂度分析

• n：数据规模

• d：最大数字的位数（如 802 有 3 位）

• k：基数（十进制时 k=10，二进制 k=2）

适合场景

• 整数排序（特别是位数较少的整数，如手机号、身份证号）。

• 需要稳定排序的场景。