手写基数排序必须先确定进制和位数，否则计数排序子过程会越界或漏桶；需处理负数补码干扰，推荐分离正负零或翻转符号位；子排序须用反向遍历+后缀和保证稳定；应双缓冲复用内存避免频繁分配；扩展到浮点等类型时需按IEEE 754位布局转换。
为什么手写基数排序要先确定位数和进制
手写 radix sort 最容易卡在“不知道从哪一位开始排”——它不像快排或归并那样只关心大小关系，而是依赖数字的**位表示**。你得明确：用十进制还是二进制？最大数有多少位？否则 counting sort 子过程会越界或漏桶。
常见错误是直接对 int 按 32 位无脑循环，结果负数补码导致高位全是 1，排序错乱；或者没处理 0 值导致计数数组下标为负。实际应先取绝对值范围，再按非负整数处理，或统一转成无符号类型。
- 若输入全为非负整数，用十进制更直观，
base = 10，位数由max_value决定（如max_value = 999→ 3 轮） - 若含负数，推荐先分离正/负/零，对绝对值排序后反转负数部分，避免补码干扰
- 二进制（
base = 256或base = 65536）性能更好，但需按字节或双字节提取，num & 0xFF、(num >> 8) & 0xFF这类操作要写对
如何正确实现稳定子排序（计数排序）
radix sort 的稳定性完全依赖子排序的稳定性，而手写时最容易把 counting sort 写成不稳定版本——比如正向遍历原数组填入输出数组，会导致相同键值的元素顺序颠倒。
必须使用**反向遍历 + 后缀和校准位置**。关键不是“统计频次”，而是“算出每个键值在输出数组中的**最后一个位置**”。
立即学习“C++免费学习笔记（深入）”；
- 先统计各桶频次：
count[digit]++ - 再做前缀和（注意是“小于等于该 digit 的总数”）：
for (int i = 1; i - 然后从原数组末尾开始遍历，对每个
digit，取count[digit]-1为输出下标，再执行count[digit]--
漏掉 -- 或用错遍历方向，排序立刻失效。示例片段：
for (int i = n - 1; i >= 0; --i) {
int d = (arr[i] / exp) % base; // exp 是当前位权，如 1, 10, 100...
output[--count[d]] = arr[i];
}
如何避免内存重复分配和拷贝开销
每轮 radix sort 都要一个临时数组存中间结果，频繁 new/delete 或 vector::resize 会拖慢性能，尤其大数据量时。手写时应复用空间，而不是每轮都新建。
- 分配两个数组
A和B，奇数轮从A排到B，偶数轮从B排到A，最后根据轮数决定返回哪个 - 避免用
std::vector存储中间结果——它的operator[]检查可能被编译器优化掉，但动态扩容逻辑仍存在；裸指针 +std::copy更可控 - 如果输入是
std::vector<int>，别在函数内直接修改它；先std::vector<int> temp = input，再双缓冲操作，防止意外覆盖
处理不同数据类型时的关键转换点
手写 radix sort 支持 unsigned int 很简单，但扩展到 int、long long 甚至 float 就得小心位布局。C++ 标准不保证 float 的 IEEE 754 表示，但主流平台可用 memcpy 强转为整数再排序（注意大小端）。
-
int→unsigned int：用static_cast<unsigned int>(x ^ 0x80000000)翻转符号位，使负数变大正数，保持序关系 -
float→uint32_t：先memcpy(&u, &f, sizeof(f))，再对u做符号位翻转（同上），因为 IEEE 754 的正数和负数位模式本身不满足数值序 - 64 位类型（如
long long）建议用base = 65536（16 位一组），而非base = 10，减少循环次数，也避免 64 位除法慢
没做符号位翻转就直接排 int，结果会是：-1、-2、-3…排在最大正数后面，完全乱序。
