纠正二进制字符串的基数排序：迭代顺序与长度一致性解析

// iterate over each character position (starting from the least significant)
for (int i = stringLength-1; i >= 0; --i) {
    array = countSort(array, i);
}

for (int i = stringLength-1; i >= 0; --i) {
    array = countSort(array, i);
}

for (int i = 0; i < stringLength; i++) { // 从最低有效位 (0) 迭代到最高有效位 (stringLength-1)
    array = countSort(array, i);
}

for (int i=0; i<charArr.length; i++)
    array[i] = Integer.toBinaryString(charArr[i]);

for (int i = 0; i < charArr.length; i++) {
    String binaryString = Integer.toBinaryString(charArr[i]);
    // 使用 String.format 进行零填充，确保所有二进制字符串长度一致
    // 例如，如果 stringLength 为 7，"100000" 会变成 "0100000"
    array[i] = String.format("%" + stringLength + "s", binaryString).replace(' ', '0');
}

import java.util.Arrays;
import java.util.Scanner;
import java.lang.StringBuilder; // 明确导入 StringBuilder

public class RadixSortBinaryTutorial {

    // 计数排序辅助方法，用于按指定位排序
    static String[] countSort(String[] input, int position) {
        int[] count = new int[2]; // 针对二进制位 (0 或 1)
        int n = input.length;

        // 统计当前位 (position) 上 0 和 1 的出现次数
        for (String value : input) {
            // value.length()-1 - position 确保从右往左 (LSD) 正确访问位
            // 例如，对于 "01100001"，position=0 访问 '1'，position=1 访问 '0'
            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];
        }

        String[] output = new String[n];
        // 从后往前遍历输入数组，保证排序稳定性
        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) {
        char[] charArr = str.toCharArray();
        String[] array = new String[charArr.length];

        // 1. 将字符转换为二进制字符串并进行零填充，确保长度一致
        for (int i = 0; i < charArr.length; i++) {
            String binaryString = Integer.toBinaryString(charArr[i]);
            // 零填充到 stringLength 长度
            array[i] = String.format("%" + stringLength + "s", binaryString).replace(' ', '0');
        }

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

        // 2. 迭代每个字符位置，从最低有效位 (0) 到最高有效位 (stringLength-1)
        for (int i = 0; i < stringLength; i++) { // 修正循环顺序
            array = countSort(array, i);
        }

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

        // 3. 将排序后的二进制字符串转换回字符
        StringBuilder sb = new StringBuilder();
        String[] resultArray = new String[array.length]; // 存储最终的字符数组
        for (int i = 0; i < array.length; i++) {
            // 这里假设每个二进制字符串代表一个字符，且长度为 stringLength
            // 如果需要按7位分割，原代码的分割逻辑是：
            // Arrays.stream(array[i].split("(?<=\G.{7})")).forEach(s -> sb.append((char) Integer.parseInt(s, 2)));
            // 但考虑到这里 array[i] 已经是一个完整的字符的二进制表示，直接转换即可
            resultArray[i] = String.valueOf((char) Integer.parseInt(array[i], 2));
        }

        return resultArray;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.print("Enter input string: ");
        String input2 = scan.next();

        // 假设每个字符的二进制表示是 7 位
        String[] result = radixSortBinary(input2, 7);
        System.out.println("Output (sorted characters):" + Arrays.toString(result));
        scan.close();
    }
}

input: abcdefgdftglkgfdj
Binary input (padded):[1100001, 1100010, 1100011, 1100100, 1100101, 1100110, 1100111, 1100100, 1100110, 1110100, 1100111, 1101100, 1101011, 1100111, 1100110, 1100100, 1101010]
Binary output (sorted):[1100001, 1100010, 1100011, 1100100, 1100100, 1100100, 1100101, 1100110, 1100110, 1100110, 1100111, 1100111, 1100111, 1101010, 1101011, 1101100, 1110100]
Output (sorted characters):[a, b, c, d, d, d, e, f, f, f, g, g, g, j, k, l, t]