如何在不设置array.length-1的情况下修复简单快速排序的StackOverflowError

问题根源 #

代码出现栈溢出的核心问题非常明确：你在递归调用的私有sort方法第一行，直接把传入的子区间右边界right参数，强制覆盖为了整个数组的最大下标array.length-1。
快速排序的核心逻辑是每次分区后递归处理左右两个独立的子区间，右边界应该随着递归逐层缩小，但你每次进入方法都把右边界重置为整个数组的最后一位，区间永远不会收敛，最终就会进入无限递归，把栈内存占满抛出StackOverflowError。
之前长度为2、3的部分数组测试通过只是巧合：这些短数组首次调用的右边界刚好等于整个数组的最大下标，第一次分区刚好能走完，等到需要递归处理更小的子区间时，边界重置的问题就会暴露，直接触发死递归。

修复方案 #

你的需求是不能修改公有sort方法中sort(array, 0, array.length)的传参写法，只需要把边界调整的逻辑从私有sort方法里移到公有sort的调用环节即可，不要在每次递归的时候都重置右边界：

private static class Quicksort {
    // 私有sort方法不再重置right参数，直接使用传入的子区间边界
    private void sort(int[] array, int left, int right) {           
        int l = left;
        int r = right;
        int pivot = array[right];

        // 分区逻辑
        while (l <= r) {
            while (array[l] < pivot)
                l++;
            while (array[r] > pivot)
                r--;

            // 交换逻辑
            if (l <= r) {
                int temp = array[l];
                array[l] = array[r];
                array[r] = temp;
                l++; 
                r--;
            }
        }
        if (left < r)
            sort(array, left, r);
        if (right > l)
            sort(array, l, right);
    }

    public int lenRight(int[] array) {
        return array.length - 1;
    }

    public void sort(int[] array) {
        // 仅在首次调用时处理边界，满足不修改原传参形式的要求
        sort(array, 0, lenRight(array));
    }
}

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