我该如何解决这个 StackOverflowError？

Question

在我的 MergeSort 程序的这一部分，我递归地划分一个名为 "arr" 的未排序数组。为此，我创建了两个子数组 "leftArr" 和 "rightArr"，然后用 "arr" 的前半部分和 "leftArr" 的后半部分填充 "leftArr" 和 "rightArr" =38=]分别。之后我将使用递归来划分/排序 leftArr 和 rightArr.

只是想澄清一下：mid = arr.length;

为了初始化 rightArr，我执行以下操作：

 double halfLength = arr.length * 0.5; 
    if((!(halfLength < 0)) && (!(0 < halfLength))){
       // if right array is an even num, length of right array is mid
       rightArr = new int [mid];
   } else 
   {
       // else right arrays length is mid + 1
       rightArr = new int[mid + 1];
   }

当我这样做时，我没有收到任何错误：

if(arr.length % 2 == 0){
       // if right array is an even num, length of right array is mid
       rightArr = new int [mid];
   } else 
   {
       // else right arrays length is mid + 1
       rightArr = new int[mid + 1];
   }

但是我的项目不允许我使用取模运算符“%”和“==”运算符。

我没有收到任何语法错误。我在控制台 window 中看到的是： “线程异常 "main" java.lang.WhosebugError”。

完整的递归方法如下所示：

 public int[] mergeSort(int[] arr) {

   if (arr.length < 2){
       return arr;  // if array has only one element, its already sorted 
   }
   int mid = arr.length / 2;     // find midpoint of array 

   int leftArr[] = new int [mid];   // create left subarray of length mid 
   int rightArr[];                  // create right subarray 

   /* if(arr.length % 2 == 0){
       // if right array is an even num, length of right array is mid
       rightArr = new int [mid];
   } else 
   {
       // else right arrays length is mid + 1
       rightArr = new int[mid + 1];
   }*/
    double halfLength = arr.length * 0.5; 
    if((!(halfLength < 0)) && (!(0 < halfLength))){
       // if right array is an even num, length of right array is mid
       rightArr = new int [mid];
   } else 
   {
       // else right arrays length is mid + 1
       rightArr = new int[mid + 1];
   }

   // create a resultArr of size arr, to store the sorted array 
   int resultArr[] = new int [arr.length];

   int i = 0;
   // Copy first half of arr[] into leftArr[]
   while(i < mid){  
       leftArr[i] = arr[i];
        i = i + 1;
   }
   int j = mid;
   int indexOfRight = 0;
   // Copy second half of arr into rightArr 
   while(j < arr.length){
       rightArr[indexOfRight] = arr[j];
       indexOfRight = indexOfRight + 1; 
       j = j + 1;
   }

   // Recursively call mergeSort to sort leftArr and rightArr
   leftArr = mergeSort(leftArr);
   rightArr = mergeSort(rightArr);

   // merge leftArr and rightArr into a resultant Array, and then return the resultArr 
   return resultArr = merge(leftArr, rightArr);

}

这是我合并的方式：

public int[] merge(int[] a1, int[] a2) {
  // TO BE COMPLETED
   int lengthOfRes = a1.length + a2.length;
   int resArr[] = new int [lengthOfRes];    // create resultant array of size a1 + a2

   int a1Index = 0;
   int a2Index = 0;
   int resIndex = 0;

   while((a1Index < a1.length) || (a2Index < a2.length))
   {
       if((a1Index < a1.length) && (a2Index < a2.length)){
           // if a1's element is <= a2's element, then insert a1's elem in resArr
           if(a1[a1Index] < a2[a2Index]){
               resArr[resIndex] = a1[a1Index];
               a1Index = a1Index + 1;
                resIndex = resIndex + 1;
           } else
             // else, insert a2's elem in resArr   
           {
               resArr[resIndex] = a2[a2Index];
               a2Index = a2Index + 1;
               resIndex = resIndex + 1;
           }
       }
       // Here, if there are any of a1's elements left over, then insert them into resArr
       else if(a1Index < a1.length){
            resArr[resIndex] = a1[a1Index];
            a1Index = a1Index + 1;
            resIndex = resIndex + 1;
       }
        // Here, if there are any of a2's elements left over, then insert them into resArr
       else
       {
           resArr[resIndex] = a2[a2Index];
            a2Index = a2Index + 1;
            resIndex = resIndex + 1;
       }
   }
   return resArr;   // return the resulting array

}

我该如何解决这个问题？

提前致谢！

Answer 1

这个算法没有对任何东西进行排序。您只是递归地破坏数组，但没有任何比较。

这个网站对合并排序算法有很好的解释：http://algs4.cs.princeton.edu/22mergesort/ http://algs4.cs.princeton.edu/22mergesort/Merge.java.html

值得研究

问题是这段代码

double halfLength = arr.length * 0.5; 
if((!(halfLength < 0)) && (!(0 < halfLength)))

不判断arr.length是否为偶数。试试这个：

    public boolean isEven(int number) {
      // return (number - (number / 2) * 2) == 0;
      return (!((number - (number / 2) * 2) > 0)) && (!((number - (number / 2) * 2) < 0));
    }

这里是另一种不用除法的方法，mod或者等于运算

    public boolean isEven(int number) {
        number = number < 0 ? number * -1 : number;
        if (number < 1) {
            return true;
        }
        if (number > 0 && number < 2) {
            return false;
        }

        return isEven(number - 2);
    }

我该如何解决这个 StackOverflowError？

How do I solve this StackOverflowError?

java

stack-overflow

arrays

recursion

mergesort