深入理解基于计数排序的基数排序：二进制字符串的排序陷阱与解决方案

public static String[] radixSortBinary(String str, int stringLength) {
    // ... 将字符转换为二进制字符串数组 array ...

    // 迭代每个字符位置（从最高有效位开始）
    for (int i = stringLength-1; i >= 0; --i) { // 错误点：这里从MSB开始迭代
        array = countSort(array, i);
    }

    // ... 将二进制字符串转换回字符 ...
    return array;
}

static String[] countSort(String[] input, int position) {
    int[] count = new int[2]; // 对于二进制，只有0和1
    int n = input.length;
    String[] output = new String[n];

    // 统计每个位上的0和1的出现次数
    for (String value : input) {
        // value.length()-1 - position 计算的是从右往左数第 position 位的字符索引
        // 例如，如果 position=0，则取最右边的字符（LSB）
        // 如果 position=stringLength-1，则取最左边的字符（MSB）
        char temp = value.charAt(value.length()-1 - position); 
        count[temp - '0']++;
    }

    // 计算累积频率
    for (int i = 1; i < 2; i++) {
        count[i] = count[i] + count[i - 1];
    }

    // 将元素放入输出数组，确保稳定性
    for (int i = n - 1; i >= 0; i--) {
        char temp = input[i].charAt(input[i].length()-1 - position);
        output[count[temp - '0'] - 1] = input[i];
        count[temp - '0']--;
    }
    return output;
}

public static String[] radixSortBinary(String str, int stringLength) {
    // ... 将字符转换为二进制字符串数组 array ...

    // 迭代每个字符位置（从最低有效位开始）
    for (int i = 0; i < stringLength; ++i) { // 修正：从LSB（i=0）开始迭代
        array = countSort(array, i);
    }

    // ... 将二进制字符串转换回字符 ...
    return array;
}

// 在 radixSortBinary 方法中转换字符为二进制字符串时进行填充
char[] charArr = str.toCharArray();
String[] array = new String[charArr.length];
int maxLength = stringLength; // 假设 stringLength 是所有二进制字符串的最大预期长度

for (int i = 0; i < charArr.length; i++) {
    String binaryString = Integer.toBinaryString(charArr[i]);
    // 使用 String.format 填充前导零
    array[i] = String.format("%" + maxLength + "s", binaryString).replace(' ', '0');
}

public static char[] radixSortDirectBits(char[] inputChars, int maxBits) {
    // 假设 maxBits 是所有字符最大需要的位数，例如7或8
    char[] result = Arrays.copyOf(inputChars, inputChars.length);

    for (int bit = 0; bit < maxBits; bit++) {
        // 使用计数排序对当前位进行排序
        // 这里的计数排序需要稍微修改，以直接处理 char 值和位
        result = countSortByBit(result, bit);
    }
    return result;
}

static char[] countSortByBit(char[] input, int bitPosition) {
    int[] count = new int[2]; // 0 或 1
    int n = input.length;
    char[] output = new char[n];

    // 统计当前位是0还是1
    for (char c : input) {
        // 提取第 bitPosition 位的数值 (0 或 1)
        // (c >> bitPosition) & 1
        // 例如，bitPosition=0 提取 LSB
        int bitValue = (c >> bitPosition) & 1;
        count[bitValue]++;
    }

    // 计算累积频率
    for (int i = 1; i < 2; i++) {
        count[i] += count[i - 1];
    }

    // 将元素放入输出数组，确保稳定性
    // 必须从后往前遍历输入数组以保持稳定性
    for (int i = n - 1; i >= 0; i--) {
        int bitValue = (input[i] >> bitPosition) & 1;
        output[count[bitValue] - 1] = input[i];
        count[bitValue]--;
    }
    return output;
}