我在Java中有一个简单的合并排序函数,该函数用于长度大于3的列表抛出StackOverFlow异常,
我每次都传递带有偏移量的数组对象以产生堆栈存储,但是它抛出stackOverFlow异常!
 问题出在哪里 ??

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
    ...

08-26 10:19