我如何解决这个StackOverflowError？

Question

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

只是想澄清一下：中=长度;

要初始化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];
   }

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

我没有得到任何语法错误。我在控制台窗口中看到的是：“线程中的异常”java.lang.StackOverFlow Error”。

完整递归方法如下所示：

 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));
    }

这是另一个没有除法、模或等于运算的方法

    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);
    }