首页 文章

基数排序工作

提问于
浏览 次
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

这与 rad_short_u() 中 bit 的值相同

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

在第一次传递期间，它将所有-ve值交换到一侧（从开始），然后从下一次传递开始，它向左移位到1位，因此位的值从此变为1073741824，直到它变为1阵列保持相同 .

请帮我理解程序逻辑 .

c radix-sort

2 回答

  • 0

    要理解这个程序，您需要了解快速排序和最重要位基数排序 .

    像quicksort一样，它将数组分成几部分，然后递归地对部分进行排序 . 它首先根据最高位的值进行分区 . 然后它在两个部分进行递归 . 但这一次，对于每一半，它基于第二个最重要的位进行分区 . 然后它再次划分，并且对于每1/4，它在第3个最重要的位上划分...

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

    另请注意，与普通快速排序不同，普通快速排序可以在某些输入上变为二次且变得非常慢，这种“快速排序”可以保证以固定的次数完成 . 实际上，无论输入如何，所需的传球次数都是常数 . （这是基数排序的典型属性 - 性能往往对输入不敏感 . ）

    另一个有趣的特性：正常的快速排序会将阵列分成3个部分 - 比枢轴更小，相等和更大 . 但是这个"quicksort"总是在每次传递时将其输入分为2个部分 - 在被测位置中为0位，在1位时为0 .

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

    回复于
  • 3

    您的 while(1) 循环在无符号整数上按位运行 . 对于每个位，它从列表的顶部和底部开始，找到第一对整数，其中位设置在底部而不是顶部，并交换它们 . 这会纠正该位的这些值的排序 .

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

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

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

    如果您天真地将基数排序应用于有符号整数，则最终将正数排序为低于负数的索引 .

    x[i] ^= INT_MIN 翻转MSB，修复了这个问题 . 第二个 x[i] ^= INT_MIN 翻了回来 .

    回复于

相关问题