algorithm - 实现类似于 radix 的排序

Question

嗨，我需要写 sucj 排序，也许它类似于基数排序而且(这不是家庭作业，因为我自己创造了它的问题，如果有人可以帮助我请)问题是这样的假设我有数组 int x[]=new int[]{4,5,3,2,1};让我们把它写成二进制形式5 -01014- 01003-00112-00101-0001我想通过使用按位运算符对这些元素进行排序或检查每一位，如果交换较少，任何人都可以帮助我例如取 5 和 4 检查第一个最右边的位 0==0 所以在 1 索引中继续 1==1 接下来相同的 0=0 和最后一个 1>0 这意味着第一个元素大于第二个所以交换它

Paraphasing:

I need to create a sort similar to radix.

Suppose I have an array: int x[] = new int[] {4, 5, 3, 2, 1};

Or, in binary form: 5-0101 4-0100 3-0011 2-0010 1-0001

I want to sort these elements by using bitwise operators or check each bit and (if less) exchange it. For example, consider 5 and 4:

The leftmost or most significant bit (MSB) of 5 in binary is 0, as is the MSB of 4. Since 0 == 0 the process continues. The next two bits (0 then 1) are also equivalent. Finally the rightmost or least significant bit (LSB) of 5 is 1 whereas the LSB of 4 is 0, indicating that the two values should be exchanged.

Answer 1

要获取 int x 的第 k 位，您可以执行以下操作:

int bit = (x >> k) & 1;

这是一个测试工具:

    int xs[] = {4,5,3,2,1};
    for (int k = 0; k < 4; k++) {
        for (int x : xs) {
            int bit = (x >> k) & 1;
            System.out.format("|%s|  ", bit);
        }
        System.out.println();
    }

这打印(带注释)

x= 4    5    3    2    1  k=
  |0|  |1|  |1|  |0|  |1|  0
  |0|  |0|  |1|  |1|  |0|  1
  |1|  |1|  |0|  |0|  |0|  2
  |0|  |0|  |0|  |0|  |0|  3

这里的棘手位是符号位，即 int 上的第 31 位。当它是1 时，表示负数。您可能希望首先有一个仅适用于正 int 的实现，然后再添加对负数的支持。

另见

• Wikipedia/Two's complement