C语言桶排序传入Bubblesort无作用，求助排查代码问题

你的代码核心问题出在冒泡排序函数的大小计算逻辑错误，同时桶索引的计算存在边界偏差，导致排序未生效。以下是具体问题和修复步骤：

1. 冒泡排序函数的致命错误 #

在bubblesort中，你添加了多余的size /= sizeof(int);语句：

void bubblesort (int arr[], unsigned char size) {
    size /= sizeof(int); // 这行是错误的
    // ... 排序逻辑
}

但bucketsort调用sort(bucket[i], s[i])时，传入的s[i]已经是桶内的元素个数，不是字节数。这会导致size被错误缩小为原来的1/4（假设int占4字节），比如一个桶有3个元素，size会变成0，排序循环直接跳过，完全不执行排序操作。

修复方法：删除这行多余代码，同时建议把逗号表达式的交换逻辑改成临时变量交换，提升可读性并避免优先级陷阱：

void bubblesort(int arr[], unsigned char size) {
    for (unsigned char i = 0; i < size - 1; i++)
        for (unsigned char j = 0; j < size - i - 1; j++)
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

2. 桶索引计算的边界偏差 #

原代码中桶索引的计算逻辑：

n*(arr[i]-min)/(max-min+1)

整数运算下，当arr[i]等于max时，(max-min)/(max-min+1)结果为0，导致所有最大值元素都被放到第0号桶，破坏了桶的划分逻辑。

修复方法：调整计算顺序，同时添加边界检查避免索引越界：

unsigned char idx = (arr[i] - min) * n / (max - min + 1);
if (idx >= n) idx = n - 1; // 处理最大值元素的索引边界

将这段逻辑单独提取，替换原代码中重复的索引计算，既避免重复运算，又能处理边界情况。

3. 其他潜在问题修复 #

• 内存泄漏：原代码中bucket的动态分配内存未释放，需要在合并桶后添加循环释放每个桶的内存。
• 无效排序调用：当桶内元素数≤1时，无需调用排序函数，可以添加判断跳过。

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>

void bubblesort(int arr[], unsigned char size) {
    for (unsigned char i = 0; i < size - 1; i++)
        for (unsigned char j = 0; j < size - i - 1; j++)
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

void bucketsort(int arr[], unsigned char size, unsigned char n, void sort(int[], unsigned char)) {
    size /= sizeof(int);
    int *bucket[n];
    unsigned char s[n];
    
    for (unsigned char i = 0; i < n; i++) {
        s[i] = 0;
        bucket[i] = NULL;
    }
    
    int min = arr[0], max = arr[0];
    for (unsigned char i = 1; i < size; i++) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }
    
    for (unsigned char i = 0; i < size; i++) {
        unsigned char idx = (arr[i] - min) * n / (max - min + 1);
        if (idx >= n) idx = n - 1;
        
        s[idx]++;
        bucket[idx] = (int*)realloc(bucket[idx], s[idx] * sizeof(int));
        bucket[idx][s[idx] - 1] = arr[i];
    }
    
    // 对每个桶排序（仅当元素数>1时）
    for (unsigned char i = 0; i < n; i++) {
        if (s[i] > 1)
            sort(bucket[i], s[i]);
    }
    
    // 合并桶到原数组并释放内存
    for (int i = 0, index = 0; i < n; i++) {
        for (int j = 0; j < s[i]; j++) 
            arr[index++] = bucket[i][j];
        free(bucket[i]);
    }
}

int main(void) {
    int a[] = {3,6,4,9,1,7,5,8,2,0};
    bucketsort(a, sizeof(a), 4, bubblesort);
    
    for (signed char i = 0; i < (signed char)(sizeof(a)/sizeof(int)); i++) 
        printf("%d, ", a[i]);
    
    return 0;
}

运行结果 #

修复后执行代码，会输出正确的排序结果：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 

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