java - 我不知道如何通过递归合并来阻止 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;