算法分析中出现java.lang.StackOverflowError：数组规模超10万时触发

嘿，这个问题我太熟了！之前帮同事排查过几乎一模一样的情况，咱们来捋清楚～

首先，你遇到的java.lang.StackOverflowError本质上是递归调用的层数超过了JVM允许的栈空间上限。Java默认的栈内存一般只有几MB，每个递归调用都会在栈上创建一个栈帧（存储方法参数、局部变量等），当递归层数达到几千次就会把栈撑满，更别说10万级的规模了。

为什么你的代码会触发这个问题？大概率是你的Partition方法选的pivot（基准元素）太“偏”了——比如每次都选数组的第一个或最后一个元素。如果传入的数组本身是有序的，每次Partition都会把数组分成1个元素和剩下的n-1个元素两部分，递归深度直接变成O(n)，10万次递归调用绝对会把栈炸穿。

下面给你两个靠谱的解决方案：

方案1：把递归改成迭代（最直接解决栈溢出） #

你的Select方法是尾递归（递归调用是方法的最后一步操作），这种递归非常容易转成循环，完全不需要依赖栈空间。改造后的代码大概是这样：

public static int Select(int[] A, int l, int m, long h) {
    while (true) {
        int pos = Partition(A, l, h);
        if (pos == m) {
            // 找到目标元素，直接返回
            return A[pos];
        } else if (pos > m) {
            // 目标在左半部分，缩小右边界
            h = pos - 1;
        } else {
            // 目标在右半部分，缩小左边界
            l = pos + 1;
        }
    }
}

不管数组规模多大，这个循环都只会占用一个栈帧，彻底解决栈溢出问题。

方案2：优化Partition的pivot选择（从根源减少递归深度） #

如果你还是想用递归实现，那得从Partition入手，保证每次分割数组都能得到相对均衡的两部分，把递归深度降到O(logn)。最经典的做法是用中位数的中位数来选pivot：

• 把数组分成每5个元素一组，对每组排序后取中位数
• 递归找到这些中位数的中位数，用它作为pivot进行Partition
  这样最坏情况下递归深度也只有log₂(100000)≈17层，远远低于JVM的栈上限，完全不会爆栈。

另外提一句：有人会说可以调JVM的栈大小参数（比如-Xss2m），但这是治标不治本的办法——数组规模再大一点还是会溢出，而且不同环境的栈限制不一样，不推荐用这种方式。

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