基数排序：获取正确键值以实现有符号整数排序的问题

我来帮你搞定这个问题！你的基数排序在处理负数时出现顺序反转的问题，核心原因是SortKeyToU32函数的键值转换逻辑有误，导致负数的相对排序被颠倒了。

问题根源分析 #

你当前的转换逻辑是：

uint32_t SortKeyToU32(int Value) {
    uint32_t Result = (uint32_t)Value;
    if(Result & 0x80000000) {
        Result = ~Result; // 负数取反所有位
    } else {
        Result |= 0x80000000; // 正数设置最高位为1
    }
    return Result;
}

这个逻辑的问题在于对负数取反所有位：有符号整数的负数是以补码形式存储的，取反会完全翻转每一位，这直接颠倒了负数之间的相对顺序。比如：

• -30的补码是0xFFFFFFE2，取反后得到0x0000001D
• -10的补码是0xFFFFFFF6，取反后得到0x00000009

显然0x00000009 < 0x0000001D，所以基数排序会把-10排在-30前面，和我们期望的升序（-30 < -10 < -4）完全相反。

正确的键值转换逻辑 #

我们需要的是把有符号整数映射到无符号整数时，保持原数的升序关系：

• 所有负数的键值应该小于所有正数的键值
• 负数之间的相对顺序要和原数一致（更小的负数对应更小的键值）
• 正数之间的相对顺序也要和原数一致

实现这个目标最简单的方式是翻转补码的最高位（也就是符号位），这样：

• 负数的最高位从1变成0，进入无符号数的低半区
• 正数的最高位从0变成1，进入无符号数的高半区
• 其他位保持不变，确保相对顺序正确

修正后的SortKeyToU32函数如下：

uint32_t SortKeyToU32(int Value) {
    uint32_t Result = (uint32_t)Value;
    // 翻转最高位，保持其他位的相对顺序
    Result ^= 0x80000000;
    return Result;
}

或者你也可以用偏移量法（本质和异或等价，注意有符号溢出的问题，但在转换为uint32_t时结果是正确的）：

uint32_t SortKeyToU32(int Value) {
    // 给所有数加上2^31，把负数偏移到无符号数的低半区
    return (uint32_t)(Value + 0x80000000);
}

验证示例输入 #

用修正后的函数处理你的示例输入：
1, 6, 9, 2, 3, -4, -10, 8, -30, 4

对应的键值会是：

• -30 → 0x7FFFFFE2
• -10 → 0x7FFFFFF6
• -4 → 0x7FFFFFFC
• 1 → 0x80000001
• 2 → 0x80000002
• ...（正数的键值都在0x80000000以上，且顺序和原数一致）

基数排序后，键值从小到大排列，对应的原数顺序就是：
-30, -10, -4, 1, 2, 3, 4, 6, 8, 9，完全符合升序要求。

额外小提示 #

你的RadixSort函数里的memset(Dest, 0, Size*sizeof(int));其实是多余的，因为后续的排序过程会覆盖Dest的所有元素，可以删掉它来节省一点性能。

内容的提问来源于stack exchange，提问作者Zhukov Artem