基数排序c++实现应避免vector分桶以减少内存重分配和缓存不友好问题；推荐用单块temp数组+count前缀和+字节级位运算（含负数补码异或处理）实现高效稳定排序。
基数排序的C++实现为什么不能直接用vector>按位分桶
因为每次分配10个vector（对应0–9）再合并，会频繁触发内存重分配和元素拷贝，尤其在大数据量时缓存不友好。更关键的是，标准vector的内部指针和容量元数据本身就有额外开销，对百万级整数来说，光桶容器的管理开销就可能多占几MB。
实操建议：
- 用单块连续数组模拟桶：预分配一个与输入等长的
temp数组，再用长度为10的count数组统计每轮各数字出现频次，通过前缀和算出每个桶在temp中的起始偏移 - 避免动态容器：所有桶操作都在
temp上做索引写入，原数组只读，temp只写，最后用std::swap交换指针（或用std::move转移） - 对
int类型，按字节（unsigned char）逐轮处理比按十进制位更高效，且规避了负数除10取余的符号问题
如何用计数排序作为子过程完成稳定的一轮分配
基数排序本质是多趟稳定排序，而计数排序天然稳定且O(n+k)时间。关键不在“排序”，而在“按某一位分组并保持组内原有顺序”——这正是计数排序的output数组填充逻辑所保证的。
实操建议：
- 每轮先遍历原数组，用
(arr[i] >> shift) & 0xFF提取当前字节（shift为0/8/16/24），累加到count[digit] - 对
count做前缀和：count[i] += count[i-1]（从1开始），此时count[digit]表示值≤digit的元素总数，也即digit桶的右边界 - 倒序遍历原数组（保证稳定性）：取出
digit，将arr[i]写入temp[--count[digit]]
负数怎么处理才不破坏排序稳定性且省空间
直接按补码二进制排序会导致负数排在正数前面（因为最高位是1），但又不能简单加偏移（如+2147483648），否则要额外分配更大范围的count数组，浪费空间。
实操建议：
- 不改数值，改解释方式：把
int强制转为unsigned int，再异或0x80000000，让符号位翻转——这样最小的负数变成0，最大的正数变成UINT_MAX，自然有序 - 这个转换是纯位运算，无分支、无内存分配，在循环外统一预处理输入数组一次即可
- 排序完成后，再用同样异或操作还原回
int，整个过程不增加额外存储，也不影响稳定性
内存优化后实际能省多少、哪些地方还容易踩坑
对一千万个int，传统vector<vector>></vector>方案峰值内存常超200MB；优化后仅需2个vector<int></int>（原数组+临时数组）+ 1个vector<int>(10)</int>，约80MB左右，减少60%以上。
但要注意：
-
count数组必须初始化为0，否则前缀和会出错——别依赖全局变量默认零初始化，显式写std::array<int> count{};</int> - 按字节排序共4轮，
shift应为0, 8, 16, 24，不是0, 1, 2, 3，否则位移不足 - 如果输入含
INT_MIN，强制转unsigned int再异或没问题，但别用abs()或条件判断，那会引入分支预测失败
最易被忽略的是：最后一轮（最高字节）结束后，结果未必在原始数组里——得检查temp是否为当前输出目标，必要时再swap一次，否则返回的是未排序副本。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
