C语言二进制Radix Sort（基数排序）实现困惑与相关问题咨询

AI 小北

2026-10-28

二进制Radix Sort实现困惑记录

场景基础说明

已完全理解Radix Sort的核心工作原理，可独立完成十进制数的Radix Sort实现，但迁移到二进制数场景时遇到实现阻碍
存储约束：当前场景不允许使用字符串形式存储二进制内容，使用二维数组arr_bin存储所有输入无符号整数的逐位二进制表示；pos代表所有输入数的最高位位置，例如输入12、8、4时，对应32位二进制表示的最高位在第4位，即pos=4
后续进展：曾考虑在排序桶中存储原数组的元素索引，基于索引生成最终的排序结果数组，不确定该思路的可行性；后续改用位操作替代逐位数组存储的方式后，基本解决了全部实现问题

待梳理的初始实现代码

// count 为 arr_bin 中存储的元素总数量
void sorter(int **arr_bin, unsigned int pos)
{
    unsigned int *bucket[2];
    bucket[0] = (unsigned int*) malloc(count * sizeof(unsigned int));
    bucket[1] = (unsigned int*) malloc(count * sizeof(unsigned int));

    for (int place = 31; place >= 31 - pos; place--){
        unsigned int zero_count = 0;
        unsigned int one_count = 0;
        for (int p = 0; p < count; p++){
            if(arr_bin[p][place] == 0){
                bucket[0][zero_count] = ?; // 未明确桶中需要填充的内容
                zero_count++;
            }
            else{
                bucket[1][one_count] = ?;
                one_count++;
            }
        }
        // 待实现：将两个桶的内容拼接为新的数组，完成单轮按位排序
    }
}