MergeSort实现给了StackOverflow

我一直在试图实现一个MergeSort，将数组分成三部分而不是两部分。我似乎在某处获得StackOverflow异常。有人可以帮我找到它吗？（这些SO正在54,58,59行上报告）MergeSort实现给了StackOverflow

import java.util。 ; import java.io.;

类MergeSortQuestion {

// merges sorted subarrays A[start...firstThird], A[firstThird+1,secondThird], and A[secondThird+1,stop] 
public static void mergeThreeWay(int A[], int start, int firstThird, int secondThird, int stop) 
{ 

    int indexLeft = start; 
    int indexFirstThird = firstThird+1; 
    int indexSecondThird = secondThird+1; 
    int tmp1[] = new int[A.length]; 
    int tmpIndex = start; 
    while(tmpIndex <= firstThird){ 

     if (indexFirstThird < firstThird || (indexLeft <= firstThird && A[indexLeft] <= A[indexFirstThird])){ 

      tmp1[tmpIndex] = A[indexLeft]; 
      indexLeft++; 

     }else if(indexSecondThird < secondThird || (indexFirstThird <= secondThird && A[firstThird] <= A[indexSecondThird])){ 

      tmp1[tmpIndex] = A[indexFirstThird]; 
      indexFirstThird++; 

     }else{ 

      tmp1[tmpIndex] = A[indexSecondThird]; 
      indexSecondThird = indexSecondThird + 1; 

     } 

     tmpIndex++; 
    } 

    int i = 0; 

    for(int temp : tmp1){ 
     A[i] = temp; 
     i++; 
    } 



} 



// sorts A[start...stop] 
public static void mergeSortThreeWay(int A[], int start, int stop) { 

    if (start < stop){ 

     int firstThird = (start+stop)/3; 
     int secondThird = 2*(firstThird); 
     mergeSortThreeWay(A, start, firstThird); 
     mergeSortThreeWay(A, firstThird+1, secondThird); 
     mergeSortThreeWay(A, secondThird+1, stop); 
     mergeThreeWay(A, start, firstThird, secondThird, stop); 
    } 


} 


public static void main (String args[]) throws Exception { 

int myArray[] = {8,3,5,7,9,2,3,5,5,6}; 

mergeSortThreeWay(myArray,0,myArray.length-1); 

System.out.println("Sorted array is:\n"); 
for (int i=0;i<myArray.length;i++) { 
    System.out.println(myArray[i]+" "); 
} 
}

}

来源

2013-09-27 Joseph Szymborski

看起来像你的递归方法没有停止。做一些调试来找出原因。 –

在'mergeSortThreeWay'中，你可能想做一些事情来'开始'和'停止'。 – devnull

你firstThird和secondThird变量不从一个迭代到另一个在mergeSortThreeWay执行某一点发生变化值。在你的榜样，我得到了：似乎

start=4 stop=6 
firstThird=3 secondThird=6 
start=4 stop=6 
firstThird=3 secondThird=6 
// so java.lang.StackOverflowError

计算firstThird和secondThird公式不工作。尝试使用

firstThird = (stop-start)/3 + start; 
secondThird = 2*(stop-start)/3 + start;

来源

2013-09-27 06:54:24 aUserHimself

MergeSort实现给了StackOverflow

回答

相关问题