c - 基数排序工作

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

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

到目前为止我所知道的是:

INT_MIN=-2147483648

这与 rad_short_u() 中 bit 的值相同

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

在第一次通过时，它将所有 -ve 值交换到一侧(从开始)，然后是 +ve从下一次开始，它向左移动 1 位，因此位的值从那时变为 1073741824 直到它变为 1 数组保持不变。

请帮助我理解程序逻辑。

Answer 1

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

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

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

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

另一个有趣的特性:普通的快速排序会将数组分成 3 个部分——小于、等于和大于主元。但是这种“快速排序”总是在每次通过时将其输入恰好分成两部分——被测试位置的 0 位和 1 位。

我觉得这个算法的名字其实是“二元快速排序”。