Java中以首个元素为基准的快速排序出现Stack Overflow问题

嗨，我来帮你捋清楚为啥会出现栈溢出的问题，以及怎么解决它！

问题根源分析 #

当你用第一个元素作为基准（pivot），并且面对的是已经升序有序或者完全降序逆序的列表时，快速排序会触发最坏情况：

• 每次分区（partition）操作后，其中一个子分区的长度会是原分区长度减1，另一个子分区则是空的。比如100000个元素的有序列表，第一次分区后左分区为空，右分区剩99999个元素；第二次分区后右分区又变成99998个，以此类推。
• 这种情况下，递归调用的深度会达到**O(n)**级别（也就是100000层），而Java的默认调用栈深度一般只有几千到一万左右，完全撑不住这么多层递归，自然就抛出StackOverflowError了。

另外提个小细节：你sort方法里的if (list.size() < 0)判断是无效的，因为ArrayList.size()的返回值永远是非负的，建议改成if (list == null || list.isEmpty())来正确处理空列表或null的情况。

解决方法 #

这里有几个实用的方案，既能解决栈溢出问题，还能优化排序性能：

1. 优先递归处理较小的子分区（最直接的解决方案）

修改你的recursiveSort方法，先递归处理长度更小的子分区，用循环代替递归处理较大的子分区。这样递归深度会被控制在**O(logn)**级别（比如100000个元素的话，log₂(100000)也就17层左右），完全不会触发栈溢出。

修改后的代码示例：

private void recursiveSort(ArrayList<E> list, int leftIndex, int rightIndex) {
    while (leftIndex < rightIndex) { // 用循环替代递归处理大分区
        int partition = partition(list, leftIndex, rightIndex);
        
        // 先递归处理更小的子分区，控制栈深度
        if (partition - leftIndex < rightIndex - partition) {
            recursiveSort(list, leftIndex, partition - 1);
            leftIndex = partition + 1; // 大分区交给循环处理，不占栈空间
        } else {
            recursiveSort(list, partition + 1, rightIndex);
            rightIndex = partition - 1;
        }
    }
}

2. 小分区改用插入排序（额外性能优化）

当子分区的长度很小（比如小于20），插入排序的实际性能比快速排序更好，还能减少递归调用次数。你可以在recursiveSort开头加个判断：

private void recursiveSort(ArrayList<E> list, int leftIndex, int rightIndex) {
    // 子分区长度小于20时，改用插入排序
    if (rightIndex - leftIndex + 1 < 20) {
        insertionSort(list, leftIndex, rightIndex);
        return;
    }
    
    // 剩下的大分区处理逻辑（沿用上面的循环+递归小分区的代码）
    while (leftIndex < rightIndex) {
        int partition = partition(list, leftIndex, rightIndex);
        if (partition - leftIndex < rightIndex - partition) {
            recursiveSort(list, leftIndex, partition - 1);
            leftIndex = partition + 1;
        } else {
            recursiveSort(list, partition + 1, rightIndex);
            rightIndex = partition - 1;
        }
    }
}

// 新增插入排序辅助方法
private void insertionSort(ArrayList<E> list, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        E key = list.get(i);
        int j = i - 1;
        while (j >= left && list.get(j).compareTo(key) > 0) {
            list.set(j + 1, list.get(j));
            j--;
        }
        list.set(j + 1, key);
    }
}

这个改动不仅能进一步降低递归深度，还能提升整体排序的实际运行效率。

3. 结合你已有的PivotChooser逻辑

你已经实现了不同的基准选择器（比如中位数三分区），这种方式本来就能避免最坏情况的出现，但如果你需要测试“首个元素作为基准”的场景，前面两个方案是最直接的解决办法。

总的来说，核心问题就是最坏情况下的递归深度超出了Java栈的承载限制，通过控制递归深度就能完美解决这个问题啦！

备注：内容来源于stack exchange，提问作者Drake