固定基准点Java快速排序栈溢出问题及优化咨询

1. StackOverflowError的成因 #

当数组**已经有序（或接近有序）时，选择末尾元素作为固定基准点的策略会导致极端不平衡的分区：每次分区后，基准点左侧子数组长度为n-1，右侧子数组长度为0。这种情况下，递归调用的深度会达到O(n)**级别。

Java默认的调用栈深度通常在几千到一万左右，当数组元素超过10万时，递归深度远超栈的容量限制，就会触发StackOverflowError。

至于“有时排序完成后才报错”的情况，本质是递归调用栈在排序过程中已经积累了过多的栈帧，即使排序逻辑执行完毕，栈帧释放过程中仍会触发栈溢出检查。

2. 优化方案：避免栈溢出并支持大数据集 #

（1）尾递归优化（减少递归深度） #

核心思路是每次只递归处理较小的子数组，较大的子数组通过循环代替递归，将递归深度控制在**O(logn)**级别，完全避免栈溢出。修改后的quickSort方法如下：

private void quickSort(int[] array, int first, int last) {
    while (first < last) {
        int pivot = partition(array, first, last);
        // 优先递归处理长度更小的子数组，减少递归栈深度
        if (pivot - first < last - pivot) {
            quickSort(array, first, pivot - 1);
            first = pivot + 1; // 循环处理右侧较大的子数组
        } else {
            quickSort(array, pivot + 1, last);
            last = pivot - 1; // 循环处理左侧较大的子数组
        }
    }
}

（2）非递归实现（完全替代递归栈） #

用手动模拟的栈存储待处理的区间，彻底避开Java调用栈的限制：

private void quickSortNonRecursive(int[] array) {
    Stack<int[]> stack = new Stack<>();
    stack.push(new int[]{0, array.length - 1});
    
    while (!stack.isEmpty()) {
        int[] range = stack.pop();
        int first = range[0];
        int last = range[1];
        
        if (first >= last) continue;
        
        int pivot = partition(array, first, last);
        // 先压入较大的区间，保证后续处理较小区间时栈深度更小
        if (pivot - first > last - pivot) {
            stack.push(new int[]{first, pivot - 1});
            stack.push(new int[]{pivot + 1, last});
        } else {
            stack.push(new int[]{pivot + 1, last});
            stack.push(new int[]{first, pivot - 1});
        }
    }
}

（3）小数组切换插入排序 #

当子数组长度小于某个阈值（如20）时，递归的开销会超过排序本身的开销，此时切换为插入排序，既减少递归次数，又提升整体效率。

3. 固定基准点快速排序的性能提升策略 #

（1）预处理打乱数组 #

固定基准点的最大隐患是有序/接近有序数组的最坏情况，排序前先随机打乱数组，能将这种极端情况的概率降到最低，保证平均时间复杂度维持在O(nlogn)。

（2）三路分区优化（处理重复元素） #

当数组中存在大量重复元素时，普通的二路分区会导致重复元素被多次递归处理。改用三路分区（将数组划分为小于基准、等于基准、大于基准三部分），可以跳过中间等于基准的区间，大幅减少递归次数：

// 三路分区示例
public void threeWayPartition(int[] array, int first, int last, int[] bounds) {
    int pivot = array[last];
    int lt = first;
    int gt = last;
    int i = first;
    
    while (i <= gt) {
        if (array[i] < pivot) {
            swap(array, lt++, i++);
        } else if (array[i] > pivot) {
            swap(array, i, gt--);
        } else {
            i++;
        }
    }
    bounds[0] = lt; // 等于基准区间的左边界
    bounds[1] = gt; // 等于基准区间的右边界
}

对应的递归逻辑只需处理[first, lt-1]和[gt+1, last]两个区间。

（3）分区过程优化 #

将单循环的分区改为双指针法，减少元素交换的次数，提升分区效率：

// 双指针分区示例
public int partition(int[] array, int first, int last) {
    int pivot = array[last];
    int left = first;
    int right = last - 1;
    
    while (left <= right) {
        while (left <= right && array[left] <= pivot) left++;
        while (left <= right && array[right] > pivot) right--;
        if (left < right) {
            swap(array, left, right);
        }
    }
    swap(array, left, last);
    return left;
}

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