基数排序适合非负整数或可映射为非负整数的数组，通过按位分桶（个位、十位等）进行稳定排序，不依赖元素间比较，要求数据可拆分为固定进制位且需额外空间。
基数排序适合什么类型的数组
基数排序只适用于整数数组，且必须是非负整数（或能映射为非负整数的类型）。它不比较元素大小，而是按位（个位、十位……）分桶，所以对 int 类型需额外处理符号位——最简单的方式是统一偏移：把 int 转成 unsigned int，利用补码特性让负数排在前面（即按内存布局直接排序），但要注意这和标准升序不等价。若严格要求数学意义上的升序，应先分离正负、分别排序再合并。
用 std::vector<int> 实现 LSD 基数排序
LSD（Least Significant Digit）从低位开始排序，稳定、易实现，适合固定位宽数据。关键点是每轮按某一位分到 10 个桶（0–9），再顺序收集。注意桶要用 std::vector 动态扩容，避免预分配过大空间；收集时用 std::move 减少拷贝开销。
常见错误：忘记清空桶、误用桶索引（如用 (num / base) % 10 计算当前位时 base 初始值设为 0）、未处理全零情况导致死循环。
- 起始
base = 1，循环条件为base <= max_val（max_val是绝对值最大元素） - 每轮遍历原数组，用
(static_cast<unsigned int>(num) / base) % 10得桶号（强制转unsigned int防止负数右移未定义行为） - 收集时按桶 0→9 顺序将元素写回原数组，用
std::move移动而非复制
void radix_sort(std::vector<int>& arr) {
if (arr.empty()) return;
int max_val = *std::max_element(arr.begin(), arr.end(),
[](int a, int b) { return std::abs(a) < std::abs(b); });
unsigned int base = 1;
while (base <= static_cast<unsigned int>(max_val)) {
std::vector<std::vector<int>> buckets(10);
for (int num : arr) {
int digit = (static_cast<unsigned int>(num) / base) % 10;
buckets[digit].push_back(std::move(num));
}
arr.clear();
for (auto& bucket : buckets)
for (int& x : bucket) arr.push_back(std::move(x));
base *= 10;
}
}
性能瓶颈在哪？为什么有时比 std::sort 慢
基数排序时间复杂度是 O(d × (n + k))（d 是最大位数，k 是基数，这里是 10），看似线性，但实际常数很大：多轮内存分配、缓存不友好（随机访问桶）、分支预测失败（桶索引跳变）。当 n 小于几千，或 d 很大（比如 int64_t 且数值分散），std::sort 的内省排序通常更快。
立即学习“C++免费学习笔记（深入）”；
优化方向有限：改用 256 桶（按字节）可减少轮数，但桶数量暴涨，空间局部性更差；使用静态桶数组（int buckets[10][N]）避免动态分配，但需预知最大长度。
- 小数组（
n < 100）直接用std::sort - 大批量同范围整数（如像素值 0–255）才显优势
- 不要对
std::vector<std::string>或浮点数直接套用——得先转整数表示
负数怎么安全处理
直接按 unsigned int 解释负数会打乱顺序（-1 变成 4294967295）。正确做法是做偏移：找到最小值 min_val，所有数加 -min_val 变成非负，排序后再减回去。但要注意溢出——int 最小值是 -2147483648，加正数可能溢出，所以必须用 long long 中间存储。
- 先扫描得
min_val和max_val - 用
std::vector<long long>存偏移后值，排序完再转回int - 或者用 MSB（最高位）单独处理：把负数视为“高位为 1”，正数为 0，先按符号分两组，再各自基数排序
真正麻烦的不是算法逻辑，而是边界检查和类型转换——漏掉一次 static_cast<unsigned int> 或用错 abs 就可能触发未定义行为。
