c++ - 从 int 获取单个数字以在 C/C++ 中进行基数排序的最佳方法

Question

从具有 n 个数字的 int 中获取单个数字以用于基数排序算法的最佳方法是什么？我想知道在 C/C++ 中是否有特别好的方法，如果没有，一般的最佳解决方案是什么？

编辑：为了澄清，我正在寻找一个解决方案，而不是将其转换为字符串并将其视为数字数组。

Answer 1

使用 size 的数字2^k。要提取第nth 位：

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

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

使用移位和掩码（通过 base 为 2 的幂）避免了昂贵的整数除法指令。

之后，选择最佳基础是一个实验性问题（特定硬件的时间/空间权衡）。可能k==3（base 8）效果很好并且限制了桶的数量，但是k==4（base 16）看起来更有吸引力，因为它划分了单词大小。但是，不分字长的基数确实没有什么问题，您可能会发现基数 32 或基数 64 的性能更好。这是一个实验性问题，可能会因硬件而异，具体取决于缓存的行为方式以及数组中有多少元素。

Final note: if you are sorting signed integers life is a much bigger pain, because you want to treat the most significant bit as signed. I recommend treating everything as unsigned, and then if you really need signed, in the last step of your radix sort you will swap the buckets, so that buckets with a most significant 1 come before a most significant 0. This problem is definitely easier if k divides the word size.

Answer 2

不要使用基数 10，使用基数 16。

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

由于整数在内部以二进制形式存储，因此这将比除以 10 来确定十进制数字更有效。