0

我的一门 CS 课程遇到了一个问题，我必须编写一个可以对无符号整数（+ 或 -）进行排序的 LSD 基数排序。假设要排序的值是 32 位整数值。

规定是我的掩码必须是一个常数值，这就是我的问题所在。如果我对 32 位整数进行 & 按位运算，其中每个数字由 4 位（十六进制表示）表示，我的掩码应该是 28 吗？（因为我希望二进制中有 28 位 1）

另外，如果有人注意到任何其他错误，请您注意它们吗？

#define BITS_PER_PASS 4
#define NUM_PASSES 8
#define NUM_BUCKETS 16
#define MASK 28

int *buckets[NUM_BUCKETS];
int bucket_sizes[NUM_BUCKETS];

void radix_sort( int *values, int n )
{
    int i, j;
    int bucket_index;
    int *p;

    for( i=0; i < NUM_PASSES; i++ )
    {
        for( j=0; j < NUM_BUCKETS; j++ )
        {
            bucket_sizes[j]=0;
        }

        for( j=0; j < n; j++ )
        {
            bucket_index = (values[j] & MASK) >> BITS_PER_PASS*i; //QUESTION
            buckets[j][ bucket_sizes[bucket_index]]=values[j];
            bucket_sizes[bucket_index]++;
        }

        p = values;

        for( j=0; j < NUM_BUCKETS; j++ )
        {
            memcpy((void *)p, (void *)buckets[j], sizeof(int)*bucket_sizes[j]);
            p+=bucket_sizes[j];
        }
    }
}

我还想补充一点，所有定义的常量和全局变量都是强制性的，因为我被告知在我的基数排序中使用它们。

4

2 回答 2

0

我看到您正在使用一个名为 bucket_sizes[NUM_BUCKETS] 的数组和指针数组。这些可以在 sort 函数中声明。对于 32 位无符号整数，NUM_BUCKETS = 32/BITS_PER_PASS。

您还需要第二个缓冲区来保存已排序的值，例如，buffer = malloc(n * sizeof(unsigned int); 排序完成后不要忘记释放（缓冲区）。

指针数组应设置为 buckets[0] = buffer, buckets[1] = buffer + bucket_sizes[0], buckets[2] = buffer + bucket_sizes[0] + bucket_sizes[1], ... 。您可以使用局部变量来跟踪存储桶大小的总和。请注意，最后一个 bucket_sizes[15] 不用于设置指针数组。

每次传递交换缓冲区和值之后（将它们视为指针）。由于它是偶数次，（8），排序后的数据最终将返回值。

于 2015-10-25T00:28:06.793 回答
0

而不是这个：

int *buckets[NUM_BUCKETS];
int bucket_sizes[NUM_BUCKETS];
...
buckets[j][ bucket_sizes[bucket_index]]=values[j];

建议：

int buckets[NUM_BUCKETS];
int bucket_size[NUM_BUCKETS];
...
buckets[bucket_size[bucket_index]]=values[j];

关于这些行：

bucket_index = (values[j] & MASK) >> BITS_PER_PASS*i;

我希望能提取 4 位的东西，例如：

bucket_index = (values[j] >> BITS_PER_PASS*i) & MASK;

其中 MASK 为 0x0F，因为尝试选择 16 个不同的“桶”之一（其中 &0x0F 将产生 0...15 范围内的值）

于 2015-10-25T00:19:40.037 回答