合并排序中出现堆栈溢出错误不知道为什么。
//BAD CODE BAD CODE
public static void main(String[] args) {
int[] S = {3,4,6,2,5,3,7};
mergesort(S, 1, 5);
System.out.println(S);
}
public static void mergesort(int[] S, int left, int right){
if (right <= 1) { return; }
int mid = (right + left) / 2;
mergesort (S, left, mid);
mergesort (S, mid+1, right);
merge(S, left, mid, right);
}
public static void merge(int[] S, int left, int mid, int right){
int i, j;
int[] aux = new int[S.length];
for (i = mid+1; i > left; i--) {aux[i-1] = S[i-1];}
for (j = mid; j < right; j++) {aux[right+mid-j] = S[j+1];}
for (int k = left; k <= right; k++){
if (aux[j] < aux[i]) {
S[k] = aux[j--];
} else{
S[k] = aux[i++];
}
}
}
//END OF BAD CODE
更新
谢谢你的快速反应,我让它工作,并提出了一些修改建议。复制粘贴,试试看:
//GOOD CODE
package longest_sequence_proj;
import java.util.*;
public class MergeTest {
/**
* @param args
*/
public static void main(String[] args) {
int[] S = {3,4,6,2,5,3,7};
mergesort(S, 0, 6);
System.out.println(Arrays.toString(S));
}
public static void mergesort(int[] S, int left, int right){
if (right <= left) { return; }
int mid = (right + left) / 2;
mergesort (S, left, mid);
mergesort (S, mid+1, right);
merge(S, left, mid, right);
}
public static void merge(int[] S, int left, int mid, int right){
int i, j;
int[] aux = new int[S.length];
for (i = mid+1; i > left; i--) {aux[i-1] = S[i-1];}
for (j = mid; j < right; j++) {aux[right+mid-j] = S[j+1];}
for (int k = left; k <= right; k++){
if (aux[j] < aux[i]) {
S[k] = aux[j--];
} else{
S[k] = aux[i++];
}
}
}
}
最佳答案
你的停止条款错了:
if (right <= 1) { return; }
当使用的部分数组的大小小于1时,实际上需要停止,因此您可能要查找:
if (right - left <= 1) { return; }
作为旁注:
System.out.println(S);
我想这不是你想要的(它不打印数组,而是对象的标识符…)
要打印数组,请使用:
System.out.println(Arrays.toString(S));