我有我的快速排序方法的基本情况，但我仍然得到堆栈溢出错误？

Question

我有一个快速排序类，它在较小的列表大小上工作，但即使我有一个基本情况，也会在较大的列表大小上不断收到错误。我有一个快速排序类，如下所示：

public class QuickSorter extends Sorter
{
  @Override
  public void sort(WordList toSort, Comparator<String> comp) throws NullPointerException{
    // TODO
      int front = 0;
      
      int back = toSort.length() -1;
      
      quickSortRec(toSort, comp, front, back);
      
  }

  private void quickSortRec(WordList list, Comparator<String> comp, int start, int end){
    // TODO
      if (start >= end) {
          return;
      }
    
      int pivotPoint = partition(list, comp, start, end);
         
      quickSortRec(list, comp, start, pivotPoint - 1);
     
      quickSortRec(list, comp, pivotPoint + 1, end);
     
      }
    
  
     
  
         
  

  private int partition(WordList list, Comparator<String> comp, int start, int end){
    // TODO
      String pivotSpot = list.get(end);
      int pivotIndex = start;
     
      for(int i = start; i < end; i++) {
          
          if(comp.compare(list.get(i), pivotSpot) < 0) {
              
              list.swap(i, pivotIndex); 
          }
      }
      
      list.swap(end, pivotIndex);
     
      return pivotIndex;
  
  
  }
}

我的代码在需要排序的较小列表上工作得很好，但在第36行得到了重复的StackOverflow异常

堆栈跟踪如下所示：

Exception in thread "main" java.lang.StackOverflowError
    at hw2.AlphabetComparator.compare(AlphabetComparator.java:1)
    at hw2.Sorter$CountingComparator.compare(Sorter.java:272)
    at hw2.QuickSorter.partition(QuickSorter.java:53)
    at hw2.QuickSorter.quickSortRec(QuickSorter.java:32)
    at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)
    at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)
    at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)
    at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)

AlphabetComparator：

int length = b.length(); // holds smallest length of both strings so I don't get an out of bounds exception with my for loop

      if (a.length() < b.length()) // default length will be String b's length if b is less than a or a and b are ==
      {
          length = a.length();
      }
      for (int i = 0; i < length; i++)
      {
          if (a.charAt(i) != b.charAt(i)) // if character at same index in both strings aren't equal
          {
              if (alphabet.isValid(a.charAt(i)) == true && alphabet.isValid(b.charAt(i)) == true) // if both characters are valid in the alphabet
              {
                  return alphabet.getPosition(a.charAt(i)) - alphabet.getPosition(b.charAt(i)); // return negative or positive
              }
          }
      }
      if (a.length() != b.length())
      {
          if (length == a.length())
          {
              return -1;
          } else
              return 1;
      }
      return 0;
  }
      ```

Answer 1

您正在使用递归进行排序，而堆栈并不是无限的。对于小的(足够的)数组，你的递归保持在限制之内。但是对于足够大的数组，它会将堆栈打乱。通常，无限循环情况下会发生堆栈溢出，但在您的情况下，可能是由于数组太宽而导致递归过深。

参考https://freecontent.manning.com/stack-safe-recursion-in-java/#:~:text=Default%20stack%20size%20varies%20between,case%20is%20recursive%20method%20calls。

你的下一个问题可能会在这里得到回答：How to increase the Java stack size?