自定义Quicksort算法触发栈溢出异常：排查分区方法逻辑错误

核心错误分析 #

你的代码在数组包含重复元素时触发栈溢出，根源在于partition方法的逻辑错误：

• 统计元素数量的循环范围错误
  统计小于等于pivot的元素时，你遍历了整个数组的si+1到input.length，但正确的范围应该是当前处理的子数组si+1到ei。当递归处理子数组时，这个错误会把不属于当前子数组的元素也算入count，导致pivot被交换到超出当前子数组的位置，进而引发递归无法正确缩小问题规模，最终出现无限递归触发栈溢出。

  比如处理全重复元素的子数组时，错误的count会让pivotPos远大于当前子数组的ei，递归调用左半部分时会重复处理同一个范围，陷入死循环。

• pivot位置交换的潜在越界问题
  由于count计算错误，si+count可能超出当前子数组的ei范围，交换时会修改不属于当前子数组的元素，破坏数组结构，进一步加剧递归逻辑的混乱。

修正后的代码 #

public class Solution {

    public static int partition(int input[],int si, int ei) {
        int pivot = input[si], pivotPos = si, count = 0;
        // 只统计当前子数组si+1到ei中<=pivot的元素数量
        for(int i = pivotPos+1; i <= ei; i++) {
            if(input[i] <= pivot)
                count++;
        }
        // 交换pivot到当前子数组内的正确位置
        input[si] = input[si+count];
        input[si+count] = pivot;
        pivotPos = si+count;
        
        int i = si, j = ei, temp;
        // 调整左右元素，保证左<=pivot，右>pivot
        while(i < pivotPos && j > pivotPos) {
            if(input[i] <= pivot)
                i++;
            else {
                if(input[j] > pivot)
                    j--;
                else {
                    temp = input[i];
                    input[i] = input[j];
                    input[j] = temp;
                    i++;
                    j--;
                }
            }
        }
        return pivotPos;
    }

    public static void quickSort(int input[], int si, int ei) {
        if(si >= ei)
            return; 
        int pivotPos = partition(input, si, ei);
        quickSort(input, si, pivotPos-1);
        quickSort(input, pivotPos+1, ei);
    }
    
    public static void quickSort(int[] input) {
        quickSort(input, 0, input.length - 1);
    }
}

验证说明 #

修正后，测试用例[4,3,8,4,6,5]会被正确排序为[3,4,4,5,6,8]，且包含大量重复元素的数组（如全重复数组）也能正常递归排序，不会触发栈溢出。

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