import java.util.Arrays;

public class RadixSort {
    
    /**
     * LSD 基数排序（适用于非负整数）
     */
    public static void sortLSD(int[] arr) {
        if (arr.length <= 1) return;
        
        // 找到最大值，确定位数
        int max = arr[0];
        for (int value : arr) {
            if (value > max) max = value;
        }
        
        // 从最低位开始，对每一位进行计数排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }
    
    /**
     * 按指定位数进行计数排序
     * @param exp 当前处理的位数（1=个位，10=十位，100=百位...）
     */
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];  // 0-9 共 10 个数字
        
        // 统计每个数字出现的次数
        for (int value : arr) {
            int digit = (value / exp) % 10;
            count[digit]++;
        }
        
        // 计算累计次数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        
        // 从后往前遍历，保持稳定性
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }
        
        // 复制回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }
    
    /**
     * LSD 基数排序（适用于包含负数的整数）
     */
    public static void sortLSDWithNegative(int[] arr) {
        if (arr.length <= 1) return;
        
        // 分离正数和负数
        int negativeCount = 0;
        for (int value : arr) {
            if (value < 0) negativeCount++;
        }
        
        int[] negatives = new int[negativeCount];
        int[] positives = new int[arr.length - negativeCount];
        
        int negIndex = 0, posIndex = 0;
        for (int value : arr) {
            if (value < 0) {
                negatives[negIndex++] = -value;  // 转为正数处理
            } else {
                positives[posIndex++] = value;
            }
        }
        
        // 分别排序
        sortLSD(negatives);
        sortLSD(positives);
        
        // 合并：负数逆序放前面，正数顺序放后面
        int index = 0;
        for (int i = negatives.length - 1; i >= 0; i--) {
            arr[index++] = -negatives[i];
        }
        for (int value : positives) {
            arr[index++] = value;
        }
    }
    
    /**
     * MSD 基数排序（适用于字符串）
     */
    public static void sortStrings(String[] arr) {
        if (arr.length <= 1) return;
        String[] temp = new String[arr.length];
        msdSort(arr, temp, 0, arr.length - 1, 0);
    }
    
    private static void msdSort(String[] arr, String[] temp, int low, int high, int charIndex) {
        if (low >= high) return;
        
        int R = 256;  // ASCII 字符集大小
        int[] count = new int[R + 2];  // 多两个用于处理字符串结束的情况
        
        // 统计频率
        for (int i = low; i <= high; i++) {
            int c = charAt(arr[i], charIndex);
            count[c + 2]++;
        }
        
        // 计算累计频率
        for (int r = 0; r < R + 1; r++) {
            count[r + 1] += count[r];
        }
        
        // 分配
        for (int i = low; i <= high; i++) {
            int c = charAt(arr[i], charIndex);
            temp[count[c + 1]++] = arr[i];
        }
        
        // 复制回原数组
        System.arraycopy(temp, 0, arr, low, high - low + 1);
        
        // 递归处理每个字符组
        for (int r = 0; r < R; r++) {
            msdSort(arr, temp, low + count[r], low + count[r + 1] - 1, charIndex + 1);
        }
    }
    
    private static int charAt(String s, int index) {
        if (index < s.length()) {
            return s.charAt(index);
        }
        return -1;  // 字符串结束
    }
    
    /**
     * 基数排序（泛型版本，适用于实现了整数转换接口的类型）
     */
    public static void sortGeneric(int[] arr, int base) {
        if (arr.length <= 1) return;
        
        int max = arr[0];
        for (int value : arr) {
            if (value > max) max = value;
        }
        
        for (int exp = 1; max / exp > 0; exp *= base) {
            countingSortByDigitBase(arr, exp, base);
        }
    }
    
    private static void countingSortByDigitBase(int[] arr, int exp, int base) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[base];
        
        for (int value : arr) {
            int digit = (value / exp) % base;
            count[digit]++;
        }
        
        for (int i = 1; i < base; i++) {
            count[i] += count[i - 1];
        }
        
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % base;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }
        
        System.arraycopy(output, 0, arr, 0, n);
    }
}