基于计数排序的基数排序：处理二进制数据时的常见陷阱与解决方案

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

// 修正迭代方向：从最低有效位（LSB）到最高有效位（MSB）
for (int i = 0; i < stringLength; ++i) { // LSB-first
    array = countSort(array, i);
}

// 原始的字符到二进制字符串转换
char[] charArr = str.toCharArray();
String[] array = new String[charArr.length];
for (int i = 0; i < charArr.length; i++) {
    // 使用String.format进行左侧补零，确保所有二进制字符串长度一致
    // 例如，如果stringLength是7，Integer.toBinaryString(charArr[i])得到"1100001"
    // String.format("%7s", "1100001") 得到 "1100001"
    // 如果得到"1"，String.format("%7s", "1") 得到 "      1"，再replace(' ', '0') 得到 "0000001"
    array[i] = String.format("%" + stringLength + "s", Integer.toBinaryString(charArr[i])).replace(' ', '0');
}

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

public class RadixSortBinaryTutorial {

    /**
     * 基于计数排序的稳定子排序方法，用于对指定位进行排序。
     *
     * @param input    待排序的二进制字符串数组。
     * @param position 当前要排序的位索引（0为最低位，stringLength-1为最高位）。
     * @return 经过当前位排序后的字符串数组。
     */
    static String[] countSort(String[] input, int position) {
        // 计数数组，用于存储'0'和'1'的出现次数
        // count[0] 存储 '0' 的计数， count[1] 存储 '1' 的计数
        int[] count = new int[2];
        int n = input.length;

        // 临时字符变量，用于存储当前位的字符
        char tempChar;
        // 遍历输入数组，统计每个位上 '0' 和 '1' 的出现次数
        for (String value : input) {
            // 获取当前位上的字符。
            // value.length() - 1 - position 确保从右向左（最低位到最高位）正确索引。
            // 例如，对于长度为7的字符串，position=0 (最低位) 对应索引6，position=6 (最高位) 对应索引0。
            tempChar = value.charAt(value.length() - 1 - position);
            // 将字符 '0' 或 '1' 转换为整数 0 或 1，并增加相应计数
            count[tempChar - '0']++;
        }

        // 将计数数组转换为累积计数数组
        // count[i] 现在表示小于或等于 i 的元素的数量
        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--) {
            tempChar = input[i].charAt(input[i].length() - 1 - position);
            // 根据累积计数，确定当前元素在输出数组中的位置
            output[count[tempChar - '0'] - 1] = input[i];
            // 减少对应位的计数，为下一个具有相同位的元素腾出位置
            count[tempChar - '0']--;
        }

        return output;
    }

    /**
     * 实现二进制字符串的基数排序。
     *
     * @param str          待排序的原始字符串。
     * @param stringLength 指定的二进制字符串长度（例如，7位用于ASCII字符）。
     * @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++) {
            // 确保所有二进制字符串长度一致，左侧补零
            array[i] = String.format("%" + stringLength + "s", Integer.toBinaryString(charArr[i])).replace(' ', '0');
        }

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

        // 步骤2: 执行LSB-first基数排序
        // 修正迭代方向：从最低有效位（LSB，position=0）到最高有效位（MSB，position=stringLength-1）
        for (int i = 0; i < stringLength; ++i) { // LSB-first
            array = countSort(array, i);
        }

        System.