关于Radix Sort（基数排序）的实现疑问：二进制数组场景如何处理？

首先明确：是的，针对二进制数数组实现基数排序时，确实应该用二进制系统的桶数组（也就是仅2个桶，对应0和1）。

核心逻辑不变，基数进制匹配输入数的进制 #

基数排序的核心是按**从低位到高位（或高位到低位）**逐位处理，每一位根据当前位的数值分配到对应桶中，再按桶的顺序收集元素完成一轮排序。不管输入是十进制还是二进制，这个逻辑都通用——唯一的区别就是桶的数量等于当前使用的基数进制数：

• 十进制基数排序用10个桶（0-9）
• 二进制基数排序用2个桶（0和1）

二进制基数排序的具体步骤 #

假设输入是二进制数的数组（可以是存储为字符串的二进制数，也可以是整数类型的二进制值，处理方式略有不同）：

1. 确定最大位数：遍历数组，找到二进制数的最长位数，不足的前面补0（保证所有数位数一致）
2. 逐位处理：从最低位到最高位（或反过来，取决于你用LSD还是MSD基数排序）：
   • 创建两个桶：bucket_0 和 bucket_1
   • 遍历数组中的每个数，提取当前处理位的数值（0或1），将数放入对应桶中
   • 按 bucket_0 在前、bucket_1 在后的顺序，把两个桶里的元素重新拼接成新数组，作为下一轮的输入
3. 完成排序：当所有位处理完毕，数组就是有序的

代码示例（Python） #

处理字符串格式的二进制数

def radix_sort_binary(bin_arr):
    # 确定最大位数
    max_len = max(len(bin_str) for bin_str in bin_arr)
    # 补前导0，统一长度
    padded_arr = [bin_str.zfill(max_len) for bin_str in bin_arr]
    
    for i in range(max_len-1, -1, -1):  # 从最低位到最高位遍历
        bucket_0 = []
        bucket_1 = []
        for num in padded_arr:
            bit = num[i]
            if bit == '0':
                bucket_0.append(num)
            else:
                bucket_1.append(num)
        # 合并桶，保持顺序
        padded_arr = bucket_0 + bucket_1
    
    # 可选：去掉前导0，转成十进制字符串输出
    return [str(int(bin_str, 2)) for bin_str in padded_arr]

# 测试
binary_nums = ["101", "11", "1", "1000", "10"]
sorted_nums = radix_sort_binary(binary_nums)
print(sorted_nums)  # 输出: ['1', '10', '11', '101', '1000']

处理整数类型的二进制数（本质是十进制整数，按二进制位处理）

def radix_sort_binary_int(int_arr):
    if not int_arr:
        return []
    # 确定最大数的二进制位数
    max_num = max(int_arr)
    max_bits = max_num.bit_length()
    
    for bit_pos in range(max_bits):
        bucket_0 = []
        bucket_1 = []
        for num in int_arr:
            # 用位运算提取当前位的数值
            current_bit = (num >> bit_pos) & 1
            if current_bit == 0:
                bucket_0.append(num)
            else:
                bucket_1.append(num)
        int_arr = bucket_0 + bucket_1
    
    return int_arr

# 测试
int_nums = [5, 3, 1, 8, 2]
sorted_int = radix_sort_binary_int(int_nums)
print(sorted_int)  # 输出: [1, 2, 3, 5, 8]

为什么不用十进制桶？ #

如果强行用十进制桶处理二进制数，完全没必要——不仅会浪费9个空桶，还会增加不必要的位转换开销（比如把二进制位转成十进制数再分配桶），效率远不如用二进制桶直接处理。基数排序的效率优势之一就是基数越小，每轮的操作成本越低，二进制基数排序的每一轮分配/收集操作其实是非常高效的，甚至可以用位运算加速。

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