修复C语言基数排序处理含负数浮点数的排序异常问题

你的代码问题出在浮点数的IEEE 754二进制特性与基数排序的逻辑不匹配：

• 单精度浮点数的最高位是符号位：正数符号位为0，负数为1。直接将float转成uint32_t后，所有负数的无符号数值都会大于正数，且负数内部的uint32_t大小顺序和实际float值的顺序完全相反（比如-5.8的uint32_t值比-1.4大，但实际-5.8更小）。
• 原基数排序从最低位到最高位处理，最高位（符号位）处理时把0（正数）放在前面、1（负数）放在后面，导致正数在前、负数在后，且负数顺序完全颠倒。

通过映射转换，让float的实际大小顺序对应uint32_t的无符号顺序，排序后再逆向映射恢复原浮点数：

1. 正向映射（float → uint32_t）：
   • 正数：将符号位设为1（val | 0x80000000），确保正数的映射值全部大于负数的映射值。
   • 负数：对整个uint32_t值取反（~val），让负数的实际大小顺序与映射后的uint32_t顺序一致。
2. 保持原LSD基数排序逻辑不变。
3. 逆向映射（uint32_t → float）：
   • 若映射值最高位为0（原数是负数），取反恢复原uint32_t值。
   • 若映射值最高位为1（原数是正数），清除符号位（val & 0x7FFFFFFF）恢复原uint32_t值。

#include <stdio.h>
#include <stdint.h>
#define MAX 100

void radix_sort(uint32_t A[], unsigned int n) {
        uint32_t bucket0[MAX], bucket1[MAX];
        unsigned int mask, count0, count1;
        for(int d = 0; d <= 31; d++) {
                mask = 1U << d;
                count0 = count1 = 0;
                for(int i = 0; i < n; i++) {
                        if((A[i] & mask) == 0) {
                                bucket0[count0++] = A[i];
                        } else {
                                bucket1[count1++] = A[i];
                        }
                }
                for (int i = 0; i < count0; i++) {
                        A[i] = bucket0[i];
                }
                for (int i = 0; i < count1; i++) {
                        A[count0 + i] = bucket1[i];
                }
        }
}

int main() {
        unsigned int n;

        printf("Enter a number of integers not greater than 100: ");
        scanf("%d", &n);

        if (n <= 0 || n > MAX) {
                printf("Invalid input.\n");
                return 1;
        }

        float float_numbers[MAX];
        printf("Enter %d real numbers:\n", n);
        for (int i = 0; i < n; ++i) {
                scanf("%f", &float_numbers[i]);
        }

        printf("Before sorting:\n");
        for(int i = 0; i < n; i++) {
                printf("%.3f\n", float_numbers[i]);
        }

        uint32_t A[MAX];
        for (int i = 0; i < n; i++) {
                uint32_t val = *(uint32_t*)&float_numbers[i];
                if (val & 0x80000000) {
                        // 负数取反，让大小顺序与uint32_t顺序一致
                        A[i] = ~val;
                } else {
                        // 正数设置符号位为1，确保正数映射值大于负数
                        A[i] = val | 0x80000000;
                }
        }

        radix_sort(A, n);

        printf("After sorting:\n");

        for (int i = 0; i < n; i++) {
                uint32_t val = A[i];
                if (!(val & 0x80000000)) {
                        // 还原负数
                        val = ~val;
                } else {
                        // 还原正数：清除符号位
                        val &= 0x7FFFFFFF;
                }
                printf("%.3f\n", *(float*)&val);
        }
        return 0;
}

• 该方案基于IEEE 754单精度浮点数标准，现代主流系统均支持该标准。
• 测试你的示例输入，输出将完全符合预期的排序结果。

内容的提问来源于stack exchange，提问作者Sebastian Llaurador