无二维数组/列表的基数排序实现问题：多位数报错求助

核心问题根源 #

你代码里用pow(10, i)计算位权的方式会导致浮点精度误差。pow是浮点运算函数，比如pow(10,4)实际计算结果可能是9999.999999999998，强制转成int后就变成9999，而非预期的10000。这会让你提取高位数字时计算错误，导致temp值异常，进而让count[temp]超出数组范围或者指向错误的dest下标，触发dest[count[temp]]=b[j];的错误。

修复方案 #

把浮点运算的位权计算换成整数乘法，完全避免精度问题。同时可以简化基数提取的逻辑，让代码更清晰。另外，你当前的计数前缀和计算方式效率较低，可以优化成更常规的前缀和累加方式。

修复后的完整代码 #

#include <iostream>
using namespace std;

int* radix(int n, int* a, int k) {
    int m = 10;
    int count[10], dest[n];
    int* b = a;
    int divisor = 1; // 用整数除法计算位权，初始为个位

    for (int i = 0; i < k; i++) {
        // 1. 初始化计数数组
        for (int j = 0; j < m; j++) {
            count[j] = 0;
        }

        // 2. 统计当前位的数字出现次数
        for (int j = 0; j < n; j++) {
            int digit = (b[j] / divisor) % 10; // 简化的基数提取逻辑
            count[digit]++;
        }

        // 3. 计算前缀和，得到每个数字的起始存放位置
        for (int j = 1; j < m; j++) {
            count[j] += count[j - 1];
        }

        // 4. 反向遍历原数组，放入目标数组（保证稳定性）
        for (int j = n - 1; j >= 0; j--) {
            int digit = (b[j] / divisor) % 10;
            dest[--count[digit]] = b[j]; // 先减1再赋值，对应起始位置
        }

        // 5. 将排序结果复制回原数组
        for (int j = 0; j < n; j++) {
            b[j] = dest[j];
        }

        // 打印当前轮结果（可选）
        for (int j = 0; j < n; j++) {
            cout << b[j] << ' ';
        }
        cout << endl << endl;

        // 更新位权，处理下一位
        divisor *= 10;
    }

    return b;
}

// 测试示例
int main() {
    int arr[] = {1234, 5678, 9012, 3456, 7890, 2345, 6789, 123};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4; // 按4位数字处理
    radix(n, arr, k);
    return 0;
}

关键改动说明 #

• 替换位权计算：用divisor整数变量，每次循环乘10，提取当前位用(b[j]/divisor)%10，彻底避免浮点误差。
• 优化前缀和计算：从左到右累加计数数组，得到每个数字在dest中的结束位置，反向遍历原数组时先减1得到起始位置，保证基数排序的稳定性。
• 修复数组访问逻辑：原代码中count[temp]直接作为下标可能越界，通过前缀和的正确计算，确保下标始终在0~n-1范围内。

内容的提问来源于stack exchange，提问作者Piece - kun