基数排序工作

Question

我想知道下面的基数排序程序的逻辑。

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

typedef unsigned uint; 
#define swap(a, b) { tmp = a; a = b; b = tmp; } 
#define each(i, x) for (i = 0; i < x; i++) 

/* sort unsigned ints */ 
static void rad_sort_u(uint *from, uint *to, uint bit) 
{ 
    if (!bit || to < from + 1) return; 

uint *ll = from, *rr = to - 1, tmp; 
while (1) { 
    /* find left most with bit, and right most without bit, swap */ 
    while (ll < rr && !(*ll & bit)) ll++; 
    while (ll < rr && (*rr & bit)) rr--; 
    if (ll >= rr) break; 
    swap(*ll, *rr); 
} 

if (!(bit & *ll) && ll < to) ll++; 
bit >>= 1; 

rad_sort_u(from, ll, bit); 
rad_sort_u(ll, to, bit); 
} 

/* sort signed ints: flip highest bit, sort as unsigned, flip back */ 
static void radix_sort(int *a, const size_t len) 
{ 
size_t i; 
uint *x = (uint*) a; 

each(i, len) x[i] ^= INT_MIN; 
rad_sort_u(x, x + len, INT_MIN); 
each(i, len) x[i] ^= INT_MIN; 
} 

static inline void radix_sort_unsigned(uint *a, const size_t len) 
{ 
rad_sort_u(a, a + len, (uint)INT_MIN); 
} 

int main(void) 
{ 
int len = 16, x[16], i; 
size_t len = 16, i; 
each(i, len) x[i] = rand() % 512 - 256; 

radix_sort(x, len); 

each(i, len) printf("%d%c", x[i], i + 1 < len ? ' ' : '\n'); 

return 0; 
} 

我坚持，因为我不太明白的，而（1）循环..

到目前为止，我已经知道的是：

INT_MIN=-2147483648 

这是相同的价值在rad_short_u()

我已经调试的程序，由于rand() % 512-256bit，一些-ve值也产生，

第一次通过时，它将所有的-ve值交换到一侧（从开始）和+ ve之后 从下一个通道它左移到1位，所以位值从1073741824变为1073741824，直到它变为1数组保持不变。

请帮我理解程序逻辑。

Answer 1

要了解这个程序，你需要了解两个快速排序和最显著位基数排序。

喜欢快速排序，它分隔所述阵列成零件，然后递归排序部件。它首先根据最高有效位的值进行分区。然后它在两边都会递归。但是这一次，对于每一半，它基于第二重要位进行分区。然后重新划分，并为每个1/4，其划分的13类最显著有点...

注意的是，虽然我说的“1/2”，“1/4”，等等，它通常不会将数组精确地分为1/2,1/4等。每个分区的大小将取决于数组中的数字分布。对于正常的快速排序，每个分区的大小取决于选择为“枢轴”的元素，但对于这个“基数快速排序”不是这样 - “枢轴”的顺序是固定的。

还要注意，不像一个正常的快速排序，它可以去二次，并成为某些输入速度很慢，这种“快速排序”保证在固定的遍数来完成。实际上，无论输入如何，所需通过次数都是一个常数。 （这是基数排序的典型属性 - 性能往往对输入不敏感）。

另一个有趣的属性：正常的快速排序会将数组分成3个部分 - 那些小于，等于和大于枢。但是这个“快速排序”总是在每次通过时将其输入精确地分为2个部分 - 那些在测试位置具有0位的数据，以及具有1位的数据。

我觉得这个算法的名称实际上是“二进制快速排序”。

Answer 2

你while(1)循环操作逐位的无符号整数。对于每一位，它从列表的顶部和底部开始，找到第一对整数，其中位设置在底部而不是顶部，并交换它们。这纠正了该位的这些值的排序。

它继续这样做直到顶部/底部相遇。最后，每次通过while(1)循环时，都会导致列表中的所有数字都在该列表底部未被设置，并且所有具有该位的数字都被设置在列表顶部。

然后按顺序对列表进行排序，从MSB开始，然后是第二个MSB，...，最后是LSB。值INT_MIN对带符号整数为负，但对应于二进制补码中的MSB。

x[i] ^= INT_MIN行允许基数排序正确处理负数。带符号的整数以二进制补码形式存储。这实际上意味着负数具有MSB设置。

如果你天真地将一个基数类型应用于带符号整数，最终的结果是排序的正数低于负数。

x[i] ^= INT_MIN翻转MSB，它解决了这个问题。第二个x[i] ^= INT_MIN翻转回来。