实现浮点型快速排序遇大数组栈溢出问题求助

一、先排查测试代码里的隐藏bug #

你看测试类的init方法里，javaSort = quickSort;这行是引用赋值，意味着javaSort和quickSort指向的是同一个float数组对象。后续你调用Arrays.sort(javaSort)和自己的QuickSort.sort(quickSort)其实是在排序同一个数组，最后assertArrayEquals肯定会通过，但这完全没起到对比两个排序结果的作用！

正确的做法应该是拷贝数组内容，比如：

javaSort = Arrays.copyOf(quickSort, SIZE);

这样两个数组才是独立的，测试才有意义。

二、栈溢出的核心原因：递归深度过大 #

Java虚拟机的默认栈容量有限（通常在几百KB到几MB之间），每一次递归调用都会在栈中创建一个栈帧。对于大小为1e8的数组，如果你的快速排序递归深度接近O(n)（比如极端有序的情况，即使有三数取中也可能出现较深的递归），栈帧的数量会直接超过虚拟机的栈容量上限，导致StackOverflowError。

而1e7时正常，是因为递归深度还没触碰到栈的阈值，但这只是侥幸，换个极端数据说不定1e7也会溢出。

三、解决栈溢出的两种有效方案 #

1. 尾递归优化（减少栈帧数量） #

我们可以对递归的顺序做调整：每次只递归处理较小的那个子数组，较大的子数组用循环代替，这样递归深度会被控制在O(log n)级别，即使是1e8的数组，log₂(1e8)大概是27，完全不会栈溢出。

修改你的quickSort方法：

private static void quickSort(float[] table, int first, int last) {
    while (first < last) {
        int pivotIndex = partition(table, first, last);
        // 优先递归处理较小的子数组，减少递归深度
        if (pivotIndex - first < last - pivotIndex) {
            quickSort(table, first, pivotIndex - 1);
            first = pivotIndex + 1; // 较大的子数组用循环处理
        } else {
            quickSort(table, pivotIndex + 1, last);
            last = pivotIndex - 1; // 较大的子数组用循环处理
        }
    }
}

2. 完全改为迭代版本（彻底避免递归栈） #

用手动模拟栈（比如java.util.Deque）来存储需要排序的区间，完全替代递归调用，这样不管数组多大，都不会用到虚拟机的调用栈，从根源上解决栈溢出问题：

public static void sort(float[] table) {
    if (table == null || table.length <= 1) {
        return;
    }
    Deque<int[]> stack = new LinkedList<>();
    stack.push(new int[]{0, table.length - 1});
    
    while (!stack.isEmpty()) {
        int[] range = stack.pop();
        int first = range[0];
        int last = range[1];
        
        if (first >= last) {
            continue;
        }
        
        int pivotIndex = partition(table, first, last);
        // 先压入较大的区间，再压入较小的，保证处理顺序和递归一致（可选，不影响正确性）
        stack.push(new int[]{pivotIndex + 1, last});
        stack.push(new int[]{first, pivotIndex - 1});
    }
}

四、额外优化建议 #

• 对于小规模子数组（比如长度小于20），可以切换为插入排序，因为插入排序在数据量小时性能更好，也能减少递归次数。
• 确保你的sort3方法是正确的三数取中（取first、mid、last三个位置的中位数放到mid位置），这能进一步降低最坏情况的出现概率。

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