Java自定义QuickSort出现StackOverflowException的原因及优化咨询

兄弟，太懂这种盯着递归代码找不出栈溢出原因的抓狂感了！咱先从快速排序栈溢出的核心诱因说起，再结合你给出的代码片段（虽然没写完，但咱按行业里最常见的坑点来拆解），给你梳理排查方向和靠谱的优化方案：

最可能的问题根源 #

1. 递归终止条件写错了 #

这是新手最容易踩的坑！快速排序的递归终止条件必须是当子数组的左边界low大于等于右边界hig时，直接返回。如果写成low > hig才返回，那当low == hig时，代码还会继续递归调用，相当于无限递归，直接把栈撑爆。

举个反例（错误写法）：

static void quickSort(int[] arr,int low,int hig) {
    // 错误：少了等于的情况，low==hig时还会继续递归
    if (low > hig) {
        return;
    }
    // ... 后续partition和递归逻辑
}

正确的终止条件应该是：

if (low >= hig) {
    return;
}

2. Pivot选择太“死板”，导致递归深度爆炸 #

如果你的代码固定选第一个元素（low）或者最后一个元素（hig）当pivot，那当数组本身是有序/逆序的时候，每次partition后，其中一个子数组的长度只会比原数组小1，递归深度直接变成O(n)。而Java默认的栈深度大概只有几千，只要数组规模过万，必然抛出StackOverflowException。

3. Partition函数返回值或递归传参错误 #

比如partition返回的pivot位置不对，或者递归调用时把pivot本身包含进了子数组（比如调用quickSort(arr, low, pivot)而不是quickSort(arr, low, pivot-1)），这会导致子数组永远无法缩小，陷入无限递归。

针对性优化方案 #

1. 先把递归终止条件修正确认 #

这是最基础的第一步，一定要确保low >= hig时立即return，不给无限递归留机会。

2. 优化Pivot选择，避免极端情况 #

推荐两种靠谱的pivot选择策略：

• 三数取中法：选low、mid、hig三个位置的中位数作为pivot，能有效避免有序数组的极端情况。
  实现示例：

  private static void selectPivot(int[] arr, int low, int hig) {
      int mid = low + (hig - low) / 2;
      // 把中位数交换到low位置，作为后续partition的基准
      if (arr[mid] < arr[low]) swap(arr, low, mid);
      if (arr[hig] < arr[low]) swap(arr, low, hig);
      if (arr[hig] < arr[mid]) swap(arr, mid, hig);
      swap(arr, low, mid);
  }
  

• 随机选择法：每次随机选一个位置和low交换，再用这个位置的值当pivot，平均递归深度会降到O(logn)。

3. 手动尾递归优化，降低栈深度 #

Java本身不支持自动尾递归优化，但咱们可以手动改代码：每次递归只处理较短的子数组，较长的子数组用循环代替，这样栈深度会大幅降低。

实现示例：

static void quickSort(int[] arr,int low,int hig) {
    while (low < hig) {
        int pivot = partition(arr, low, hig);
        // 优先递归处理较短的子数组，较长的用循环接着处理
        if (pivot - low < hig - pivot) {
            quickSort(arr, low, pivot - 1);
            low = pivot + 1;
        } else {
            quickSort(arr, pivot + 1, hig);
            hig = pivot - 1;
        }
    }
}

4. 小数据量切换插入排序 #

当子数组长度小于某个阈值（比如10）时，改用插入排序。小数据量下插入排序的常数项更小，还能减少递归次数，进一步降低栈压力。

完整的优化后示例代码 #

import java.util.*;

public class Solution {
    static void quickSort(int[] arr, int low, int hig) {
        // 子数组长度小于10时，切换插入排序
        if (hig - low + 1 < 10) {
            insertionSort(arr, low, hig);
            return;
        }
        while (low < hig) {
            selectPivot(arr, low, hig);
            int pivot = partition(arr, low, hig);
            // 优先处理短子数组，减少栈深度
            if (pivot - low < hig - pivot) {
                quickSort(arr, low, pivot - 1);
                low = pivot + 1;
            } else {
                quickSort(arr, pivot + 1, hig);
                hig = pivot - 1;
            }
        }
    }

    private static int partition(int[] arr, int low, int hig) {
        int pivotVal = arr[low];
        int i = low, j = hig;
        while (i < j) {
            // 从右往左找小于pivot的元素
            while (i < j && arr[j] >= pivotVal) j--;
            arr[i] = arr[j];
            // 从左往右找大于pivot的元素
            while (i < j && arr[i] <= pivotVal) i++;
            arr[j] = arr[i];
        }
        arr[i] = pivotVal;
        return i;
    }

    private static void selectPivot(int[] arr, int low, int hig) {
        int mid = low + (hig - low) / 2;
        // 三数取中，把中位数放到low位置
        if (arr[mid] < arr[low]) swap(arr, low, mid);
        if (arr[hig] < arr[low]) swap(arr, low, hig);
        if (arr[hig] < arr[mid]) swap(arr, mid, hig);
        swap(arr, low, mid);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void insertionSort(int[] arr, int low, int hig) {
        for (int i = low + 1; i <= hig; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= low && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

    public static void main(String[] args) {
        // 用10000个元素的逆序数组测试，不会栈溢出
        int[] arr = new int[10000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr.length - i;
        }
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序完成：" + Arrays.toString(arr).substring(0, 50) + "...");
    }
}

内容的提问来源于stack exchange，提问作者mr.h