为何quicksort2处理超90万数组时偶发StackOverflowError？如何解决？

嘿，你写的这个quicksort2是标准的递归版快排，但踩了快排的经典坑——固定选末尾元素当基准值（pivot），这就是大数组一半概率触发栈溢出的核心原因：

1. 当数组接近有序（不管升序还是降序）时，每次选末尾元素当基准，分区后其中一个子数组的长度会几乎和原数组一样长。比如数组完全升序，每次基准都是最大的元素，左边子数组长度是n-1，递归深度直接拉到O(n)级别。
2. Java默认的JVM栈深度也就几千到几万（不同版本略有差异），当数组超过90万时，一旦碰到这种极端不平衡的分区，递归层数远远超过栈的承载能力，直接就触发StackOverflowError了。你说一半概率出现，应该是数组的无序程度刚好让这种极端分区频繁发生的时候就会炸。

1. 别再固定选末尾当基准了！ #

改用三数取中法或者随机基准法，从根源上避免极端分区：

• 三数取中：选数组首、中、尾三个元素的中位数当基准，完美避开有序数组的最坏情况；
• 随机基准：随机挑数组里的一个元素当基准，从概率上降低极端情况的出现概率。

给你改好的三数取中版代码：

public static void quicksort2(int[] xs, int lo, int hi) {
    int h, l, p;
    if (lo < hi) {
        // 三数取中选基准，把基准移到末尾适配原有逻辑
        int mid = lo + (hi - lo) / 2;
        if (xs[mid] > xs[hi]) swap(xs, mid, hi);
        if (xs[lo] > xs[hi]) swap(xs, lo, hi);
        if (xs[mid] > xs[lo]) swap(xs, mid, lo);
        p = xs[hi]; // 现在hi位置的元素就是三数中的中位数

        l = lo;
        h = hi;
        do {
            while ((l < h) && (xs[l] <= p)) l++;
            while ((h > l) && (xs[h] >= p)) h--;
            if (l < h) swap(xs, l, h);
        } while (l < h);
        swap(xs, hi, l);
        quicksort2(xs, lo, l - 1);
        quicksort2(xs, l + 1, hi);
    }
}

private static void swap(int[] xs, int i, int j) {
    int t = xs[i];
    xs[i] = xs[j];
    xs[j] = t;
}

2. 递归深度砍半：只递归短数组 #

每次分区后，只对较短的子数组递归，较长的子数组用循环处理，这样递归深度直接降到O(log n)，绝对不会超栈：

public static void quicksort2(int[] xs, int lo, int hi) {
    while (lo < hi) {
        int l = lo, h = hi;
        int p = xs[hi];
        do {
            while ((l < h) && (xs[l] <= p)) l++;
            while ((h > l) && (xs[h] >= p)) h--;
            if (l < h) swap(xs, l, h);
        } while (l < h);
        swap(xs, hi, l);

        // 只递归短的那个子数组，长的用循环接着处理
        if (l - lo < hi - l) {
            quicksort2(xs, lo, l - 1);
            lo = l + 1;
        } else {
            quicksort2(xs, l + 1, hi);
            hi = l - 1;
        }
    }
}

3. 小数组换插入排序，既快又省栈 #

当子数组长度小于10~20的时候，递归的开销反而比插入排序大，而且插入排序在小数组上性能更好。加个判断，小范围直接用插入排序：

private static final int INSERTION_SORT_THRESHOLD = 15;

public static void quicksort2(int[] xs, int lo, int hi) {
    if (hi - lo + 1 <= INSERTION_SORT_THRESHOLD) {
        insertionSort(xs, lo, hi);
        return;
    }
    // 下面是原来的快速排序逻辑...
}

private static void insertionSort(int[] xs, int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++) {
        int key = xs[i];
        int j = i - 1;
        while (j >= lo && xs[j] > key) {
            xs[j + 1] = xs[j];
            j--;
        }
        xs[j + 1] = key;
    }
}

4. 彻底抛弃递归：用自己的栈模拟 #

如果不想碰递归，直接用Java的Deque模拟递归调用栈，完全避开JVM栈的限制：

public static void quicksortNonRecursive(int[] xs) {
    Deque<int[]> stack = new ArrayDeque<>();
    stack.push(new int[]{0, xs.length - 1});

    while (!stack.isEmpty()) {
        int[] range = stack.pop();
        int lo = range[0], hi = range[1];
        if (lo >= hi) continue;

        int l = lo, h = hi;
        int p = xs[hi];
        do {
            while ((l < h) && (xs[l] <= p)) l++;
            while ((h > l) && (xs[h] >= p)) h--;
            if (l < h) swap(xs, l, h);
        } while (l < h);
        swap(xs, hi, l);

        // 先压大的子数组，再压小的，保证栈深度最小
        if (l - lo > hi - l) {
            stack.push(new int[]{lo, l - 1});
            stack.push(new int[]{l + 1, hi});
        } else {
            stack.push(new int[]{l + 1, hi});
            stack.push(new int[]{lo, l - 1});
        }
    }
}

最核心的问题就是固定选末尾当基准导致的最坏情况递归深度超标，优先用三数取中优化基准选择，就能解决大部分问题；再结合递归深度优化或者非递归实现，不仅能彻底消除栈溢出，还能提升快排的整体性能哦！

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