java - 我的快速排序算法中的 Stackoverflow 错误
问题描述
由于递归期间的堆栈溢出错误,我已经在这段代码上工作了几天,但没有运气。
问题表明我们的主元始终是第 0 个元素,通过递归,我们可以通过交换或创建新数组并将它们复制到原始数组中来对数组进行排序。我选择创建 2 个数组,因为它更容易理解,但是一旦我到达递归步骤,我就会得到这个错误。
我跟踪了算法并意识到枢轴元素总是被放置在较低的数组中,这可能是问题所在。
enter code here
public static void main(String[] args) {
int[] arr = new int[] { 12, 7, 5, 8, 4, 6, 11, 15 };
quicksort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
private static int[] quicksort(int[] arr, int middle) {
// Base case
if (arr.length == 1) {
return arr;
}
int[] upper = new int[arr.length];
int[] lower = new int[arr.length];
int upperIndex = 0, lowerIndex = 0;
// Put the elements into their respective pivots
for (int i = 0; i < arr.length; i++) {
if (arr[i] <= middle) {
lower[lowerIndex++] = arr[i];
} else {
upper[upperIndex++] = arr[i];
}
}
// Recurse, and sort the pivots
lower = quicksort(lower, lower[0]);
upper = quicksort(upper, upper[0]);
// Combine lower, middle, and upper back into one array
System.arraycopy(lower, 0, arr, 0, lowerIndex);
arr[lowerIndex + 1] = middle;
System.arraycopy(upper, 0, arr, lowerIndex + 2, upperIndex);
return arr;
}
结果应该是按升序排序的数组。
解决方案
正如 Quimby 的回答中提到的,lower 和upper 都设置为arr.length 的大小。代码需要使用第三个参数表示实际长度,如
quicksort(lower, lower[0], lowerIndex);
quicksort(upper, upper[0], upperIndex);
由于中间将在较低的位置结束,如果数据已经排序,那么在每个递归级别,所有数据都以较低的位置结束,零元素在上部,导致无限递归,仅由堆栈溢出停止。
由于您使用单独的数组进行快速排序,因此您可能需要考虑 3 路分区:
public static void quicksort(int[] arr, int pivot, int size) {
// Base case
if (size < 2) {
return;
}
int[] upper = new int[size];
int[] middle = new int[size];
int[] lower = new int[size];
int upperIndex = 0, middleIndex = 0, lowerIndex = 0;
// Put the elements into their respective arrays
for (int i = 0; i < size; i++) {
if (arr[i] < pivot) {
lower[lowerIndex++] = arr[i];
} else if (arr[i] == pivot){
middle[middleIndex++] = arr[i];
} else {
upper[upperIndex++] = arr[i];
}
}
// sort lower and upper
quicksort(lower, lower[0], lowerIndex);
quicksort(upper, upper[0], upperIndex);
// Combine lower, middle, and upper back into one array
System.arraycopy(lower, 0, arr, 0, lowerIndex);
System.arraycopy(middle, 0, arr, lowerIndex, middleIndex);
System.arraycopy(upper, 0, arr, lowerIndex+middleIndex, upperIndex);
}