C语言二进制Radix Sort代码问题求助：位运算实现桶索引排序

我编写了一段C语言的二进制基数排序（Radix Sort）代码，但无法得到预期输出。需求是在radix_sort函数中通过位运算提取二进制位，以位值作为桶索引，对用户输入的数组完成排序。现有代码如下：

void radix_sort(unsigned int *array, int num, int bits);

int main()
{   
    int bits = 32;
    int num = 0;
    
    printf("Enter number of elements: ");
    scanf("%d", &num);
    
    unsigned int array[100];
    
    if(num > 100)
    {
        printf("Number of elements cannot be greater than 100.");
    }
    else
    {
        for(int i = 0; i < num; i++)
        {   
            printf("Enter a number: ");
            scanf("%u", &array[i]);
        }
    }
    
    radix_sort(array, num, bits);
    for(int i = 0; i < num; i++)
    {
        printf("%u\n", array[i]);
    }
    return 0;
}


void radix_sort(unsigned int *array, int num, int bits)
{
    unsigned int bucket_0[num];
    unsigned int bucket_1[num];
    
    for(int d = 0; d < bits; d++)
    {   
        int count0 = 0;
        int count1 = 0;
        for(int i = 0; i < num; i++)
        {
            if( ( array[d] & (1 >> i) ) != 0)
            {
                bucket_1[i] = array[d];
                count1++;
            }
            else
            {
                bucket_0[i]= array[d];
                count0++;
            }
        }
        
        int i = 0;
        for(int j = 0; j < count0; ++i, ++j)
        {
            array[i] = bucket_0[j];
        }
        
        for(int j = 0; j < count1; ++i, ++j)
        {
            array[i] = bucket_1[j];
        }
    }
    
}

代码中的核心错误 #

• 位运算逻辑完全颠倒：提取第d位时，应该针对当前数组元素array[i]，用1U << d生成掩码，而不是用array[d]和1 >> i——后者不仅索引错位，1是有符号int，左移可能触发溢出，必须用无符号的1U。
• 桶的赋值逻辑错误：把array[d]重复放入桶中，而非当前遍历的array[i]；同时用循环变量i作为桶的索引，会导致元素覆盖或位置错乱，应该用count0和count1记录桶的当前填充位置。

修正后的代码 #

void radix_sort(unsigned int *array, int num, int bits);

int main()
{   
    int bits = 32;
    int num = 0;
    
    printf("Enter number of elements: ");
    scanf("%d", &num);
    
    unsigned int array[100];
    
    if(num > 100)
    {
        printf("Number of elements cannot be greater than 100.\n");
        return 1;
    }
    else
    {
        for(int i = 0; i < num; i++)
        {   
            printf("Enter a number: ");
            scanf("%u", &array[i]);
        }
    }
    
    radix_sort(array, num, bits);
    printf("Sorted array:\n");
    for(int i = 0; i < num; i++)
    {
        printf("%u\n", array[i]);
    }
    return 0;
}


void radix_sort(unsigned int *array, int num, int bits)
{
    unsigned int bucket_0[num];
    unsigned int bucket_1[num];
    
    for(int d = 0; d < bits; d++)
    {   
        int count0 = 0;
        int count1 = 0;
        // 按当前位分桶
        for(int i = 0; i < num; i++)
        {
            // 提取第d位（从0开始，最低位为第0位）
            if( (array[i] & (1U << d)) != 0 )
            {
                bucket_1[count1++] = array[i];
            }
            else
            {
                bucket_0[count0++] = array[i];
            }
        }
        
        // 合并桶到原数组
        int idx = 0;
        for(int j = 0; j < count0; j++)
        {
            array[idx++] = bucket_0[j];
        }
        for(int j = 0; j < count1; j++)
        {
            array[idx++] = bucket_1[j];
        }
    }
}

修正说明 #

1. 修正了位运算的掩码生成和元素索引，确保正确提取每个元素的指定二进制位。
2. 用count0和count1作为桶的填充指针，避免元素覆盖。
3. 给main函数添加错误返回逻辑，当输入元素数量超过100时直接退出。
4. 优化输出提示，让结果展示更清晰。

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