C++如何手写基数排序算法-C++-PHP中文网

手写基数排序必须先确定进制和位数，否则计数排序子过程会越界或漏桶；需处理负数补码干扰，推荐分离正负零或翻转符号位；子排序须用反向遍历+后缀和保证稳定；应双缓冲复用内存避免频繁分配；扩展到浮点等类型时需按ieee 754位布局转换。

c++如何手写基数排序算法

手写 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++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

漏掉 -- 或用错遍历方向，排序立刻失效。示例片段：

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></int>，别在函数内直接修改它；先 std::vector<int> temp = input</int>，再双缓冲操作，防止意外覆盖

手写 radix sort 支持 unsigned int 很简单，但扩展到 int、long long 甚至 float 就得小心位布局。C++ 标准不保证 float 的 IEEE 754 表示，但主流平台可用 memcpy 强转为整数再排序（注意大小端）。

int → unsigned int：用 static_cast<unsigned int>(x ^ 0x80000000)</unsigned> 翻转符号位，使负数变大正数，保持序关系
float → uint32_t：先 memcpy(&u, &f, sizeof(f))，再对 u 做符号位翻转（同上），因为 IEEE 754 的正数和负数位模式本身不满足数值序
64 位类型（如 long long）建议用 base = 65536（16 位一组），而非 base = 10，减少循环次数，也避免 64 位除法慢