1

我想知道遵循基数排序程序的逻辑。

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

我被卡住了，因为我不太了解 while(1) 循环..

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

INT_MIN=-2147483648

bit这与in的值相同rad_short_u()

我已经调试了程序，由于rand() % 512-256，还生成了一些 -ve 值，

在第一次传递期间，它将所有 -ve 值交换到一侧（从开始）和 +ve 之后从下一次传递它向左移动到 1 位，因此位的值从那时变为 1073741824 直到它变成 1 数组保持不变。

请帮助我理解程序逻辑。

4

2 回答 2

3

要理解这个程序，你需要理解快速排序和最高有效位基数排序。

与快速排序一样，它将数组划分为多个部分，然后递归地对这些部分进行排序。它首先根据最高有效位的值进行分区。然后它在两半上递归。但是这一次，对于每一半，它根据第二个最高有效位进行分区。然后它再次划分，对于每 1/4，它在第 3 个最高有效位上划分......

请注意，虽然我说的是“1/2”、“1/4”等，但它通常不会将数组精确地划分为 1/2、1/4 等。每个划分的大小取决于数组中的数字分布。对于普通的快速排序，每个分区的大小将取决于选择为“枢轴”的元素，但对于这种“基数快速排序”来说，情况并非如此——“枢轴”的顺序是固定的。

另请注意，与正常的快速排序不同，它可能会变成二次方并且在某些输入上变得非常慢，这种“快速排序”保证在固定数量的通过中完成。实际上，无论输入如何，所需的通过次数都是一个常数。（这是基数排序的一个典型属性——性能往往对输入不敏感。）

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

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

于 2012-06-28T20:07:06.697 回答
0

您的while(1)循环对无符号整数按位运行。对于每个位，它从列表的顶部和底部开始，找到该位设置在底部而不是顶部的第一对整数，然后交换它们。这更正了这些值在该位的顺序。

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

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

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

如果你天真地对有符号整数应用基数排序，你最终会得到排序为比负数更低的正数。

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

于 2012-06-28T20:21:04.087 回答