基数排序

算法定义

基数排序（Radix Sort）是一种非比较型排序算法，它通过按数字的 "位"（个位、十位、百位等）或字符的 "基数"（如 ASCII 码）进行排序。与比较型排序（如快速排序、归并排序）不同，基数排序不通过比较元素大小来排序，而是利用 "分配 - 收集" 的过程，按每个位的优先级依次排序，最终实现整体有序。

算法思路

基数排序有两种实现方式：最高位优先（MSD） 和最低位优先（LSD）。实际应用中 LSD 更为常见，步骤如下：

确定最大位数：找出数组中最大元素的位数（如最大元素是 1234，则最大位数为 4）。
按位排序：从最低位（个位）到最高位（千位）依次处理：
- 分配：将每个元素按当前位的值放入对应的桶（0-9，共 10 个桶）。
- 收集：按桶的顺序（0 到 9）将元素依次取出，组成新的数组。
重复操作：完成所有位的 "分配 - 收集" 后，数组排序完成。

例如，排序[170, 45, 75, 90, 802, 24, 2, 66]：

按个位排序：[170, 90, 802, 2, 24, 45, 75, 66]
按十位排序：[802, 2, 24, 45, 66, 170, 75, 90]
按百位排序：[2, 24, 45, 66, 75, 90, 170, 802]

算法复杂度

最好时间复杂度：O (d×(n+r)) - d 为最大位数，n 为元素个数，r 为基数（如 10）
最坏时间复杂度：O (d×(n+r)) - 与最好情况相同，不受数据分布影响
平均时间复杂度：O(d×(n+r))
空间复杂度：O (n+r) - 需要 r 个桶存储元素，总空间为 n+r

优点与缺点

优点：
- 时间复杂度低，接近线性时间 O (n)
- 稳定的排序算法（相等元素相对位置不变）
- 适合并行处理（各桶可独立操作）
- 对大数据集效率高于部分比较型排序
缺点：
- 仅适用于可按 "位" 或 "基数" 划分的数据（如整数、字符串）
- 需要额外空间存储桶和临时数据
- 对小数、负数需要特殊处理
- 位数 d 较大时，效率会下降

应用场景

整数或字符串排序（可按位或字符处理）
固定长度数据的排序（如身份证号、电话号码）
外部排序（数据量超过内存时）
对排序稳定性要求高的场景
基数较小且位数固定的场景

各版本优化说明

基本版（LSD）：
- 处理非负整数，按最低位到最高位排序
- 使用计数数组实现 "分配 - 收集" 过程
- 保证排序稳定性，实现简单直观
支持负数优化：
- 将负数转换为正数排序，再反转结果
- 分别处理负数和非负数，最后合并
- 扩展了基数排序的适用范围
计数排序子排序优化：
- 将每一位的排序单独封装为计数排序
- 代码结构更清晰，可维护性更高
- 减少重复代码，提高效率

基数排序是一种高效的非比较型排序算法，特别适合处理位数固定的整数或字符串。虽然需要额外空间，但在大数据集且基数较小时，性能优于许多比较型排序算法。实际应用中，常作为字符串排序或大型数据库排序的底层实现。

代码

import java.util.Arrays;

public class RadixSort {
    
    // 1. 基本版基数排序（LSD，处理非负整数）
    public static void radixSortBasic(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        // 找到最大值，确定最大位数
        int max = findMax(arr);
        int maxDigits = getDigits(max);
        
        // 基数为10（0-9）
        final int RADIX = 10;
        int n = arr.length;
        int[] temp = new int[n]; // 临时数组
        int[] count = new int[RADIX]; // 计数数组（桶）
        
        // 从最低位到最高位排序
        for (int digit = 1; digit <= maxDigits; digit++) {
            int divisor = (int) Math.pow(10, digit - 1); // 除数（1, 10, 100...）
            
            // 重置计数数组
            Arrays.fill(count, 0);
            
            // 统计每个桶的元素个数
            for (int num : arr) {
                int d = (num / divisor) % 10;
                count[d]++;
            }
            
            // 计算前缀和，确定每个元素在temp中的位置
            for (int i = 1; i < RADIX; i++) {
                count[i] += count[i - 1];
            }
            
            // 从后往前遍历，保证稳定性
            for (int i = n - 1; i >= 0; i--) {
                int d = (arr[i] / divisor) % 10;
                temp[count[d] - 1] = arr[i];
                count[d]--;
            }
            
            // 将temp复制回原数组
            System.arraycopy(temp, 0, arr, 0, n);
        }
    }
    
    // 2. 优化版1：处理负数（分离正负再合并）
    public static void radixSortWithNegatives(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        // 分离负数和非负数
        int[] negatives = new int[arr.length];
        int[] nonNegatives = new int[arr.length];
        int negCount = 0, nonNegCount = 0;
        
        for (int num : arr) {
            if (num < 0) {
                negatives[negCount++] = -num; // 负数取绝对值
            } else {
                nonNegatives[nonNegCount++] = num;
            }
        }
        
        // 分别排序（负数排序后需反转）
        if (negCount > 0) {
            int[] validNegatives = Arrays.copyOf(negatives, negCount);
            radixSortBasic(validNegatives);
            reverse(validNegatives); // 反转使负数从小到大
            for (int i = 0; i < negCount; i++) {
                negatives[i] = -validNegatives[i]; // 恢复负数
            }
        }
        
        if (nonNegCount > 0) {
            radixSortBasic(Arrays.copyOf(nonNegatives, nonNegCount));
        }
        
        // 合并结果（负数在前，非负数在后）
        System.arraycopy(negatives, 0, arr, 0, negCount);
        System.arraycopy(nonNegatives, 0, arr, negCount, nonNegCount);
    }
    
    // 3. 优化版2：使用计数排序作为子排序（更高效）
    public static void radixSortWithCounting(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int max = findMax(arr);
        int maxDigits = getDigits(max);
        final int RADIX = 10;
        int n = arr.length;
        
        for (int digit = 1; digit <= maxDigits; digit++) {
            int divisor = (int) Math.pow(10, digit - 1);
            countingSortByDigit(arr, divisor, RADIX);
        }
    }
    
    // 按指定位进行计数排序（子排序）
    private static void countingSortByDigit(int[] arr, int divisor, int radix) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[radix];
        
        // 统计每个位出现的次数
        for (int num : arr) {
            int d = (num / divisor) % radix;
            count[d]++;
        }
        
        // 计算前缀和
        for (int i = 1; i < radix; i++) {
            count[i] += count[i - 1];
        }
        
        // 构建输出数组（从后往前保证稳定性）
        for (int i = n - 1; i >= 0; i--) {
            int d = (arr[i] / divisor) % radix;
            output[count[d] - 1] = arr[i];
            count[d]--;
        }
        
        // 复制回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }
    
    // 辅助方法：查找最大值
    private static int findMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }
    
    // 辅助方法：计算数字的位数
    private static int getDigits(int num) {
        if (num == 0) return 1;
        int count = 0;
        while (num > 0) {
            num /= 10;
            count++;
        }
        return count;
    }
    
    // 辅助方法：反转数组
    private static void reverse(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
    
    public static void main(String[] args) {
        int[] arr1 = {170, 45, 75, 90, 802, 24, 2, 66};
        int[] arr2 = {-170, 45, -75, 90, -802, 24, 2, 66};
        int[] arr3 = {170, 45, 75, 90, 802, 24, 2, 66};
        
        radixSortBasic(arr1);
        System.out.println("基本版（非负整数）: " + Arrays.toString(arr1));
        
        radixSortWithNegatives(arr2);
        System.out.println("支持负数: " + Arrays.toString(arr2));
        
        radixSortWithCounting(arr3);
        System.out.println("计数排序优化: " + Arrays.toString(arr3));
    }
}