固定长度的字符串排序

Question

我想对整数进行排序。因此，我将它们解释为长度为 32 的二进制字符串。现在我可以为每个组件应用 bucketsort。这是我在 java:

中的实现

public static void sort(List<Integer> numbers)
{
    Queue<Integer> tmp =new LinkedList<Integer>();
    for (int i = 0; i < numbers.size(); i++) {
        tmp.offer(numbers.get(i));
    }

    List<Integer>[] bucket = new ArrayList[2];
    for (int i = 0; i < bucket.length; i++) {
        bucket[i] = new ArrayList<Integer>();
    }

    for (int k = 32; k > 0; k--) {
        // Clear
        for (int i = 0; i < bucket.length; i++) {
            bucket[i].clear();
        }

        while (!tmp.isEmpty()) {
            Integer firstel =tmp.element();
            String el =String.valueOf(firstel);

            if (el.charAt(k - 1) == 0) {
                bucket[0].add(firstel);
            } else {
                bucket[1].add(firstel);
            }
            tmp.remove();
        }

        for (int i = 0; i < bucket.length; i++) {
            for (Integer j : bucket[i]) {
                tmp.add(j);
            }
        }
    }
}

我不确定我的代码是否正确处理了这些二进制字符串。我是否必须将整数从列表数字转换为二进制字符串？注意：仅供练习。时间复杂度没有更深层次的意义。

Answer 1

Java 已经提供了一个方便的 api 作为集合框架的一部分。 Collections.sort（数字）；这将按升序对整数进行排序。如果你需要不同的顺序，你可以使用另一个 api 也需要 Comparator.

Answer 2

让我们先稍微重写一下，因为不需要队列或 tmp arraylist 等。第一步，一个让我们少写代码的存根 class:

private class Numlist extends ArrayList<Integer> {
  Numlist() { super(); }
}

完成，我们不再需要到处写ArrayList<Integer>。

现在，java 执行 "autoboxing"，因此您存储整数的任何内容都可以执行 int，反之亦然。这很方便，因为我们可以扔掉所有的字符串。如果我们只关心位比较，我们不需要它：

public void sort(Numlist numbers) {
  // No copying `numbers` to a `tmp` queue: just work with it directly.
  Numlist zeroes, ones;

  for (int k = 1; k < 32; k++) {
    // Build this step's masking value, which we can use to
    // find the value of individual bits by using bitwise AND.
    // Also note that we _know_ this is a safe integer operation.
    mask = (int) Math.pow(2,k);

    // just allocate new lists; it's about as fast as clearing.
    zeroes = new Numlist();
    ones = new Numlist();

    // "scatter": now we empty the numbers list one element at a
    //  time, and then we'll fill it back up after we emptied it.
    while (!numbers.isEmpty()) {
      int e = numbers.remove(0);

      if ((e & mask) == mask) {
        ones.add(e);
      } else {
        zeroes.add(e);
      }        
    }

    // "gather"
    for (int i: zeroes) { numbers.add(i); }
    for (int i: ones) { numbers.add(i); }      
  }
}

通过重写，一切正常。我们删除了很多冗长的内容，这使得我们更容易理解代码的作用，并且我们删除了整个 "int to string to substring, then char comparison"，这意味着出错的可能性要小得多。

在测试方面，将您的功能添加到以下 class:

import java.lang.Math;
import java.util.ArrayList;

public class Test {

  // private class goes here

  public static void main(String[] argv) { new Test(); }

  public Test() {
    Numlist list = new Numlist();
    list.add(10);
    list.add(77810);
    list.add(4);
    list.add(100);
    list.add(1);
    list.add(290387423);
    list.add(23423);
    sort(list);
    System.out.println(list);
  }

  // function goes here
}

完成：javac 将愉快地编译它，执行应该产生 [1, 4, 10, 100, 23423, 77810, 290387423]

您还会注意到我们没有使用 for (int k = 31; k > 0; k--) 但我们正在使用 for (int k=1; k<32; k++)... 为什么？有区别吗？

差别很大

通过运行将我们的掩码从 b000...001 调整到 b100...000，我们保证尽管 "picking values back out"，它们的相对 "less than the current bit" 顺序被保留。

如果我们运行以另一种方式进行屏蔽，从 b1000...000 到 b000...001，那么在每一步中我们都会取消刚刚设置的顺序，结果是根本不是排序列表：[1, 4, 100, 77810, 10, 290387423, 23423]

** 编辑 **：为什么屏蔽有效？

整数类型byte、char、int和long分别只是1、2、4、8字节的位模式，所以所有这些已经是 "binary numbers"，我们只需要一种方法来访问各个位，我们可以使用 bitwise masking 来实现。

为了屏蔽掉 "everything but a specific bit"，您可以采用一些位模式的按位与，以及一个只设置了一个位的模式，我们可以很容易地创建因为这些只是 "powers of 2".

的数字

例如，要检查数字 23 中的位，我们可以使用以下检查：

     23  &   1     2    4      8     16    32  

b0    1  &  1=1   0=0   0=0   0=0   0=0   0=0
b1    1  &  0=0   1=1   0=0   0=0   0=0   0=0
b2    1  &  0=0   0=0   1=1   0=0   0=0   0=0
b3    0  &  0=0   0=0   0=0   1=0   0=0   0=0
b4    1  &  0=0   0=0   0=0   0=0   1=1   0=0
b5    0  &  0=0   0=0   0=0   0=0   0=0   1=0

在这里我们可以看到数字 23，二进制 10111，以及通过 2 的每个幂进行掩码的结果：23 & 1 产生 1，所以我们知道第一位已设置。我们看到 23 & 2 产生 2，所以我们知道第二位已设置。 4 也一样，但是 23 & 8 产生 0。我们知道第四位是 not set.

因此我们可以使用按位与检查任何长度的位模式：如果 (number & mask) == mask 我们知道该掩码的位已设置。如果结果为 0，则我们知道该位未设置。

另请注意，&与&&不相同：&是按位与运算，对运算符左右手之间的每一位。 &&运算符是逻辑AND，要求左右两边为布尔值。逻辑与实际上是 "a single AND"，而按位与是 "as many AND operations as there are bits to test".

固定长度的字符串排序

Sorting of strings with fixed length

java

bucket

radix-sort