C++数组怎么实现基数排序-C++-PHP中文网

适合，但必须是整型数组且元素非负；lsd基数排序可用原生数组实现，通过按位计数排序+辅助数组稳定重排，负数需偏移处理，浮点数需转整型。

c++数组怎么实现基数排序

基数排序适合用C++数组实现吗

适合，但必须是整型数组，且元素非负——std::vector 或原生 int arr[N] 都能用，关键不在容器类型，而在能否按位分桶。负数需偏移处理，浮点数不能直接用，得转成整型表示（如 IEEE 754 位模式需额外解码）。

怎么用数组实现 LSD 基数排序（最低位优先）

LSD 是最常用、最容易用数组落地的版本。核心是：对每一位（个位、十位……）做计数排序，稳定地重排整个数组。不依赖递归或额外容器类，纯数组 + 辅助数组即可。

实操要点：

准备一个长度为 N 的输出数组 output[]，每次按某一位排序后把结果暂存进去，再拷回原数组
用长度为 10 的 count[10] 统计当前位上数字 0–9 出现次数
做前缀和，让 count[i] 表示“≤ i”的元素个数，从而得到每个数字在 output[] 中的右边界位置
倒序遍历原数组（保证稳定性），取当前位数字 d = (arr[j] / exp) % 10，查 count[d] 得插入位置，填入 output[--count[d]]
exp 从 1 开始，每次乘 10，直到 exp > max_val

示例关键片段：

void radixSort(int arr[], int n) {
    int output[n];
    int max_val = *std::max_element(arr, arr + n);
    for (int exp = 1; max_val / exp > 0; exp *= 10) {
        countingSortByDigit(arr, output, n, exp);
        std::copy(output, output + n, arr);
    }
}

为什么不能直接对 `std::array` 或 `std::vector` 调用 `std::sort` 替代

std::sort 是快排/堆排混合，平均 O(n log n)，而基数排序是 O(d·n)，d 是最大数的位数。当 d 较小（比如固定 32 位整数，d=10 进制下最多 10 轮）、n 很大时，基数排序实际更快，且可预测——没有快排的最坏 O(n²) 风险。但 std::sort 通用、稳定（C++11 起）、支持自定义比较器；基数排序只适用于可拆解为“有限位+有限值域”的类型，写错一位就全乱。