实现快速排序处理大列表时频繁触发栈溢出，求排查解决

你的栈溢出不是终止条件的问题，而是快速排序在有序/接近有序的数据集下触发了最坏情况：每次选最后一个元素当基准，分区后只会得到长度为1和n-1的两个子数组，递归深度直接达到O(n)——10万条数据的递归深度远超JVM默认栈容量（通常仅几百到几千），必然撑爆栈。

以下是具体修复思路和代码修改：

1. 优化基准选择（解决最坏情况） #

把固定选最后一个元素改为三数取中或随机选择基准，避免在有序数据下出现极端递归深度：

三数取中实现示例 #

private void qSort(List<E> items, int low, int high, Comparator<E> comparator) {
    if (low >= high) {
        return;
    }

    // 三数取中：取low、mid、high的中位数作为基准，放到high位置
    int mid = low + (high - low) / 2;
    if (comparator.compare(items.get(low), items.get(mid)) > 0) {
        swap(items, low, mid);
    }
    if (comparator.compare(items.get(low), items.get(high)) > 0) {
        swap(items, low, high);
    }
    if (comparator.compare(items.get(mid), items.get(high)) > 0) {
        swap(items, mid, high);
    }

    E pivot = items.get(high);
    int leftPointer = low;
    int rightPointer = high;

    // 原有分区逻辑不变
    while (leftPointer < rightPointer) {
        while (leftPointer < rightPointer && comparator.compare(items.get(leftPointer), pivot) <= 0) {
            leftPointer++;
        }
        while (leftPointer < rightPointer && comparator.compare(items.get(rightPointer), pivot) >= 0) {
            rightPointer--;
        }
        swap(items, leftPointer, rightPointer);
    }
    swap(items, leftPointer, high);

    qSort(items, low, leftPointer - 1, comparator);
    qSort(items, leftPointer + 1, high, comparator);
}

2. 尾递归优化（进一步降低栈深度） #

即使做了基准优化，递归深度还是O(logn)，手动做尾递归优化可把栈深度压到更低：每次只递归处理较小的子数组，较大的子数组用循环代替递归，避免栈帧堆积。

优化后代码 #

private void qSort(List<E> items, int low, int high, Comparator<E> comparator) {
    // 用循环代替递归处理较大的子数组
    while (low < high) {
        // 三数取中基准选择（同上）
        int mid = low + (high - low) / 2;
        if (comparator.compare(items.get(low), items.get(mid)) > 0) {
            swap(items, low, mid);
        }
        if (comparator.compare(items.get(low), items.get(high)) > 0) {
            swap(items, low, high);
        }
        if (comparator.compare(items.get(mid), items.get(high)) > 0) {
            swap(items, mid, high);
        }
        E pivot = items.get(high);

        // 分区逻辑
        int leftPointer = low;
        int rightPointer = high;
        while (leftPointer < rightPointer) {
            while (leftPointer < rightPointer && comparator.compare(items.get(leftPointer), pivot) <= 0) {
                leftPointer++;
            }
            while (leftPointer < rightPointer && comparator.compare(items.get(rightPointer), pivot) >= 0) {
                rightPointer--;
            }
            swap(items, leftPointer, rightPointer);
        }
        swap(items, leftPointer, high);

        // 递归处理小的子数组，循环处理大的
        if (leftPointer - low < high - leftPointer) {
            qSort(items, low, leftPointer - 1, comparator);
            low = leftPointer + 1; // 循环处理右半部分
        } else {
            qSort(items, leftPointer + 1, high, comparator);
            high = leftPointer - 1; // 循环处理左半部分
        }
    }
}

3. 小数组切换插入排序（可选，提升性能） #

当子数组长度小于阈值（比如15），直接用插入排序替代递归，减少递归次数同时提升小数据排序效率：

private static final int INSERTION_SORT_THRESHOLD = 15;

private void qSort(List<E> items, int low, int high, Comparator<E> comparator) {
    // 小数组直接用插入排序
    if (high - low + 1 <= INSERTION_SORT_THRESHOLD) {
        insertionSort(items, low, high, comparator);
        return;
    }

    // 基准选择+分区逻辑同上...
}

// 插入排序实现
private void insertionSort(List<E> items, int low, int high, Comparator<E> comparator) {
    for (int i = low + 1; i <= high; i++) {
        E temp = items.get(i);
        int j = i - 1;
        while (j >= low && comparator.compare(items.get(j), temp) > 0) {
            items.set(j + 1, items.get(j));
            j--;
        }
        items.set(j + 1, temp);
    }
}

关键说明 #

• 增大栈内存只是临时 workaround，无法从根本解决最坏情况的递归深度问题，优化算法本身才是正确方向。
• 上述优化后，10万条数据的递归深度会降到约17层（log₂(100000)≈17），完全不会触发栈溢出。

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