java.lang.StackOverflowError 在合并排序中

Question

public class MergeSort
{
public static double[] MergeSort(double[] a){
    if(a.length < 1){
        return new double[0];
    }
    else if(a.length == 1){
        return a;
    }
    else{
        double[] l = Teiler(a, false);
        double[] r = Teiler(a, true);
        return Fueger(MergeSort(l), MergeSort(r));
    }
}
...
}

public static double[] Fueger(double[] a, double[] b): returns 包含 a 和 b 中所有数字的双精度数组，顺序正确。

public static double[] Teiler(double[] a, boolean l): returns一半的元素（前半部分，如果l为假，后半部分，如果l为真）

Fueger 和 Teiler 工作得很好，但 MergeSort 总是给出 java.lang.WhosebugError，即使递归应该在数组为空或只包含一个元素时立即终止。有什么问题？

感谢您的帮助

这是 Fueger：

public static double[] Fueger(double[] a, double[] b){
    double[] hilf = new double[a.length + b.length];
    int i = 0;
    while((a.length != 0) && (b.length != 0)){
        if(a[0] < b[0]){
            hilf[i] = a[0];
            a = Weg(a);
        }
        else{
            hilf[i] = b[0];
            b = Weg(b);
        }
        i++;
    }
    if(a.length != 0){
        for(double x : a){
            hilf[i] = x;
            a = Weg(a);
            i++;
        }
    }
    if(b.length != 0){
        for(double x : b){
            hilf[i] = x;
            b = Weg(b);
            i++;
        }
    }
    return hilf;
}

泰勒：

public static double[] Teiler(double[] a, boolean r){
    double[] hilf;
    int x = 0;
    if(r == false){
        hilf = new double[(int) a.length / 2];
        for(int i = 0; i < a.length / 2; i++){
            hilf[x] = a[i];
            i ++;
        }
    }
    else{
        hilf = new double[(int) (a.length / 2) + 1];
        for(int i = a.length / 2; i < a.length; i++){
            hilf[x] = a[i];
            i ++;
        } 
    }
    return hilf;
}

Answer 1

问题出在Teiler方法中。考虑一个长度为 2 的列表，else 分支创建一个长度为 2 而不是 1 的列表（即使它只填充第一个元素）。因此，将递归陷入无限循环。您可以通过仅在长度为奇数时添加最后一个元素来轻松解决此问题：

public static double[] Teiler(double[] a, boolean r){
   double[] hilf;
   int x = 0;
   if(r == false){
       hilf = new double[(int) a.length / 2];
       for(int i = 0; i < a.length / 2; i++){
           hilf[x] = a[i];
           i ++;
       }
   } else{
       hilf = new double[(int) (a.length / 2) + (a.length % 2)];
       for(int i = a.length / 2; i < a.length; i++){
           hilf[x] = a[i];
           i ++;
       } 
   }
   return hilf;
}

java.lang.StackOverflowError 在合并排序中

java.lang.StackOverflowError in MergeSort

java

stack-overflow

sorting

mergesort