对 4 字节整数列表进行排序的十六进制基数

Question

#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;
}

目标是十六进制基数排序。这意味着程序应一次处理 4 位并使用 16 个桶进行排序。好的，明白了。我的缓冲区数组和数字数组永远不会超过 100。我对其进行排序，但顺序不正确。这是我总是得到的输出：

• *14394
• *-5905
• *-12765
• *1193
• *-7496
• *================执行结果================
• *1193
• *14394
• *-12765
• *-7496
• *-5905
• *======与正确结果的差异======
• *1,2d0
• *< 1193
• *< 14394
• *5a4,5
• *>1193
• *>14394

负数放在列表底部。较大的负数应位于顶部，正数应位于下方，即：

• -100
• -10
• 0
• 10
• 100

我不太确定如何实现这个结果。 我在 SO 上看到了一个用于处理基数中的负数的解决方案，该解决方案表示将符号视为特殊类型的数字，但海报没有指定。我觉得我走在正确的轨道上，我只需要它正确排序，但我改变逻辑的尝试导致了巨大的错误和所有零结果。

Answer 1

基本问题是您没有按输入数字本身的值对输入数字进行排序。您将按照转换为

unsigned int

所得的值对它们进行排序。该转换甚至明确地出现在您的代码中。 结果是有符号值最终从零到最大正数排序，然后是最大负数到最小负数。

如果您想按有符号类型的数字本身的数值对它们进行排序，那么基数排序不太适合。至少，您需要为标志做一些特殊的调整。

我在SO上看到了一个用于处理基数中的负数的解决方案，该解决方案表示将符号视为一种特殊的数字，但海报没有指定。

考虑符号位的一种方法是，它具有比所有其他位的（正）位置值更大的负位置值。例如，在 8 位二进制补码中，位的位置值可以解释为

\位数	7	6	5	4	3	2	1	0
位值	-128	64	32	16	8	4	2	1

这使得包含符号位的任何一组连续位在性质上不同于所有不包含符号位的连续位。

考虑这些位模式：

号码\	7	6	5	4	3	2	1	0
-128	1	0	0	0	0	0	0	0
-125	1	0	0	0	0	0	1	1
-64	1	1	0	0	0	0	0	0
-1	1	1	1	1	1	1	1	1
1	0	0	0	0	0	0	0	1
7	0	0	0	0	0	1	1	1

观察到以 2 为基数（逐位）的基数排序是很简单的——除了由于该位的负数位置值而需要反转符号位的比较意义之外，这很正常。您可以通过实施以下更改来在您的排序中使用它：

• 在主排序循环中，仅按 31 个普通值位进行排序。这是一个很简单的改变：

          unsigned int magnitude_mask = ~0u >> 1;
          unsigned int sign_mask = ~magnitude_mask;
          // ...
  
              r = ((magnitude_mask & (unsigned int) arr[i]) >> shift) & 0xf;
  

• 在主排序循环之后，执行一次额外的遍历，其中按符号位进行反向排序。有多种方法可以考虑和实现它，但一种是使用与主循环相同的代码，除了像这样计算

  r

  ：

              r = ~(sign_mask & (unsigned int) arr[i]);
  

  在这种情况下，按位取反会影响“相反”部分。