java - 使用位掩码和二进制运算符的排序算法

Question

我正在努力理解以下算法(在 Java 中)是如何工作的。

private static void sort(int[] values, k) 
{
    int mask = 0x00000001 << k;
    int insertIndex = 0;
    int ArrayList<Integer> big = new ArrayList<Integer>();

    for (int i = 0; i < values.length; ++i) {
        if ((values[i] & mask) == 0) 
            values[insertIndex++] = values[i];
        else
            big.add(values[i]);
    }

    for (int i = 0; i < big.size(); ++i)
        values[insertIndex++] = big.get(i);
}

public static void sort(int[] values) 
{
    for (int i = 0; i < 31; ++i)
        sort(values, i);
}

这是我到目前为止所理解的:

首先 0x00000001(32 位？)左移 k。所以掩码现在是其他数字。然后我们检查当前值 values[i] 使用 Binary-And 运算符添加 mask 是否等于 0。

我无法理解 (values[i] & mask) == 0 子句的作用。第二个 for-loop 也让我头疼。为什么我们只在 public static void sort(int[] values) 中迭代 31 次？

此算法无法正确排序负整数。为何如此？如何修改它以使负整数也得到排序？

据说该算法使用了与一种著名的排序算法类似的概念。像堆排序、插入排序、快速排序、归并排序、桶排序 或 基数排序。我排除了 Quick-sort 的可能性，因为它使用分区和递归。 合并排序使用递归和合并子数组，所以我也取消了它。 插入排序 也不太可能是那个，因为时间复杂度差异很大。 插入排序 O(n^2) 并且给定的算法是O(n)。 桶排序 实际上并不对任何东西进行排序，它只是将数组分成子数组，然后可以使用某种排序算法对其进行排序。 堆排序是一种基于比较的算法，给定的算法看起来不像。所以剩下的唯一可能是 Radix-Sort，它不是基于比较的算法。所以我最好的选择是给定的算法类似于基数排序。我是对的还是我绝望地迷路了？

Answer 1

是的，这是使用按位运算符的基数排序的实现。由于按位运算符，实现不是很直观。

该算法的工作原理是一次对列表中的一位数字进行排序。这就是为什么有31个循环...因为一个Java整数只有32位，最左边的位表示该值为负数，所以一个positiveJava整数只有31位.

掩码用于跟踪正在检查的位置。 0x0001是那个地方，0x0002是二位，0x0004是三分位，0x0001 << n是第n位。

排序是通过将检查位为 0 的所有整数放在数组的左侧，将检查位为 1 的所有整数放在右侧来完成的。这很简单:mask & values[i] == 0如果值的屏蔽位是 0。

当我们开始移动变量时，事情就变得棘手了。每当我们在检查的位中发现一个值为 0 的值时，我们就想将它向左移动。但是，这涉及覆盖一个值。 insertIndex和 i两者都从 0 开始。每次我们在位置“i”找到一个需要向左移动的值时，我们将它移动到 insertIndex，如果我们找到一个需要向右移动的值，我们将它存储在一个稍后使用的临时数组列表。

0 0 1 0 1 0   i and insertindex are the same, so we copy the 0 to itself
^

0 0 1 0 1 0   Again.
  ^

0 0 1 0 1 0   Here we find our first 1. We don't increment insertindex
    ^         We store the 1 in the temp array list. Nothing is copied.

0 0 0 0 1 0   This is a zero. We copy the zero from i to insertindex
    ^<^

0 0 0 0 1 0   Another 1 goes in the temp array list. Nothing is copied, we don't 
              increment insertindex.
      ^ ^

0 0 0 0 1 0   We copy the last zero from i to insertindex. Remember that the
      ^<<<^   zero we overwrite is actually safely in the third bit - it
              was copied earlier.

现在对于第二个 for 循环，我们获取存储在临时数组列表中的所有值，并将它们放在数组现在为空的右侧。这边的所有东西都在数组“左侧”的其他地方。

0 0 0 0 1 0   Retrieve the first value from the temp array list
        ^

0 0 0 0 1 1   Retrieve the second value from the temp array list
          ^

希望对您有所帮助!如果您想将其扩展为负值，请尝试查看 Two's Complement notation