英文:
Having a problem with my mergeSort implementation
问题
我对mergeSort
的实现出现了越界错误,但我无法找出原因。这是确切的错误信息:Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
。
这是我的mergeSort
实现:
public static void mergeSort(int[] arr, int n) {
if (n < 2) {
return;
}
int mid_index = n / 2;
int[] left = new int[mid_index];
int[] right = new int[n - mid_index];
for (int i = 0; i < mid_index; i++) {
left[i] = arr[i];
}
for (int i = mid_index; i < n; i++) {
right[i - mid_index] = arr[i];
}
mergeSort(left, mid_index);
mergeSort(right, n - mid_index);
merge(arr, left, right, mid_index, n - mid_index);
}
public static void merge(int[] arr, int[] left, int[] right, int left_length, int right_length) {
int i = 0;
int j = 0;
int k = 0;
while (j < left_length && k < right_length) {
if (left[i] < right[j]) {
arr[k] = left[i];
k++;
i++;
} else {
arr[k] = right[j];
k++;
j++;
}
}
while (j < left_length) {
arr[k] = left[i];
k++;
i++;
}
while (i < right_length) {
arr[k] = right[j];
k++;
j++;
}
}
英文:
I'm getting an out of bounds error for my implementation of mergeSort
, and I can't figure out why. This is the exact error message: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1"
Here's my implementation of mergeSort
:
public static void mergeSort(int[] arr, int n) {
if (n < 2) {
return;
}
int mid_index = n / 2;
int[] left = new int[mid_index];
int[] right = new int[n - mid_index];
for (int i = 0; i < mid_index; i++) {
left[i] = arr[i];
}
for (int i = mid_index; i < n; i++) {
right[i - mid_index] = arr[i];
}
mergeSort(left, mid_index);
mergeSort(right, n - mid_index);
merge(arr, left, right, mid_index, n - mid_index);
}
public static void merge(int[] arr, int[] left, int[] right, int left_length, int right_length) {
int i = 0;
int j = 0;
int k = 0;
while (j < left_length && k < right_length) {
if (left[i] < right[j]) {
arr[k] = left[i];
k++;
i++;
} else {
arr[k] = right[j];
k++;
j++;
}
}
while (j < left_length) {
arr[k] = left[i];
k++;
i++;
}
while (i < right_length) {
arr[k] = right[j];
k++;
j++;
}
}
答案1
得分: 2
问题出在 merge
方法中。你在索引方面犯了一些错误。我在下面的代码中对它们进行了修正。
public static void merge(int[] arr, int[] left, int[] right, int left_length, int right_length) {
int i = 0; // left
int j = 0; // right
int k = 0;
while (i < left_length && j < right_length) {
if (left[i] < right[j]) {
arr[k] = left[i];
k++;
i++;
} else {
arr[k] = right[j];
k++;
j++;
}
}
while (i < left_length) {
arr[k] = left[i];
k++;
i++;
}
while (j < right_length) {
arr[k] = right[j];
k++;
j++;
}
}
英文:
The problem was in merge
method. You make some mistakes with indexes. I corrected them in code below
public static void merge(int[] arr, int[] left, int[] right, int left_length, int right_length){
int i = 0;//left
int j = 0; //right
int k = 0;
while(i<left_length && j < right_length){
if(left[i] < right[j]){
arr[k] = left[i];
k++;
i++;
}
else{
arr[k] = right[j];
k++;
j++;
}
}
while(i<left_length){
arr[k] = left[i];
k++;
i++;
}
while(j<right_length){
arr[k] = right[j];
k++;
j++;
}
}
答案2
得分: 1
所有 merge
方法中的三个 while
循环使用了错误的索引变量。第一个循环 while (j < left_length && k < right_length) {
应该更改为
while (i < left_length && j < right_length) {
第二个循环 while (j < left_length) {
应该更改为
while (i < left_length) {
最后,最后一个循环 while (i < right_length) {
应该更改为
while (j < right_length) {
英文:
All 3 while
loop in the merge
method use the wrong index variables. The first loop while (j < left_length && k < right_length) {
should be
while (i < left_length && j < right_length) {
The second loop while (j < left_length) {
should be
while (i < left_length) {
Finally, the last loop while (i < right_length) {
should be
while (j < right_length) {
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论