基于计数排序的基数排序对二进制字母排序异常问题求助

你的二进制基数排序结果不符合预期，核心存在两个关键问题：

1. 基数排序的位遍历顺序完全错误 #

基数排序（LSD最低位优先）要求从最右侧的最低有效位（LSB）开始排序，逐步往左处理最高有效位（MSB），但你的代码是从最左侧的高位开始遍历到低位：

// 错误：从高位到低位遍历
for (int i = stringLength-1; i >= 0; --i) {
    array = countSort(array, i);
}

这种MSB优先的方式不适合用迭代计数排序实现，后续低位的排序会打乱之前高位排好的顺序，最终导致结果混乱。

2. 二进制字符串未补前导零 #

Integer.toBinaryString(char)返回的字符串没有前导零，比如ASCII值为32的空格，二进制是100000（仅6位），这会引发两个问题：

• 访问value.charAt(value.length()-1 - position)时出现索引越界
• 位位置计算错误，不同长度的字符串无法对齐相同权重的二进制位

修正后的完整代码 #

import java.util.Arrays;
import java.util.Scanner;

public class RadixSortBinaryFix {
    static String[] countSort(String[] input, int position) {
        int[] count = new int[2];
        int n = input.length;

        char temp;
        for (String value : input) {
            temp = value.charAt(value.length() - 1 - position);
            count[temp - '0']++;
        }

        for (int i = 1; i < 2; i++) {
            count[i] = count[i] + count[i - 1];
        }

        String[] output = new String[n];
        for (int i = n - 1; i >= 0; i--) {
            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) {
        char[] charArr = str.toCharArray();
        String[] array = new String[charArr.length];
        for (int i = 0; i < charArr.length; i++) {
            // 补前导零到指定长度，确保所有二进制字符串长度一致
            array[i] = String.format("%" + stringLength + "s", Integer.toBinaryString(charArr[i])).replace(' ', '0');
        }

        System.out.println("Binary input:" + Arrays.toString(array));

        // 修正遍历顺序：从最低位到最高位
        for (int i = 0; i < stringLength; i++) {
            array = countSort(array, i);
        }

        System.out.println("Binary output:" + Arrays.toString(array));

        // 转换回字母
        String[] result = new String[array.length];
        for (int i = 0; i < array.length; i++) {
            result[i] = String.valueOf((char) Integer.parseInt(array[i], 2));
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String input2 = scan.next();

        String[] result = radixSortBinary(input2, 7);
        System.out.println("Output:" + Arrays.toString(result));
        scan.close();
    }
}

关键修改说明 #

1. 补前导零：用String.format将每个二进制字符串补全到7位，确保所有字符串长度一致，避免索引越界和位位置计算错误。
2. 修正遍历顺序：将循环改为从i=0到i<stringLength-1，也就是从最右侧的最低位开始处理，逐步往左到最高位，符合LSD基数排序的要求。

测试验证 #

用你的第二个测试案例abcdefgdftglkgfdj测试，修正后的输出会是：

Output:[a, b, c, d, d, d, e, f, f, f, g, g, g, j, k, l, t]

完全符合ASCII字符的升序排序结果。

内容的提问来源于stack exchange，提问作者Flamenco