我正在使用2D数组作为赋值进行bucket排序。BucketSort类中的最后一个方法是递归的。对于每个递归调用，我都会将用于确定基本情况的变量除以10来递减。我需要一双新的眼睛来看看我看不见的东西。我的代码如下：
import java.util.Arrays;
import java.util.Random;
public class BucketSort {
//Random rand = new Random();
//int length = 3 + rand.nextInt(10);
int[] array = {97, 100, 3};
int[][] buckets = new int[10][array.length - 1];
int col = 0;
int row = 0;
boolean occupied = false;
int max = 0;
int maxDigits = 1;
public BucketSort() { // constructor
for (int i = 0; i < array.length; i++) { // for each array element
//array[i] = rand.nextInt(1000);
System.out.print(array[i] + " ");
if (array[i] > max) // if current array element is greater than max
max = array[i]; // set the new max
System.out.println("nMax is: " + max);
}
// get the number of digits in the largest number (max) in the array
int largest = max; // largest is a temp var initialized to the value of max. I'm using it in calculations because I don't wanna destroy max
while (largest / 10 > 0) { // the largest number in the array is more than one digit
maxDigits++; // add 1 to maxDigits
largest /= 10; // divide largest by 10
System.out.println("maxdigits is: " + maxDigits);
System.out.println("Largest is: " + largest);
}
}
public void distribPass() {
// distribution pass
for (int i = 0; i < array.length; i++) { // for each array element
row = array[i] % 10; // get the ones place
if (buckets[row][col] == 0) { // if bucket is not occupied
buckets[row][col] = array[i]; // store the array element in bucket
}
else {
occupied = true; // bucket is occupied
while (occupied && (col < array.length - 1)) { // bucket is occupied
col++; // move to the next column
if (buckets[row][col] == 0 ){ // the bucket in the new column is not occupied
buckets[row][col] = array[i]; // store the array element in the bucket
occupied = false; // set occupied to false
} // end if
} // end while
} // end else
} // end for
for (row = 0; row < buckets.length; row++) { // for each row in buckets
//System.out.println("row: " + row + "n");
System.out.println();
for (col = 0; col < buckets[row].length; col++) { // for each column in current row
System.out.print(buckets[row][col] + "t"); // print contents of the current bucket
}
}
} // end distribPass
public void gatherPass() {
int index = 0; // reset the array index to 0
System.out.println("Gathering Pass");
for (row = 0; row < buckets.length; row++) { // for each row in buckets
for (col = 0; col < buckets[row].length; col++) { // for each column of current row
if (buckets[row][col] != 0) { // there's a number in the current bucket
array[index] = buckets[row][col]; // copy the number from the bucket back into the array
System.out.println(array[index]);
index++; // move to the next position in the array
buckets[row][col] = 0; // reset current bucket to 0
}
}
}
}
public void sort() {
// tens digit, hundreds digit, etc.
row = 0;
col = 0;
System.out.println("Testing the sort method");
for (int i = 0; i < array.length; i++) { // for each array element
for (int digit = 2; digit <= maxDigits; digit++) { // for each digit of the current array element
row = getPlace(array[i], digit - 1); // get the proper bucket row to store the current array element in
System.out.println("Digit is: " + digit + " Place is " + row);
}
// do another distribution pass
if (buckets[row][col] == 0) { // current bucket is not occupied
buckets[row][col] = array[i]; // store the current array item in the current bucket
}
else { // current bucket is occupied
occupied = true; // set occupied to true
while (occupied && (col < array.length - 1)) {
col++; // move to the next column
if (buckets[row][col] == 0) { // if current bucket is not occupied
buckets[row][col] = array[i]; // store the current array item in the current bucket
occupied = false; // set occupied to false
}
}
}
}
gatherPass();
}
public int getPlace(int num, int exp) {
int intPlace;
double doublePlace;
if (num >= Math.pow(10, exp) && num < Math.pow(10, exp + 1)) { // for example, to check if a number is between 10 and 100
// base case
doublePlace = num / Math.pow(10, exp);
intPlace = (int) doublePlace;
return intPlace;
}
else
return getPlace(num / 10, exp); // recursive call
}
}
public class BucketSortTest {
public static void main(String[] args) {
BucketSort screwup = new BucketSort();
screwup.distribPass();
screwup.gatherPass();
screwup.sort();
}
}
您的程序有以下方法getPlace
public int getPlace(int num, int exp) {
int intPlace;
double doublePlace;
if (num >= Math.pow(10, exp) && num < Math.pow(10, exp + 1)) { // for example, to check if a number is between 10 and 100
// base case
doublePlace = num / Math.pow(10, exp);
intPlace = (int) doublePlace;
return intPlace;
}
else
return getPlace(num / 10, exp); // recursive call
}
我看了你的代码，当用num value 3和exp value 1调用它时，它在一次调用中很好，但在getPlace的第二次调用中，num变成0，exp变成1，这导致了无限递归，永远不会到达基条件，并导致stackoverflow exception。
因此，您必须在基本情况下处理此情况才能终止infinite recursion。