Java中基于计数排序的基数排序处理二进制字符串的常见陷阱与解决方案

// 迭代每个字符位置，从最不重要位（LSB）开始
for (int i = 0; i < stringLength; ++i) {
    array = countSort(array, i);
}

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

public class RadixSortBinaryTutorial {

    /**
     * 基于计数排序的稳定排序，按指定位置的二进制位进行排序。
     *
     * @param input    待排序的二进制字符串数组。
     * @param position 要排序的位的位置（0表示最低位，stringLength-1表示最高位）。
     * @return 经过一轮排序后的字符串数组。
     */
    static String[] countSort(String[] input, int position) {
        // 基数是2（0或1）
        int[] count = new int[2];
        int n = input.length;
        String[] output = new String[n];

        // 统计每个位（0或1）出现的次数
        for (String value : input) {
            // 获取当前位置的位。position=0是最低位，stringLength-1是最高位。
            // value.length() - 1 - position 确保从右往左访问位。
            char bit = value.charAt(value.length() - 1 - position);
            count[bit - '0']++;
        }

        // 累计计数，确定每个元素在输出数组中的最终位置
        for (int i = 1; i < 2; i++) {
            count[i] = count[i] + count[i - 1];
        }

        // 从后往前遍历输入数组，将元素放置到正确的位置，确保稳定性
        for (int i = n - 1; i >= 0; i--) {
            char bit = input[i].charAt(input[i].length() - 1 - position);
            output[count[bit - '0'] - 1] = input[i];
            count[bit - '0']--;
        }
        return output;
    }

    /**
     * 对字符的二进制表示进行基数排序。
     *
     * @param str          输入的原始字符串。
     * @param stringLength 预期二进制字符串的最大长度（用于零填充）。
     * @return 排序后的字符数组。
     */
    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]);
            // 使用String.format进行零填充
            array[i] = String.format("%" + stringLength + "s", binaryString).replace(' ', '0');
        }

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

        // 2. 迭代每个字符位置，从最不重要位（LSB）到最重要位（MSB）进行计数排序
        // i = 0 对应最低位 (LSB)
        // i = stringLength-1 对应最高位 (MSB)
        for (int i = 0; i < stringLength; ++i) {
            array = countSort(array, i);
        }

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

        // 3. 将排序后的二进制字符串转换回字符
        String[] resultArray = new String[array.length];
        for (int i = 0; i < array.length; i++) {
            // 注意：这里假设每个二进制字符串都代表一个字符。
            // 如果一个二进制字符串可能包含多个字符的二进制表示，
            // 则需要根据原始的分割逻辑进行调整。
            // 原始代码中的分割逻辑 `Arrays.stream(array[i].split("(?<=\G.{7})"))`
            // 意味着每个7位是一个字符。如果输入字符串本身就是由多字符组成，
            // 且每个字符被独立排序，那么这里也应该独立转换。
            // 鉴于原始问题是将单个字符转换为二进制，这里也按单个字符转换。
            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("请输入字符串: ");
        String inputStr = scan.next();

        // 假设ASCII字符最大需要7位二进制表示
        // 如果处理Unicode字符，可能需要更大的stringLength
        String[] result = radixSortBinary(inputStr, 7);
        System.out.println("Output (sorted characters):" + Arrays.toString(result));
        scan.close();
    }
}

请输入字符串: abcdefgdftglkgfdj
Binary input (padded):[01100001, 01100010, 01100011, 01100100, 01100101, 01100110, 01100111, 01100100, 01100110, 01110100, 01100111, 01101100, 01101011, 01101111, 01101100, 01101011, 01101111]
Binary output (sorted):[01100001, 01100010, 01100011, 01100100, 01100100, 01100101, 01100110, 01100110, 01100110, 01100111, 01100111, 01101010, 01101011, 01101011, 01101100, 01101100, 01110100]
Output (sorted characters):[a, b, c, d, d, e, f, f, f, g, g, j, k, k, l, l, t]