C/C++中基数排序的最佳方法

使用大小的数字 2^k n 第位数字:

#define BASE (2<<k)
#define MASK (BASE-1)

inline unsigned get_digit(unsigned word, int n) {
    return (word >> (n*k)) & MASK;
}

在那之后,选择最佳的基础是一个实验性的问题(特定硬件的时间/空间权衡)。可能 k==3 (基数8)运行良好,限制了铲斗的数量,但 k==4

最后一点注意:如果您正在排序 整数生活是一个更大的痛苦,因为你想把最重要的位作为符号。我建议将所有内容都视为无符号,然后如果确实需要有符号,则在基数排序的最后一步,您将交换存储桶,以便具有最高有效1的存储桶位于最高有效0之前 一定地 k 分词大小。

不要用基数10,用基数16。

for (int i = 0; i < 8; i++) {
    printf("%d\n", (n >> (i*4)) & 0xf);
}

由于整数以二进制形式存储在内部,因此这比除以10来确定 十进制的 数字。