如何用递归实现针对0-999数组的多轮拆分桶排序？

核心思路 #

针对0-999的数组，我们需要按个位→十位→百位分3次拆分桶（每次拆10个子桶），核心是通过递归遍历每个桶，对每个非空桶重复执行桶拆分逻辑，直到处理完最高位（百位）。具体逻辑：

• 每次按当前位（由divider控制：1对应个位、10对应十位、100对应百位）将元素分到10个桶中
• 对每个非空桶，递归调用桶排序，处理更高一位（divider *= 10）
• 当divider超过数组最大元素的最高位除数时（比如最大元素是999，divider=1000时），停止递归，直接合并桶即可

修正后的代码实现 #

#include <stdio.h>

// 获取数组最大值
int getMax(int arr[], int size) {
    int max = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

void bucketSort(int arr[], int size, int divider) {
    int bucketCount = 10;
    int i, j, k;
    // 创建10个桶，每个桶最多容纳size个元素
    int buckets[bucketCount][size];
    int bucketSizes[bucketCount] = {0};
    int max = getMax(arr, size);

    // 1. 将元素按当前位分到对应桶中
    for (i = 0; i < size; i++) {
        // 计算当前位的数字（个位/十位/百位）
        int digit = (arr[i] / divider) % bucketCount;
        buckets[digit][bucketSizes[digit]] = arr[i];
        bucketSizes[digit]++;
    }

    // 2. 递归处理每个非空桶，直到处理完最高位
    if (divider <= max / 10) { // 还有更高位需要处理
        for (i = 0; i < bucketCount; i++) {
            if (bucketSizes[i] > 0) {
                // 递归调用，处理下一位（divider*10）
                bucketSort(buckets[i], bucketSizes[i], divider * 10);
            }
        }
    }
    // 3. 将桶中元素合并回原数组
    k = 0;
    for (i = 0; i < bucketCount; i++) {
        for (j = 0; j < bucketSizes[i]; j++) {
            arr[k++] = buckets[i][j];
        }
    }
}

// 测试用例
int main() {
    int arr[] = {456, 123, 789, 321, 654, 987, 111, 222, 333};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    // 初始调用，从个位开始处理（divider=1）
    bucketSort(arr, size, 1);
    
    printf("排序后的数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

关键细节说明 #

• 修正位计算逻辑：原代码中j = floor(arr[i]/divider)会导致索引越界，改为(arr[i]/divider)%10才能正确提取当前位的数字
• 递归终止条件：当divider > max/10时，说明已经处理完最高位（比如999的最高位是百位，divider=100时，max/10=99，100>99，停止递归），此时桶内元素已经通过低位的递归处理完成排序
• 桶的复用：每次递归都会创建新的10个桶，处理当前位的拆分，避免了手动遍历多层桶的复杂度

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