java - 随机快速排序 IndexOutOfBounds 异常
问题描述
这是我提出的 QuickSort Randomized,但它不断抛出 IndexOutOfBounds 异常。我可以帮忙吗?谢谢!
import java.util.Random;
public class QuickSort {
void quickSort(int[] A, int start, int end) { // Initially: start = 0, end = n-1
while (start < end) {
int iOfPartition = randomisedPartition(A, start, end);
if (iOfPartition - start < end - iOfPartition) {
quickSort(A, start, iOfPartition - 1);
start = iOfPartition + 1;
} else {
quickSort(A, iOfPartition + 1, end);
end = iOfPartition - 1;
}
}
}
int randomisedPartition(int[] A, int start, int end) {
Random rng = new Random();
int randomNum = rng.nextInt(end + 1 - start) + start;
swap(A, A[randomNum], A[start]);
return hoarePartition(A, start, end);
}
int hoarePartition(int[] A, int start, int end) {
int pivot = A[start];
int i = start;
int j = end;
while (i < j) {
while (A[i] <= pivot && i < end) i++;
while (A[j] > pivot && j > start) j--;
if (i < j) swap(A, A[i], A[j]);
}
swap(A, A[start], A[j]);
return j;
}
void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
我不断收到 arrayindexoutofbounds 错误。
解决方案
我赞同上面评论的观点,你应该学会使用调试器或打印语句来尝试拼凑正在发生的事情。
尽管如此,我还是忍不住去调查。
在调用交换中查看您在此处执行的操作。您正在使用 A[randomNum] 获取位于 randomNum 位置的值
swap(A, A[randomNum], A[start]); // incorrectly indexing here
但是在交换内部,您正在重复该过程,并在不一定存在的 A[A[randomNum]] 处获取值。
int temp = A[i]; // indexing here again
所以你的问题是你错误地索引了两次。您应该只在交换函数中使用 [],而不是在 randomisedPartition 函数中。randomisedPartition 应该发送交换索引,而不是索引值。
我是怎么想出来的?我尝试使用非常简单的数据进行通话
int data[] = {5,3,4};
new Example().quickSort(data, 0, 2);
并得到一个索引超出范围 5 错误。这就是你调试的方式。
推荐阅读
- laravel - 简单的 Laravel 项目抛出未定义的变量错误
- javascript - 事件循环和承诺
- kotlin - TornadoFX _ Kotlin _ IntelliJ IDEA:由于我在项目中使用 openJDK 8,我怎么可能得到“未解决的参考:javafx”?
- excel - 使用 VBA 排序 - 多级排序
- excel - 在单独的工作簿中设置一个值,并恢复为旧值
- stripe-payments - 如何使用 Stripe PaymentIntent 处理产品可用性/税收/运费?
- office365 - 如何对未在 Microsoft word 365 中加载的 VSTO 插件进行故障排除?
- string - 逐行读取文件 ARDUINO
- python - 我可以用更少的属性进行预测吗?
- javascript - 数组可以很好地打印对象值,但试图访问其打印的值未定义