我坚持递归地实现基数排序

Question

我需要实现一个程序，对 0 到 99999 之间的数字进行递归排序（这基本上是基数排序）。该过程本身有点简单：用户在 main 方法中键入一个包含这些数字的数组。然后，主要方法调用排序方法，我在其中创建一个名为 'space' 的二维数组，其中包含 10 行和 1 列。然后，我将数组中的每个数字除以第一个运行中的数字，即 10.000。因此，例如，23456 / 10000 = 2,3456 = 2（在 java 中），因此，程序将此数字放在 space[2][0] 中，也就是第二行。然后，我们获取整行并扩展它，这是在 putInBucket 方法中完成的。我们这样做是为了确保我们可以将另一个数字放入同一行。

我们对 'numbers' 数组中的每个数字都这样做。然后，我们想对这些行进行处理，并按照相同的原则再次对它们进行排序，但现在我们看一下第二位数字。我们想从左到右，而不是从右到左。所以，如果我们的第二行看起来像这样

[23456, 24567],

我们想比较 3 和 4，这导致 23456 < 24567。

我们借助排序方法末尾的递归调用来完成此操作。现在，这就是我迷路的地方。我根本不知道如何操作数字变量以便能够处理每个数字的第二个、第三个……数字。在第一个运行中，如您所见，这可以通过除以 10.000 来简单地完成，但我没有找到进一步的方法。

请注意：是的，这是一道作业题，因此，我只能在这里使用原语。我们还没有经历 math.pow(...) 之类的事情。提前致谢！

public static int[] sort(int[] numbers, int digit) {

  if (numbers.length == 0)
    return numbers;

  int[][]space = new int[10][1];
  int i, j = 0;

  for (j = 0; j < numbers.length; j++) {
    i = numbers[j] / digit;
    space[i][0] = numbers[j];
    space[i] = putInBucket(space[i], numbers[j]);
  }

  for (i = 0; i < space[i].length; i++) {
    sort(space[i], digit); //not sure how to work with digit here
  }

  return ... //not sure what to return here

}

private static int[] putInBucket(int[] bucket, int number) {

  int[] bucket_new = new int[bucket.length+1];

  for (int i = 1; i < bucket_new.length; i++) {
    bucket_new[i] = bucket[i-1];
  }

  return bucket_new;

}

public static void main (String [] argv) {

  int[] numbers = IO.readInts("Numbers: ");
  int digit = 10000;
  int[] bucket = sort(numbers, digit); 

}

Answer 1

要提取最后一位，余数运算符%是你的朋友：

123 % 10 == 3

如果您还没有学习 % 运算符，您可以使用

123 % 10 == 123 - (123 / 10 * 10) == 3

要提取另一个数字，您可以先将其移动到末尾 /:

123 / 10 == 12
12 % 10 == 2

因此您可以使用

提取任意数字

(number / mask) % 10

其中掩码 ∈ {..., 10000, 1000, 100, 10, 1}.

加分

基数排序通常在二进制数字系统中实现，因为无需执行除法即可提取二进制数字（或其序列），效率更高：

x % 16 == x & 15;
x \ 16 == x >> 4;

另外，如果你真的要实现这个，你需要一种更有效的方法来增加桶（你的实现需要 O(n) 来将单个元素添加到桶中，因此将 n 个元素添加到桶中需要 O(n^2)，这使得基数排序比插入排序慢）。 Dynamic arrays are usually implemented with a more efficient geometric expansion.

Answer 2

这应该有效：

public static int[] sort(int[] numbers, int digit) {

     if (numbers.length == 0 || digit <= 0)
           return numbers;

     int[][]space = new int[10][10];
     int[] len = new int[10];
     int i, j = 0;

      for (j = 0; j < numbers.length; j++) {
            i = (numbers[j] / digit) % 10;
            len[i]++;
            for (int k = len[i] - 1; k > 0; k--) {
                space[i][k] = space[i][k - 1];
            }
            space[i][0] = numbers[j];
      }


      for (i = 0; i < 10; i++) {
          int[] bucket = new int[len[i]];
          for (int k = 0; k < len[i]; k++) 
              bucket[k] = space[i][k];
          space[i] = sort(bucket, digit / 10); 
      }

      int k = 0;

      for (i = 0; i < 10; i++) {
          for (j = 0; j < len[i]; j++) {
              numbers[k] = space[i][j];
              k++;
          }
      }

      return numbers; 

}

a) 首先，space 被分配为只有一列。因此，space[i] = bucket 将不起作用。

相反，您可以将其声明为 int[10][10]。（注意：它只支持一个桶中最多 10 个值）。或者您可以通过编程方式分配新数组。或者，当然，List 可能更适合。

b) i = (numbers[j] / digit) % 10;

只获取所需的数字。例如：如果数字是 12130，并且 digit = 1000，我们希望将 i 设置为 2，而不是 12。

c) putInBucket 替换为就地循环。

d) 对于 space 的每个 bucket，我们通过递归调用 sort 将其排序为低一位。

e) 最后，要返回的结果 (numbers) 可以通过从数字 0 到 9 循环 space 来创建。

注意：这个解决方案可能会变得更好。

我坚持递归地实现基数排序

I am stuck at implementing Radix sort recursively

java

arrays

sorting

recursion

radix-sort