遇到了合并排序(mergeSort)实现的问题。

huangapple go评论92阅读模式
英文:

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 &quot;main&quot; java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1&quot;

Here's my implementation of mergeSort:

public static void mergeSort(int[] arr, int n) {
if (n &lt; 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 &lt; mid_index; i++) {
left[i] = arr[i];
}
for (int i = mid_index; i &lt; 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 &lt; left_length &amp;&amp; k &lt; right_length) {
if (left[i] &lt; right[j]) {
arr[k] = left[i];
k++;
i++;
} else {
arr[k] = right[j];
k++;
j++;
}
}
while (j &lt; left_length) {
arr[k] = left[i];
k++;
i++;
}
while (i &lt; 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&lt;left_length &amp;&amp; j &lt; right_length){
if(left[i] &lt; right[j]){
arr[k] = left[i];
k++;
i++;
}
else{
arr[k] = right[j];
k++;
j++;
}
}
while(i&lt;left_length){
arr[k] = left[i];
k++;
i++;
}
while(j&lt;right_length){
arr[k] = right[j];
k++;
j++;
}
} 

答案2

得分: 1

所有 merge 方法中的三个 while 循环使用了错误的索引变量。第一个循环 while (j &lt; left_length &amp;&amp; k &lt; right_length) { 应该更改为

while (i &lt; left_length &amp;&amp; j &lt; right_length) {

第二个循环 while (j &lt; left_length) { 应该更改为

while (i &lt; left_length) {

最后,最后一个循环 while (i &lt; right_length) { 应该更改为

while (j &lt; right_length) {
英文:

All 3 while loop in the merge method use the wrong index variables. The first loop while (j &lt; left_length &amp;&amp; k &lt; right_length) { should be

    while (i &lt; left_length &amp;&amp; j &lt; right_length) {

The second loop while (j &lt; left_length) { should be

    while (i &lt; left_length) {

Finally, the last loop while (i &lt; right_length) { should be

    while (j &lt; right_length) {

huangapple
  • 本文由 发表于 2020年8月19日 23:16:27
  • 转载请务必保留本文链接:https://go.coder-hub.com/63490144.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定