快速排序遇StackOverflow问题：逆序数组n=100000时出错

这太正常了！咱们来一步步拆解为什么会出现这种情况：

首先先看你用到的快速排序代码：

private void quickSort(int[] numbers, int l, int r) { 
    if (l < r) { 
        int p = numbers[r]; 
        int i = l - 1; 
        int j = r; 
        do { 
            do { 
                i++; 
            } while (numbers[i] < p); 
            do { 
                j--; 
            } while (j >= l && numbers[j] > p); 
            if (i < j) { 
                swap(numbers, i, j); 
            } 
        } while (i < j); 
        swap(numbers, i, r); 
        quickSort(numbers, l, i - 1); 
        quickSort(numbers, i + 1, r); 
    } 
}

问题出在基准选择和最坏情况的递归深度 #

你这个版本的快速排序，每次选择当前子数组的最后一个元素作为基准值。当你传入的是完全逆序的数组时，这个基准值刚好是当前子数组里最小的元素：

• 每次划分后，所有元素都会被分到基准值的左边，右边的子数组长度为0
• 这就导致递归调用变成了一条“直线”——每次只处理长度减1的子数组，递归深度等于原数组的长度

而Java虚拟机（JVM）的默认调用栈是有大小限制的（通常在几百KB到几MB之间），每个递归方法调用都会在栈里创建一个栈帧。当数组长度是100000时，递归深度达到100000层，远远超过了栈的承载上限，自然就抛出了StackOverflowError；而长度为10000时，递归深度刚好在默认栈的承受范围内，所以能正常运行。

怎么解决这个问题？ #

给你几个实用的优化方案：

• 随机选择基准：每次从子数组里随机挑一个元素和最后一个元素交换，再用它作为基准，避免最坏情况的固定出现
• 三数取中法：取子数组的首、中、尾三个元素的中位数作为基准，让划分更平衡
• 递归深度阈值切换：当递归深度超过某个值（比如20）时，改用插入排序这类非递归的排序算法
• 改用迭代版快速排序：用手动模拟栈来替代JVM的调用栈，彻底避免栈溢出问题

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