快速排序实现中出现StackOverflowError的原因排查求助

嘿，我来帮你搞定这个栈溢出的问题！

问题根源 #

你遇到的StackOverflowError完全是因为快速排序在最坏场景下的递归深度爆炸。

你的实现里固定选数组的最后一个元素当基准值（pivot），当数组已经完全有序（不管升序还是降序）时，每次partition操作都会把基准值放到数组的最右端（因为所有元素都≤它）。这就导致每次递归调用时，其中一个子数组的长度只比原数组少1，另一个子数组直接是空的。

举个例子，你测试用的是40000长度的数组，排序后再跑一次，递归深度会直接拉到40000层左右，但Java虚拟机默认的调用栈深度也就1000-2000层，根本扛不住，直接就栈溢出了。

解决方案 #

我们只要优化基准值的选择，就能避免这种极端最坏情况，给你两个常用的靠谱方案：

1. 随机选基准值

在分区前，随机挑一个元素和最后一个元素交换，再用原来的逻辑处理。这样哪怕数组有序，基准值也是随机的，不会让递归深度一路飙升。

修改后的partition代码：

private int partition(int arr[], int first, int last) {
    // 随机选一个位置，和最后一位交换
    Random rand = new Random();
    int randomPivotPos = first + rand.nextInt(last - first + 1);
    int temp = arr[randomPivotPos];
    arr[randomPivotPos] = arr[last];
    arr[last] = temp;
    
    // 下面是你原来的分区逻辑，不用改
    int pivot = arr[last]; 
    int i = (first-1);
    for (int j = first; j < last; j++) {
        if (arr[j] <= pivot) {
            i++;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    temp = arr[i+1];
    arr[i+1] = arr[last];
    arr[last] = temp;
    return i+1;
}

2. 三数取中法选基准值

从数组的开头、中间、结尾三个位置里，挑大小居中的那个元素当基准值，这种方式对有序数组的优化效果特别好：

private int partition(int arr[], int first, int last) {
    // 找首、中、尾三个位置里的中间值
    int mid = first + (last - first) / 2;
    int pivotPos = mid;
    
    // 判断哪个位置的元素是中间值
    if ((arr[first] > arr[mid]) != (arr[first] > arr[last])) {
        pivotPos = first;
    } else if ((arr[mid] > arr[first]) != (arr[mid] > arr[last])) {
        pivotPos = mid;
    } else {
        pivotPos = last;
    }
    
    // 把基准值换到最后一位，复用原来的分区逻辑
    int temp = arr[pivotPos];
    arr[pivotPos] = arr[last];
    arr[last] = temp;
    
    // 原分区逻辑不变
    int pivot = arr[last]; 
    int i = (first-1);
    for (int j = first; j < last; j++) {
        if (arr[j] <= pivot) {
            i++;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    temp = arr[i+1];
    arr[i+1] = arr[last];
    arr[last] = temp;
    return i+1;
}

额外优化：减少递归深度

除了基准值优化，还可以改一下递归逻辑，先处理较短的子数组，再用循环代替较长子数组的递归，这样能把递归深度压到O(log n)：

private void quickSort(int arr[], int first, int last) {
    while (first < last) {
        int pivindex = partition(arr, first, last);
        // 先递归处理较短的子数组，避免深度爆炸
        if (pivindex - first < last - pivindex) {
            quickSort(arr, first, pivindex-1);
            first = pivindex + 1;
        } else {
            quickSort(arr, pivindex+1, last);
            last = pivindex - 1;
        }
    }
}

测试效果 #

改完之后再跑你的代码，不管是随机数组还是已排序数组，都不会再出现栈溢出了，而且排序速度也会快很多。

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