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

回答

相關問題