Java程序出现StackOverflowError且无法终止，请求代码修复帮助

核心问题分析 #

1. 快速排序栈溢出：当前快排选取最右侧元素作为基准值（pivot），当数组已经有序（比如插入排序后的数组），快排会退化为O(n²)时间复杂度，递归深度达到n级别。对于n=200000，Java默认栈深度远不足以支撑这么多层递归，直接抛出StackOverflowError。

2. 插入排序效率极低：插入排序的时间复杂度是O(n²)，当n达到200000时，单次排序的时间会非常长，导致程序几乎无法终止。而且测试循环中从n=1到200000每次都执行插入排序，完全不具备可行性。

3. 测试逻辑错误：当前代码中，插入排序后数组已经有序，再用这个有序数组测试快排，直接触发快排的最坏情况；且两种排序应该测试相同的原始随机数组，而不是排序后的数组，否则测试结果没有对比意义。

修复方案 #

1. 优化快速排序 #

• 随机选取基准值，避免有序数组的最坏情况
• 递归到小数据量（比如数组长度≤10）时切换为插入排序，减少递归层数
• 对分区后的子数组优先处理较小的那个，进一步降低栈深度

2. 调整测试逻辑 #

• 限制插入排序的测试范围（比如n≤1000），因为大数据量下插入排序性能极差，无测试价值
• 每次测试时，为两种排序生成相同的原始随机数组副本，保证测试的公平性

修复后的代码 #

import java.util.Random;
import java.io.PrintWriter;
import java.io.IOException;

public class SortingAlgorithms {
   
   public static void insertionSort(int[] arr) {
      int n = arr.length;
      for (int j = 1; j < n; j++) {
         int key = arr[j];
         int i = j - 1;
         while (i >= 0 && arr[i] > key) {
            arr[i + 1] = arr[i];
            i--;
         }
         arr[i + 1] = key;
      }
   }
   
   public static void quickSort(int[] arr, int left, int right) {
      // 小数据量切换为插入排序，减少递归层数
      if (right - left + 1 <= 10) {
         insertionSortSubarray(arr, left, right);
         return;
      }
      
      if (left < right) {
         // 随机选取基准值，避免有序数组触发最坏情况
         int pivotIndex = left + new Random().nextInt(right - left + 1);
         swap(arr, pivotIndex, right); // 将随机基准值移到右侧，复用原分区逻辑
         
         pivotIndex = partition(arr, left, right);
         // 优先递归较小的子数组，降低栈深度
         if (pivotIndex - left < right - pivotIndex) {
            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);
         } else {
            quickSort(arr, pivotIndex + 1, right);
            quickSort(arr, left, pivotIndex - 1);
         }
      }
   }
   
   // 针对子数组的插入排序，避免创建新数组
   private static void insertionSortSubarray(int[] arr, int left, int right) {
      for (int j = left + 1; j <= right; j++) {
         int key = arr[j];
         int i = j - 1;
         while (i >= left && arr[i] > key) {
            arr[i + 1] = arr[i];
            i--;
         }
         arr[i + 1] = key;
      }
   }
   
   private static int partition(int[] arr, int left, int right) {
      int pivot = arr[right];
      int i = left - 1;
      for (int j = left; j < right; j++) {
         if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
         }
      }
      swap(arr, i + 1, right);
      return i + 1;
   }
   
   private static void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
   }
   
   public static void main(String[] args) {
      Random rand = new Random();
      int L = 200000;
      // 插入排序仅测试小数据量，大数据量无实际意义
      int insertionMax = 1000;
      long[] timeInsertionSort = new long[L];
      long[] timeQuickSort = new long[L];
      
      for (int n = 1; n <= L; n++) {
         // 生成原始随机数组
         int[] originalArr = new int[n];
         for (int i = 0; i < n; i++) {
            originalArr[i] = rand.nextInt(n);
         }
         
         // 测试插入排序（仅小n值）
         if (n <= insertionMax) {
            int[] insertionArr = originalArr.clone();
            long start = System.nanoTime();
            insertionSort(insertionArr);
            long end = System.nanoTime();
            timeInsertionSort[n-1] = end - start;
         } else {
            // 大数据量插入排序标记为-1
            timeInsertionSort[n-1] = -1;
         }
         
         // 测试快速排序
         int[] quickArr = originalArr.clone();
         long start = System.nanoTime();
         quickSort(quickArr, 0, n - 1);
         long end = System.nanoTime();
         timeQuickSort[n-1] = end - start;
      }
      
      // 写入CSV文件
      try {
         PrintWriter writer = new PrintWriter("execution_times.csv", "UTF-8");
         writer.println("n,TInsertionSort(n),TQuickSort(n)");
         for (int n = 1; n <= L; n++) {
            writer.println(n + "," + timeInsertionSort[n-1] + "," + timeQuickSort[n-1]);
         }
         writer.close();
         System.out.println("CSV文件写入完成");
      } catch (IOException e) {
         e.printStackTrace();
      }
   }
}

说明 #

• 快速排序的随机基准值和小数据量切换逻辑，彻底避免了栈溢出问题，同时保证了平均O(nlogn)的时间复杂度
• 插入排序仅测试小n值，避免了程序因插入排序过慢而无法终止
• 两种排序都基于原始随机数组的副本，测试结果具备对比性
• 优先递归较小的子数组，进一步降低了递归栈的深度

内容的提问来源于stack exchange，提问作者AJ Rios