在C/C++中从int获取基数排序的最佳方法

Question

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

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

Answer 1

使用大小的数字2^k.提取n数字:

#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(基数8)运行良好并且限制了桶的数量,但是k==4(基数16)看起来更有吸引力,因为它划分了字大小.然而,没有划分字大小的基础确实没有问题,你可能会发现基数32或基数64表现更好.这是一个实验性问题,根据缓存的行为方式以及阵列中有多少元素,硬件可能会有所不同.

最后的注意事项:如果你要对有符号整数进行排序,那么生活就会受到更大的痛苦,因为你想把最重要的一点视为签名.我建议将所有内容视为未签名,然后如果你真的需要签名,在你的基数排序的最后一步你将交换桶,以便最重要的1之前的桶来到最重要的0之前.如果这个问题肯定更容易k划分单词大小.