十六进制基数排序处理负数排序异常问题求助

问题描述 #

我实现了一段基于十六进制基数的基数排序C语言代码，每次处理4位二进制位，用16个桶排序。但运行后正数全排在前面，负数在末尾，不符合数值升序的预期（比如应该是-100、-10、0、10、100）。修改逻辑后还引发了严重错误，求解决办法。

现有代码 #

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

void radix_sort(int arr[], int n) {
    int buckets[16][MAX_SIZE];
    int bucket_count[16];
    int i, j, k, r, shift, pass, NOP = 8;
    int buffer[MAX_SIZE];

    for (pass = 0; pass < NOP; pass++) {
        for (i = 0; i < 16; i++)
            bucket_count[i] = 0;

        shift = pass * 4;
        for (i = 0; i < n; i++) {
            r = ((unsigned int)arr[i] >> shift) & 15;
            buckets[r][bucket_count[r]] = arr[i];
            bucket_count[r]++;
        }

        i = 0;
        for (k = 0; k < 16; k++) {
            for (j = 0; j < bucket_count[k]; j++) {
                buffer[i] = buckets[k][j];
                i++;
            }
        }

        for (i = 0; i < n; i++)
            arr[i] = buffer[i];
    }
}

int main() {
    int arr[MAX_SIZE];
    int n, i;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    radix_sort(arr, n);

    for (i = 0; i < n; i++)
        printf("%d\n", arr[i]);

    return 0;
}

运行结果 #

输入：

14394
-5905
-12765
1193
-7496

执行结果：

1193
14394
-12765
-7496
-5905

正确结果对比差异：

1,2d0
< 1193
< 14394
5a4,5
> 1193
> 14394

问题原因与解决方法 #

原因 #

C语言中int是有符号数，采用补码存储。将int强制转为unsigned int处理时，负数的符号位会被当作高位数值，导致所有负数的无符号值都大于正数，最终排序结果正数在前、负数在后，不符合数值升序要求。

修复方案 #

针对32位有符号整数的特性，可在最后一趟处理最高4位时，调整桶的遍历顺序：先遍历对应负数的8_{15号桶，再遍历对应正数的0}7号桶，这样负数会被排在前面，正数在后，实现整体升序。

修改后的代码

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

void radix_sort(int arr[], int n) {
    int buckets[16][MAX_SIZE];
    int bucket_count[16];
    int i, j, k, r, shift, pass, NOP = 8;
    int buffer[MAX_SIZE];

    for (pass = 0; pass < NOP; pass++) {
        for (i = 0; i < 16; i++)
            bucket_count[i] = 0;

        shift = pass * 4;
        for (i = 0; i < n; i++) {
            r = ((unsigned int)arr[i] >> shift) & 15;
            buckets[r][bucket_count[r]] = arr[i];
            bucket_count[r]++;
        }

        i = 0;
        // 最后一趟处理最高4位时，先输出负数对应的桶，再输出正数的桶
        if (pass == NOP - 1) {
            // 遍历负数对应的桶（8-15）
            for (k = 8; k < 16; k++) {
                for (j = 0; j < bucket_count[k]; j++) {
                    buffer[i] = buckets[k][j];
                    i++;
                }
            }
            // 遍历正数对应的桶（0-7）
            for (k = 0; k < 8; k++) {
                for (j = 0; j < bucket_count[k]; j++) {
                    buffer[i] = buckets[k][j];
                    i++;
                }
            }
        } else {
            // 前7趟按正常顺序遍历桶，保证低位排序正确
            for (k = 0; k < 16; k++) {
                for (j = 0; j < bucket_count[k]; j++) {
                    buffer[i] = buckets[k][j];
                    i++;
                }
            }
        }

        for (i = 0; i < n; i++)
            arr[i] = buffer[i];
    }
}

int main() {
    int arr[MAX_SIZE];
    int n, i;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    radix_sort(arr, n);

    for (i = 0; i < n; i++)
        printf("%d\n", arr[i]);

    return 0;
}

说明

• 32位有符号整数的最高4位决定数值正负：符号位为1时是负数，对应无符号右移后的最高4位范围是8_{15；符号位为0时是正数，对应范围是0}7。
• 最后一趟调整桶的遍历顺序，让负数先被写入结果数组，正数在后，直接修正排序顺序。
• 前7趟保持原有遍历逻辑，确保低位排序的正确性。

内容的提问来源于stack exchange，提问作者David Czerepak