递归地实现Radix排序-如何在最后打印元素? [英] Implementing Radix sort recursively - how to print the elements at the end?
问题描述
注意:
I already asked a specific question on this programm before, but now I'm stuck at the very last step and I guess it might be better to open a new thread for it.
说明:
我需要实现一个程序，该程序对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.为此，我们在每个递归调用中计算位数/10.如果数字为0，则不再排序.
we'd want to compare the 3 and the 4. In order to do so, we calculate digit / 10 in each recursive call. If the digit is 0, there is nothing to sort anymore.
递归调用本身适用于0到9的行，我们在此之前输入了不同的数字，现在通过将它们放在不同的行中再次对它们进行排序.
The recursive call itself works with the rows from 0 to 9 where we put in the different numbers before and now sorts them again by putting them in different rows.
问题:
我认为程序可以完成它应该做的事情.不幸的是，我不知道如何正确打印结果.例如，在下面的代码中，我尝试在main方法中打印出存储区，但它只能为我提供刚键入的数组，因此可能不正确.
I think the programm does what it is supposed to do. Unfortunately, I don't know how to print the result properly. For example, in the code below, I tried to print out the bucket in the main method, but it only gives me exactly the array that I just typed in, so that can't be right.
我需要从第9行中的所有元素开始，如果这一行包含多个数字，则必须按递归调用中得到的结果对它们进行排序.
I need to start with all the elements in the row 9, and if this row contains more than one number, I'd have to sort them by the results I got in the recursive call.
有人知道如何正确实施吗?预先感谢！
Does anyone have an idea how to implement this properly? Thanks in advance!
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 中所展示的问题，您需要返回排序后的numbers.您可以通过从最小的数字到最大的数字通过space获得排序的数字.
As I demonstrated in my answer to your previous question, you need to return the sorted numbers. You get the sorted numbers by going through space from the smallest to the largest digits.
int k = 0;
for (i = 0; i < 10; i++) {
for (j = 0; j < len[i]; j++) {
numbers[k] = space[i][j];
k++;
}
}
为此，您可能需要跟踪每个数字的存储桶的长度(len[i]变量).
For that, you would probably need to keep track of the lengths of the buckets for each digit (the len[i] variable).
完整的解决方案是:
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;
}
这篇关于递归地实现Radix排序-如何在最后打印元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
