Java快速排序运行抛出StackOverflowError栈溢出错误如何解决？

问题根因定位 #

你代码的核心错误是基准值索引mid的计算逻辑写反，直接导致后续分区逻辑完全混乱，递归永远无法触发终止条件，最终栈溢出：

• 错误行：int mid = low + (low - high) / 2;
• 你要计算low和high的中间索引，应该用low + (high - low) / 2，原写法算出来的mid会小于low甚至为负数，拿到的基准值完全不符合预期，分区永远无法收敛，递归深度无限增加触发StackOverflowError
• 额外笔误：报错信息里类名是QucikSort，和你代码里的QuickSort拼写不一致，保持类名和文件名统一即可

修正后可直接运行的代码 #

public class QuickSort {

    static void Sort(int[] arr, int low, int high) {
        if (low >= high) return;
        // 仅修改mid计算逻辑即可，其余代码无需改动
        int mid = low + (high - low) / 2;
        int pivot = arr[mid];
        int i = low;
        int j = high;

        while (i < j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;

            }
        }
        if (low < j)
            Sort(arr, low, j);
        if (high > i)
            Sort(arr, i, high);
    }

    public static void main(String[] args) {
        int[] arr = {5, 8, 45, 3, 54, 8, 3, 5, 31, 4, 21, 2, 5, 1};

        System.out.print("Before  quick sorting:");
        for (int j : arr) {
            System.out.print(" " + j);
        }
        System.out.println();
        
        Sort(arr, 0, arr.length - 1);

        System.out.print("After quick sorting:");
        for (int j : arr) {
            System.out.print(" " + j);
        }
    }
}

运行输出结果 #

Before  quick sorting: 5 8 45 3 54 8 3 5 31 4 21 2 5 1
After quick sorting: 1 2 3 3 4 5 5 5 8 8 21 31 45 54

内容的提问来源于stack exchange，提问作者Rajan kumar