使用快速排序处理大数组时如何修复StackOverflowError？

问题根源 #

你当前的快速排序实现选择数组末尾元素作为基准值（pivot），当数组接近有序时，递归深度会达到O(n)级别。以10万元素为例，递归次数可能接近10万次，远超Java默认的栈容量（通常仅几MB，对应几千次递归），直接触发StackOverflowError。调整栈大小能临时解决，但针对100万级别的数组，更推荐从算法本身优化，彻底避免递归过深的问题。

临时解决方案：调整JVM栈大小 #

在运行Java程序时，通过-Xss参数指定栈大小，例如：

java -Xss16m YourMainClass

• 16m表示将栈大小设置为16MB，可根据数组规模调整（处理100万元素可能需要-Xss32m甚至更大）。
• 注意：该方法仅为临时 workaround，无法从根本解决最坏情况的递归深度问题，且栈大小受操作系统限制，不能无限增大。

根本解决方案：优化快速排序实现 #

1. 优化基准值（pivot）选择：三数取中法 #

选择数组首、中、尾三个元素的中位数作为pivot，避免有序数组导致的最坏递归深度，将递归深度控制在O(log n)级别。

2. 尾递归优化 #

将第二个递归调用改为循环，减少栈帧的累积。因为在完成左子数组排序后，右子数组的排序属于尾调用，可以用循环替代递归，进一步降低栈使用。

3. 小数组切换插入排序 #

当子数组长度小于阈值（如15）时，改用插入排序，减少递归次数的同时，小数组上插入排序的实际效率优于快排。

修改后的代码示例 #

private static int partition(int a[], int start, int end) {
    // 三数取中优化pivot
    int mid = start + (end - start) / 2;
    // 交换首、中、尾的中位数到末尾，保持原partition逻辑
    if (a[mid] < a[start]) swap(a, start, mid);
    if (a[end] < a[start]) swap(a, start, end);
    if (a[mid] < a[end]) swap(a, mid, end);
    
    int pivot = a[end];
    int i = (start - 1);

    for (int j = start; j <= end - 1; j++) {
        if (a[j] < pivot) {
            i++;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, end);
    return (i + 1);
}

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

// 优化后的快速排序（尾递归+小数组优化）
public static long quickSort(int a[], int start, int end) {
    long comeco = System.currentTimeMillis();
    
    // 尾递归优化：用循环替代第二个递归
    while (start < end) {
        // 小数组切换插入排序
        if (end - start + 1 <= 15) {
            insertionSort(a, start, end);
            break;
        }
        
        int p = partition(a, start, end);
        // 优先递归更小的子数组，进一步减少栈深度
        if (p - start < end - p) {
            quickSort(a, start, p - 1);
            start = p + 1;
        } else {
            quickSort(a, p + 1, end);
            end = p - 1;
        }
    }
    
    long tempo = System.currentTimeMillis() - comeco;
    return tempo;
}

// 插入排序实现
private static void insertionSort(int[] a, int start, int end) {
    for (int i = start + 1; i <= end; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= start && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

额外提示：修正计时逻辑 #

你当前的代码在每次递归调用时都会计算时间，最终返回的是所有递归时间的总和（存在重复计算）。正确的做法应该是在最外层调用时启动计时，例如：

public static void main(String[] args) {
    int[] arr = new int[1000000];
    // 初始化数组...
    
    long startTime = System.currentTimeMillis();
    quickSort(arr, 0, arr.length - 1);
    long totalTime = System.currentTimeMillis() - startTime;
    System.out.println("排序耗时：" + totalTime + "ms");
}

内容的提问来源于stack exchange，提问作者Gustavo Calanzani