我不知道如何通過遞歸合併來阻止Stackoverflow錯誤

Question

所以我一直在研究這段代碼很長一段時間，我感覺我差不多完成了。但是，我一直反覆出現堆棧溢出錯誤，似乎無法修復它。我希望能夠在標準代碼之後打印出遞歸代碼，但我似乎在mergesort方法中有時會出現錯誤。即使在查詢遞歸和堆棧溢出後，我無法弄清楚是什麼導致錯誤。我需要幫助。這是一個遞歸合併方法。

import java.util.*; 
import java.lang.*; 
import java.io.*; 

public class merge_recursive { 

    public void mergeSort(ArrayList <Comparable> a, int first, int last){ 
     int mid; 
     int temp; 

     if (first == last){ 
     } 
     else{ 
      if (first +1 == last){ 
       //list of 2 values, swap if needed 
       if(a.get(first).compareTo(a.get(last)) > 0){ 
        swap(a, first, last); 
       } 
      } 
      else { 
       //general case 
       mid = (first + last)/2; 
       mergeSort(a, first, mid); 
       mergeSort(a, mid +1, last); 
       merge(a, first, mid, last); 
      } 
     } 
    } 

    private void merge(ArrayList <Comparable> a, int first, int mid, int last) 
    { 
     int aPtr = first; 
     int bPtr = mid + 1; 
     int cPtr = first; 
     int total = last - first + 1; 
     int loop; 
     boolean doneA = false; 
     boolean doneB = false; 
     ArrayList <Comparable> c = new ArrayList <Comparable>(a); 

     for (loop = 1; loop <= total; loop++){ 
      if (doneA){ 
       c.set(cPtr, a.get(bPtr)); 
       bPtr++; 
      } else if (doneB){ 
       c.set(cPtr, a.get(aPtr)); 
       aPtr++; 
      } else if (a.get(aPtr).compareTo(a.get(bPtr)) < 0){ 
       // ok to compare, valid data in each sublist 
       c.set(cPtr, a.get(aPtr)); 
       aPtr++; 
      } else { 
       c.set(cPtr, a.get(bPtr)); 
       bPtr++; 
      } 
      cPtr++; 
      if (aPtr > mid){ 
       doneA = true; 
      } 
      if (bPtr > last){ 
       doneB = true; 
      } 
     } 
     ArrayList<Comparable> d = new ArrayList <Comparable>();         
     for (int i = 0; i < c.size()/2; i++){ 
      d.add(i,c.get(c.size()-1)); 
     } 
     System.out.println("Sorted list: " + d); 
    } 

    public ArrayList <Comparable> fillArray(){//sortstep 
     Scanner console = new Scanner(System.in); 

     System.out.println(); 
     System.out.print("How many numbers do you wish to generate? "); 
     int numInts = console.nextInt(); 

     ArrayList <Comparable> temp = new ArrayList<Comparable>(); 

     System.out.print("Largest integer to generate? "); 
     int largestInt = console.nextInt(); 

     Random randGen = new Random(); 

     for (int loop = 0; loop < numInts; loop++){ 
      temp.add(randGen.nextInt(largestInt) + 1); 
     } 
     return temp; 
    } 

    public void swap(ArrayList <Comparable> list, int a, int b){ 
     Comparable c = list.get(a); 
     list.set(a, list.get(b)); 
     list.set(b, c); 
    } 
} 

// End of Recursive merge // 

import java.util.ArrayList; 

public class merge_recursive_Driver { 
    public static void main(String[] args){ 
     merge_recursive s = new merge_recursive(); 

     ArrayList standard = s.fillArray(); 
     System.out.println("Standard: " + standard); 
     int first = (int) standard.get(0); 
     int last = (int) standard.get(standard.size() -1); 
     s.mergeSort(standard, first, last); 
    } 
} 

// End of Driver // 

輸出：

How many numbers do you wish to generate? 100 
Largest integer to generate? 100 
Standard: [81, 4, 23, 2, 88, 70, 64, 74, 1, 16, 16, 11, 24, 88, 28, 89, 
52, 5, 86, 73, 89, 95, 69, 15, 58, 34, 80, 63, 96, 11, 63, 92, 95, 71, 
87, 76, 94, 87, 27, 23, 69, 47, 87, 55, 14, 90, 9, 61, 13, 39, 56, 55, 
19, 20, 85, 93, 6, 8, 90, 9, 26, 99, 41, 11, 60, 22, 30, 46, 52, 20, 1, 
23, 2, 37, 10, 19, 89, 16, 43, 12, 47, 52, 28, 13, 10, 41, 46, 91, 49, 
62, 66, 17, 87, 69, 47, 58, 45, 38, 83, 31] 
Exception in thread "main" java.lang.StackOverflowError 
    at merge_recursive.mergeSort(merge_recursive.java:11) 
    at merge_recursive.mergeSort(merge_recursive.java:24) 
    at merge_recursive.mergeSort(merge_recursive.java:24) 
    at merge_recursive.mergeSort(merge_recursive.java:24) 
    at merge_recursive.mergeSort(merge_recursive.java:24) 
    at merge_recursive.mergeSort(merge_recursive.java:24) 

等等。

Answer 1

「first」和「last」是數組索引，而不是數組值。替換：

int first = (int) standard.get(0); 
    int last = (int) standard.get(standard.size() -1); 

與

int first = 0; 
    int last = standard.size() -1;