我被困在递归地实现Radix排序 [英] I am stuck at implementing Radix sort recursively

问题描述

我需要实现一个程序，该程序对0到99999之间的数字进行递归排序(这基本上是Radix排序).该过程本身就是一个简单的例子:用户在main方法中键入一个包含这些数字的数组.然后，main方法调用排序方法，在此方法中，我创建了一个名为'space'的二维数组，该数组包含10行和1列.然后，我将数组中的每个数字除以数字，第一次运行将为10.000.因此，例如23456/10000 = 2,3456 = 2(在Java中)，因此，程序会将这个数字放在space [2] [0]中，因此放在第二行中.然后，我们将整个行都进行扩展，这是通过putInBucket方法完成的.我们这样做是为了确保我们可以在同一行中放入另一个数字.

I'm required to implement a programm that sorts numbers ranging from 0 to 99999 recursively (this is basically Radix sort). The process itself is kinda simpel: The user types in an array that contains those numbers in the main method. Then, the main method calls for the sort-method where I create a two-dimensional array named 'space' with 10 rows and 1 column. Then, I divide every number in the array by the digit, which would be 10.000 in the first run. So, for example, 23456 / 10000 = 2,3456 = 2 (in java), hence, the programm puts this number in space[2][0], so in the second row. Then, we take this entire row and extend it, which is done in the putInBucket-method. We do this in order to make sure that we can put another number into the same row.

我们对数字"数组中的每个数字执行此操作.然后，我们要使用这些行并按照相同的原理再次对其进行排序，但是现在我们看一下第二个数字.我们想从左到右，而不是从右到左.因此，如果我们的第二行看起来像这样

We do this for every number that is inside the 'numbers'-array. Then, we want to work with these rows and sort them again by the same principle, but now we take a look at the second digit. We want to do this from left to right, not from right to left. So, if our second row would look like this

[23456，24567]，

[23456, 24567],

我们想比较3和4，得出23456< 24567.

we'd want to compare the 3 and the 4, which leads to 23456 < 24567.

我们在sort方法末尾的递归调用的帮助下执行此操作.现在，这是我迷路的地方.我根本不知道如何操纵数字变量以便能够使用每个数字的第二，第三，...数字.如您所见，在第一轮中，可以简单地将其除以10.000，但是我没有找到进一步的方法.

We do this with the help of the recursive call at the end of the sort method. Now, this is where I am lost. I simply don't know how to manipulate the digit-variable in order to be able to work with the second, third, ... digit of each number. In the first run, as you see, this can be simply done by dividing through 10.000, but I didn't find a way to go further from here.

请注意:是的，这是一个家庭作业问题，因此，只允许在这里使用基元.我们还没有经历过math.pow(...)之类的事情.预先感谢！

Please note: Yes, this is a homework question, hence, I'm only allowed to use primitives here. We didn't go through stuff like math.pow(...) yet. Thanks in advance!

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

}

推荐答案

要提取最后一位数字，余数运算符%是您的朋友:

To extract the last digit, the remainder operator % is your friend:

123 % 10 == 3

如果尚未涵盖%运算符，则可以使用

if you haven't covered the % operator yet, you can use

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

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

To extract another digit, you can first move it to the end with /:

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

因此，您可以使用

(number / mask) % 10 

其中mask∈{...，10000，1000，100，10，1}.

where mask ∈ {..., 10000, 1000, 100, 10, 1}.

额外信用

基数排序通常在二进制数系统中实现，因为可以提取二进制数字(或其序列)而无需执行除法，这更有效:

Radix sort is usually implemented in the binary number system instead because a binary digit (or a sequence thereof) can be extracted without performing a division, which is more efficient:

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

此外，如果您要真正实现此目标，则需要一种更有效的方式来增加存储桶(您的实现需要O(n)将单个元素添加到存储桶中，向存储桶中添加n个元素因此需要O (n ^ 2)，这会使您的基数排序比插入排序慢). 动态数组通常使用效率更高的

Also, if you are implementing this for real, you'd need a more efficient way to grow buckets (your implementation takes O(n) to add a single element to the bucket, adding n elements to the bucket therefore takes O(n^2), which makes your radix sort slower than insertion sort). Dynamic arrays are usually implemented with a more efficient geometric expansion.

这篇关于我被困在递归地实现Radix排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！