我需要实现一个程序，对从 0 到 99999 的数字进行递归排序(这基本上是基数排序)。该过程本身有点简单:用户在 main 方法中输入包含这些数字的数组。然后，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);
}
最佳答案
要提取最后一位数字，余数运算符 % 是你的 friend :
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) (n^2)，这使得基数排序比插入排序慢)。 Dynamic arrays通常采用更高效的 geometric expansion 来实现.
关于java - 我坚持以递归方式实现基数排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41322457/