基数排序为负整数

Question

我试图为整数实现基数排序,包括负整数.对于非负的int,我计划为数字0-9创建一个10个队列的队列,并实现LSD算法.但我对负整数感到困惑.我现在想的是,继续为他们创建10个队列的另一个队列并分别对它们进行排序,然后在最后,我将给出2个列表,一个包含负的整数排序,另一个包含非负的整数.最后我会合并它们.

你怎么看待这件事？是否有更有效的方法来处理负整数？

谢谢!

Answer 1

您可以将标志视为一种特殊的数字.你对单位进行排序,然后对数十等进行排序,最后在标志上进行排序.这确实会产生负面的反转顺序,然后您只需反转该存储桶的内容即可.这是多大的机械卡分拣机的工作原理.

Answer 2

另一种解决方案是将负整数从数组中分离出来，使它们为正数，使用基数将其排序为正值，然后将其反转并附加排序的非负数组。

Answer 3

请注意,符号位是有符号整数中的最高位,但默认情况下,所有数字都被基数排序视为无符号整数.因此,您需要告诉算法负数小于正数.在32位有符号整数的情况下,您可以先排序三个较低的字节,然后对符号位反转的第四个(较高)字节进行排序,这样0将用于负数而不是1,因此它们将首先出现.

我强烈建议逐字节而不是十进制数字对数字进行排序,因为机器拾取字节要比提取数字容易得多.

Answer 4

接受的答案需要多通过一次。

只需翻转符号位即可。

这假设您正在使用补码表示，这对我们 99% 的人来说都是如此。

下表演示了在按字典顺序排序时，简单地翻转符号位将导致补码整数正确排序。

第一列给出一个 4 位二进制值，第二列给出这些位作为有符号整数的解释，第三列给出那些高位翻转的位的解释。

Binary    | 2s-comp  | Flip sign
----------+----------+----------
0000      | 00       | -8
0001      | +1       | -7
0010      | +2       | -6
0011      | +3       | -5
0100      | +4       | -4
0101      | +5       | -3
0110      | +6       | -2
0111      | +7       | -1
1000      | -8       | 00
1001      | -7       | +1
1010      | -6       | +2
1011      | -5       | +3
1100      | -4       | +4
1101      | -3       | +5
1110      | -2       | +6
1111      | -1       | +7

punpcklbw 给出的答案建议仅在查看最高字节时翻转该位，但每次简单地翻转符号位会更快。这是因为翻转位的单个异或比决定是否应该翻转的分支更快。

[需要提及的一个重要细节（一些教科书未能正确解决）是，真正的实现应该使用基数 256 而不是基数 10。这允许您读取字节而不是十进制数字。]