C语言 这个基数排序代码中的最后一个"for"循环有什么作用?

Question

我正在阅读Zed A. Shaw的《Learn C The Hard Way》一书，我正在研究他对基数排序算法的实现。

这是他的代码：

#define ByteOf(x, y) (((u_int8_t *)x)[y])
static inline void radix_sort(short offset, uint64_t max,
uint64_t * source, uint64_t * dest)
{
uint64_t count[256] = { 0 };
uint64_t *cp = NULL;
uint64_t *sp = NULL;
uint64_t *end = NULL;
uint64_t s = 0;
uint64_t c = 0;
// Count occurences of every byte value
for (sp = source, end = source + max; sp < end; sp++) {
count[ByteOf(sp, offset)]++;
}
// transform count into index by summing
// elements and storing them into same array.
for (s = 0, cp = count, end = count + 256; cp < end; cp++) {
c = *cp;
*cp = s;
s += c;
}
// fill dest with right values in the right place
for (sp = source, end = source + max; sp < end; sp++) {
cp = count + ByteOf(sp, offset);
printf("dest[%d] = %dn", *cp, *sp);
dest[*cp] = *sp;
++(*cp);
}
}

以上只是一个辅助函数。他的实际基数排序在这里完成：

void RadixMap_sort(RadixMap * map)
{
uint64_t *source = &map->contents[0].raw;
uint64_t *temp = &map->temp[0].raw;
radix_sort(0, map->end, source, temp);
radix_sort(1, map->end, temp, source);
radix_sort(2, map->end, source, temp);
radix_sort(3, map->end, temp, source);
}

以下是他定义的结构：

typedef union RMElement {
uint64_t raw;
struct {
uint32_t key;
uint32_t value;
} data;
} RMElement;
typedef struct RadixMap {
size_t max;
size_t end;
uint32_t counter;
RMElement *contents;
RMElement *temp;
} RadixMap;

我可以理解内联函数radix_sort中的前 2 个 for 循环。据我了解，第一个只是简单地计算字节值，第二个函数基本上制作一个累积频率表，其中每个条目都是先前条目的总和。

我仍然无法绕开ByteOf(x, y)宏和第三个 for 循环。我尝试阅读维基数排序的维基百科页面，并阅读了另一篇使用C++实现的文章。但是，这些文章中编写的代码与他编写的代码不匹配。

我了解基数排序原则上的工作原理。基本上，我们根据每个数字对其进行分组，为我们遇到的每个新数字重新排列分组。例如，要对数组[223, 912, 275, 100, 633, 120, 380]进行排序，首先按 1 位对它们进行分组，这样得到[380, 100, 120]、[912]、[633, 223]、[275]。然后你对十和几百个地方做同样的事情，直到你用完数字。

任何帮助解释他的代码将不胜感激。 谢谢。

Answer 1

ByteOf(x， y) 与：

#define ByteOf(x, y)  ((*(x) >> (offset*8)) & 0xff)

也就是说，它将字节 #{offset} 的值隔离在一个值中。

第二个循环是一种分配器。 如果前六个计数[]在第一个循环后为1,2,4,0,16,25，则在第二个循环后将是0,1,3,7,7,23。 这会指示第三个循环(通过 source[])将目标布局为：

ByteOf       index       number of values
0            0           1
1            1           2
2            3           4
3            7           0 -- there are none.
4            7           16
5            23          25

我发现将第三个循环重写为：

for (i = 0; i < max; i++) {
dest[count[ByteOf((source+i), offset)]++] = source[i];
}

我认为它更清楚地显示了关系，即 ith' source 元素正在复制到 dest 中的索引。 dest 中的索引位于先前为此数字计算的分区 (count[]) 的开头。 由于此位置现在有一个数字，因此我们增加此分区的开头以防止覆盖它。

请注意，括号 (source+i) 对于获取 ByteOf 中强制转换的正确地址是必需的。