合并排序抛出 StackOverflowError
Merge sort throws StackOverflowError
我在 Java 中有一个简单的合并排序函数,对于长度大于 3 的列表抛出 Whosebug 异常,
我每次都传递数组对象及其偏移量以生成堆栈存储,但它抛出 Whosebug 异常!
哪里出了问题??
public class DiviedAndConquer {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
DiviedAndConquer app=new DiviedAndConquer();
Integer[] arr={3,5,1,8};
app.mergSort(arr,0,arr.length-1);
for(int i = 0;i<=arr.length-1;i++)
System.out.print(arr[i]+" ");
}
public void mergSort(Integer[] arr,int l,int h){
if(h-l>0){
int m=(h-l+1)/2;
//int l=arr.length-h;
mergSort(arr,l,m);
mergSort(arr,m+1,h);
merg(arr,l,h);
}
}
public void merg(Integer[] arr,int l,int h){
Integer[] tarr=new Integer[h-l+1];
for(int p=0;p<=h;p++)
tarr[p]=0;
int m=(h-l)/2;
int j=m+1;
int k=0;
int i=l;
while(i<=m && j<=h){
if(arr[j]<arr[i]){
tarr[k]=arr[j];
j++;
}
else{
tarr[k]=arr[i];
i++;
}
k++;
}
if(i<=m){
for(;i<=m;i++){
tarr[k]=arr[i];
k++;
}
k--;
}
else if(j<=h){
for(;j<=m;j++){
tarr[k]=arr[j];
k++;
}
k--;
}
for(int z=0;z<=k;z++){
arr[l+z]=tarr[z];
}
}}
您计算的中间索引不正确。
int m=(h-l+1)/2;
应该是
int m=(h+l)/2;
这可能就是你的递归永不结束的原因。
您的 merg
方法也有一些错误:
改变
public void merg(Integer[] arr,int l,int h) {
Integer[] tarr = new Integer[h-l+1];
for(int p=0;p<=h;p++)
tarr[p]=0;
int m=(h-l)/2;
...
到
public void merg(Integer[] arr,int l,int h){
Integer[] tarr = new Integer[h-l+1];
for(int p=0;p<tarr.length;p++) // corrected the range of the loop
tarr[p]=0;
int m=(h+l)/2; // the same fix of m calculation as before
...
我在 Java 中有一个简单的合并排序函数,对于长度大于 3 的列表抛出 Whosebug 异常, 我每次都传递数组对象及其偏移量以生成堆栈存储,但它抛出 Whosebug 异常! 哪里出了问题??
public class DiviedAndConquer {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
DiviedAndConquer app=new DiviedAndConquer();
Integer[] arr={3,5,1,8};
app.mergSort(arr,0,arr.length-1);
for(int i = 0;i<=arr.length-1;i++)
System.out.print(arr[i]+" ");
}
public void mergSort(Integer[] arr,int l,int h){
if(h-l>0){
int m=(h-l+1)/2;
//int l=arr.length-h;
mergSort(arr,l,m);
mergSort(arr,m+1,h);
merg(arr,l,h);
}
}
public void merg(Integer[] arr,int l,int h){
Integer[] tarr=new Integer[h-l+1];
for(int p=0;p<=h;p++)
tarr[p]=0;
int m=(h-l)/2;
int j=m+1;
int k=0;
int i=l;
while(i<=m && j<=h){
if(arr[j]<arr[i]){
tarr[k]=arr[j];
j++;
}
else{
tarr[k]=arr[i];
i++;
}
k++;
}
if(i<=m){
for(;i<=m;i++){
tarr[k]=arr[i];
k++;
}
k--;
}
else if(j<=h){
for(;j<=m;j++){
tarr[k]=arr[j];
k++;
}
k--;
}
for(int z=0;z<=k;z++){
arr[l+z]=tarr[z];
}
}}
您计算的中间索引不正确。
int m=(h-l+1)/2;
应该是
int m=(h+l)/2;
这可能就是你的递归永不结束的原因。
您的 merg
方法也有一些错误:
改变
public void merg(Integer[] arr,int l,int h) {
Integer[] tarr = new Integer[h-l+1];
for(int p=0;p<=h;p++)
tarr[p]=0;
int m=(h-l)/2;
...
到
public void merg(Integer[] arr,int l,int h){
Integer[] tarr = new Integer[h-l+1];
for(int p=0;p<tarr.length;p++) // corrected the range of the loop
tarr[p]=0;
int m=(h+l)/2; // the same fix of m calculation as before
...