递归地实现基数排序 - 如何在最后打印元素？

Question

注：

我已经问了一个关于这个程序的具体问题，但现在我卡在了最后一步，我想为它打开一个新线程可能会更好。

描述：

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

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

[23456, 24567],

我们想要比较 3 和 4。为此，我们在每次递归调用中计算 digit / 10。如果数字为 0，则不再需要排序。

递归调用本身适用于从 0 到 9 的行，我们之前在其中输入了不同的数字，现在通过将它们放在不同的行中再次对它们进行排序。

问题：

我认为程序做了它应该做的事情。不幸的是，我不知道如何正确打印结果。例如，在下面的代码中，我试图在 main 方法中打印出 bucket，但它只准确地给出了我刚刚输入的数组，所以这是不对的。

我需要从第 9 行的所有元素开始，如果这一行包含多个数字，我必须按照递归调用的结果对它们进行排序。

有人知道如何正确实施吗？提前致谢！

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

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

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

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

  digit = digit / 10;

  for (i = 0; i < 9; i++) {
    sort(space[i], digit); 
  }

  return numbers

}

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); 

  for (int i = 0; i < bucket.length; i++) {
    System.out.println(bucket[i]);

}

Answer 1

在排序中，正在更新 space 的本地实例，但它返回输入参数编号，但未更新。

我认为 space 应该初始化为 space[10][0]，因为 space 的另一行可能没有任何数据。

您确定这应该是从右到左（最低有效位在前）基数排序吗？通常这是通过迭代完成的（只需将 space 复制回每个外循环中的数字）。基数排序从左到右（最重要的数字在前）通常使用递归完成。

Bijay Gurung 的 sort() 可以稍微简化。评论中指出的更改：

public static int[] sort(int[] numbers, int digit) {
    if (numbers.length == 0 || digit <= 0)
        return numbers;
    int[][]space = new int[10][0];  // [1] => [0]
    int[] len = new int[10];
    int i, j;
    for (j = 0; j < numbers.length; j++) {
        i = (numbers[j] / digit) % 10;
        len[i]++;
        space[i] = putInBucket(space[i], numbers[j]);
    }
    for (i = 0; i < 10; i++) {
    //  int[] bucket = new int[len[i]];        // deleted
    //  for (int k = 0; k < len[i]; k++)       // deleted
    //      bucket[k] = space[i][k];           // deleted
        space[i] = sort(space[i], digit / 10); // bucket => space[i]
    }
    int k = 0;
    for (i = 0; i < 10; i++) {
        for (j = 0; j < len[i]; j++) {
            numbers[k] = space[i][j];
            k++;
       }
    }
    return numbers; 
}

Answer 2

正如我在中针对您之前的问题所展示的那样，您需要 return 排序 numbers。您可以通过从最小到最大数字遍历 space 来获得排序后的数字。

  int k = 0;

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

为此，您可能需要跟踪每个数字的桶长度（len[i] 变量）。

完整的解决方案是：

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

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

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

      for (j = 0; j < numbers.length; j++) {
            i = (numbers[j] / digit) % 10;
            len[i]++;
            space[i] = putInBucket(space[i], 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; 

}

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];
    }
    bucket_new[0] = number;

    return bucket_new;

}

递归地实现基数排序 - 如何在最后打印元素？

Implementing Radix sort recursively - how to print the elements at the end?

java

arrays

sorting

recursion

radix-sort