LSD 基数排序并非只能处理非负整数。真正的障碍不是负号，而是按无符号字节排序后，补码负数会落在正数之后。本文从排序键的单调映射出发，用翻转最高符号位的方法统一有符号整数顺序，给出稳定的 C++ 四趟字节排序、边界测试与复杂度分析。
“基数排序遇到负数就先分成两组”是一种常见做法，却不是唯一解。分组后还要处理负数绝对值的逆序，INT_MIN 取绝对值会溢出，代码分支很快变多。更反直觉但更整洁的思路是：不要改变数值，只改变用于比较的排序键。
32 位有符号整数使用补码。按位把它看成无符号数时，非负数位于 0x00000000 到 0x7fffffff，负数位于 0x80000000 到 0xffffffff。无符号顺序恰好把所有负数放在正数后面。若把每个数的最高位翻转，也就是与 0x80000000 异或，区间会旋转半圈：最小负数映射到 0，-1 映射到 0x7fffffff，0 映射到 0x80000000，最大正数映射到 0xffffffff。这个映射严格保持有符号整数的大小顺序。
辟谣一：稳定性只是为了对象排序
LSD 表示从最低有效位开始。第一趟按最低字节分桶，第二趟按次低字节分桶。第二趟若打乱同一字节内第一趟的顺序，最低字节信息就丢了。因此每一趟都必须稳定，哪怕排序对象只是整数。
计数排序很适合做单趟稳定分配。先统计 256 个字节值的出现次数，再算每个桶的起始偏移，最后按原数组从左到右写入临时数组。写入时递增偏移，同桶元素自然保持上一趟的先后关系。
辟谣二：最高字节单独倒序即可
有人把前三个字节按升序，最后一趟将最高字节倒序，试图让负数提前。这会把负数区间内部也整体倒转，得到错误结果。正确需求不是让 0xff 比 0x80 小，而是让最高字节的顺序变成 0x80..0xff, 0x00..0x7f。翻转符号位把这个环形顺序转换为普通的 0x00..0xff，四趟代码因此完全一致。
完整 C++ 程序
实现使用 uint32_t 提取字节，避免对负有符号数右移时依赖实现细节。static_cast<uint32_t>(value) 保留补码位模式，排序键再翻转最高位。
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <random>
#include <vector>
static uint32_t sortableKey(int32_t value) {
return static_cast<uint32_t>(value) ^ 0x80000000u;
}
void radixSortSigned(std::vector<int32_t>& values) {
if (values.size() < 2) return;
std::vector<int32_t> buffer(values.size());
for (int pass = 0; pass < 4; ++pass) {
std::array<std::size_t, 256> count{
};
const int shift = pass * 8;
for (int32_t value : values) {
uint32_t byte = (sortableKey(value) >> shift) & 0xffu;
++count[byte];
}
std::array<std::size_t, 256> offset{
};
for (std::size_t i = 1; i < offset.size(); ++i) {
offset[i] = offset[i - 1] + count[i - 1];
}
for (int32_t value : values) {
uint32_t byte = (sortableKey(value) >> shift) & 0xffu;
buffer[offset[byte]++] = value;
}
values.swap(buffer);
}
}
int main() {
std::vector<int32_t> data = {
7, -3, 0, std::numeric_limits<int32_t>::min(),
7, -1, 256, -257, std::numeric_limits<int32_t>::max()
};
auto expected = data;
std::sort(expected.begin(), expected.end());
radixSortSigned(data);
for (int32_t x : data) std::cout << x << ' ';
std::cout << '\n';
assert(data == expected);
std::mt19937 rng(20260805);
std::uniform_int_distribution<int32_t> distribution(
std::numeric_limits<int32_t>::min(),
std::numeric_limits<int32_t>::max()
);
std::vector<int32_t> randomData(10000);
for (auto& x : randomData) x = distribution(rng);
auto randomExpected = randomData;
std::sort(randomExpected.begin(), randomExpected.end());
radixSortSigned(randomData);
assert(randomData == randomExpected);
std::vector<int32_t> empty;
radixSortSigned(empty);
std::cout << "signed radix tests passed\n";
}
编译运行：
g++ -std=c++17 -O2 SignedRadixSort.cpp -o SignedRadixSort && ./SignedRadixSort
预期输出的第一行是：
-2147483648 -257 -3 -1 0 7 7 256 2147483647
signed radix tests passed
四趟为什么足够
32 位整数有四个字节，每趟处理 8 位。完成第 p 趟后，数组按低 8*(p+1) 位的键稳定有序。归纳基础是第一趟的稳定计数排序；归纳步骤依靠当前字节分桶且保留同桶内旧顺序。四趟后所有 32 位都参与，排序键全序成立，再由符号位翻转映射回有符号顺序。
这里没有比较两个完整整数，所以基于比较的 Omega(n log n) 下界不适用。算法利用了键宽固定且可按字节直接寻址的额外条件。把它宣传成“任何排序都能线性完成”才是概念混淆。
复杂度不是只写 O(n)
每趟扫描输入、256 个桶和输出，四趟总时间为 O(4*(n+256))，固定 32 位下可写成 O(n)。临时数组占 O(n)，计数与偏移表是常数空间。若键宽为 w 位、每趟处理 r 位，一般式是 O((w/r)*(n+2^r))。
桶数不是越大越好。一次处理 16 位只需两趟，却要维护 65536 个计数，清零成本和缓存压力上升。8 位桶表通常能放进高速缓存，工程表现常比理论趟数更少的大桶稳定。最终选择要用真实数据规模压测，而非只数循环层数。
边界条件
空数组和单元素数组直接返回。重复值必须保留数量；本文与 std::sort 的整体结果比较会覆盖这一点。INT_MIN 是专门测试对象，因为“分离负数再取绝对值”的方案最容易在这里触发未定义行为。最大正数、-1、0 共同验证符号边界。
如果数据类型改为 64 位，需要八趟并将掩码改为 0x8000000000000000ULL。若平台并非 8 位字节或整数表示不满足预期，应使用固定宽度类型并检查编译环境。C++ 标准对固定宽度整数是否存在有条件约束，主流平台通常提供 int32_t，通用库仍应做静态断言。
常见错误清单
第一，直接对负数右移取字节，算术右移会补符号位，跨语言行为还可能不同。第二，计数转偏移时写成包含当前桶的前缀和，导致第一个写入位置越过桶首。第三，从右向左分配却仍递增起始位置，稳定性规则前后不匹配。第四，四趟后忘记数据可能停在临时缓冲区；示例每趟交换，偶数趟后恰好回到原向量，但实现逻辑不能依赖模糊记忆。
第五，把浮点数位模式照搬进来。IEEE 754 的符号位、负数区间与 NaN 顺序需要不同映射，本文结论只针对二进制补码有符号整数。第六，使用 char 保存桶号并让其成为负值，索引直接越界；应使用无符号整数。
如何验证不是“刚好过样例”
手工样例覆盖符号边界和重复值，固定随机种子生成一万项，再与标准库排序对拍。固定种子使失败可复现；标准库提供独立的比较排序参照。还可以补充全相同、已经升序、完全降序、只含负数以及高字节相同的数据，分别检查稳定分配和各趟有效性。
若要验证稳定性本身，可把元素扩展为“键加原始序号”，排序只读取键，最后确认相同键的序号递增。本文排序的是纯整数，重复值不可区分，所以结果相等只能间接覆盖稳定性；算法内部仍按从左到右写桶保证了该性质。
内存流量往往比比较次数更重要
四趟基数排序会完整读取和写入数组四次，另加计数表扫描。对于已经基本有序的小数组，标准库的高度优化比较排序可能更快，因为它不一定需要同等规模的额外缓冲区。基数排序的优势通常出现在大量固定宽度整数、比较成本低但数量很大、内存带宽仍可承受的场景。
临时数组每趟与原数组交换，不会复制向量对象中的全部元素，只交换底层缓冲区所有权；真正的数据写入发生在稳定分配阶段。若元素是带负载的大对象，不应直接搬动完整对象，可以排序索引或键值对中的紧凑记录，再按索引重排。算法的线性时间不代表内存写放大可以忽略。
并行化时，每个线程可以统计私有桶，再计算线程与桶的全局偏移，最后无冲突写入输出。若多个线程直接对同一计数数组做原子递增，竞争会吞掉收益。NUMA 机器上还要关注输入与输出缓冲区所在节点。基数排序看似只是四个循环，性能版本实质上是一项数据布局工程。
降序与复合键
降序不应简单在最后调用 reverse，如果元素还带有相同键下的稳定顺序，整体反转会把相等键的次序也颠倒。可以对排序键逐位取反后做升序稳定排序，或在每趟构造反向桶偏移并保持桶内稳定。
对多个 32 位字段做字典序排序，可以从最低优先级字段开始依次执行稳定基数排序，最后处理最高优先级字段。也可以拼成更宽的无符号键，但要明确字段位宽、符号映射和端序。稳定性在这里不再是实现细节，而是复合排序正确性的基础。
总结
负数没有让基数排序失效，失效的是把补码位模式直接当无符号顺序。翻转最高符号位构造了一个单调排序键，让四次稳定字节排序无需特殊分支便覆盖整个 int32_t。这比先拆正负两组更容易解释，也避开了最小负数绝对值溢出的陷阱。
