快速排序实证分析遭遇StackOverflowError问题求助

哥们，我之前做大规模数据排序时也踩过这个坑！你遇到的问题本质是固定选arr[0]当基准导致的最坏递归深度——虽然你的数据集是随机生成，但偶发情况下会出现基准恰好是当前子数组的最小值/最大值，这时候分区会变成一边空、一边是n-1个元素，递归深度直接拉到O(n)，而Java默认的栈深度大概只有几千，10000个元素肯定会爆栈。结合分区函数可能的问题，给你几个落地的解决方法：

1. 先搞定基准选择：避免最坏情况 #

固定选首元素当基准是快速排序的大忌，换成三数取中或者随机基准能把递归深度稳定在O(logn)，彻底解决栈溢出问题。推荐三数取中，比随机基准更稳定：

// 取首、尾、中间元素的中位数作为基准，放到low位置
private static int medianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    // 排序三个位置的元素，把中位数移到low处
    if (arr[low] > arr[mid]) swap(arr, low, mid);
    if (arr[low] > arr[high]) swap(arr, low, high);
    if (arr[mid] > arr[high]) swap(arr, mid, high);
    swap(arr, mid, low);
    return arr[low];
}

2. 优化递归：尾递归消除 #

就算基准选得好，极端情况下还是可能有较深的递归，用尾递归优化把较大的子数组改成循环处理，栈里只保留较小的子数组递归，进一步降低栈压力：

public static void quickSort(int[] arr) {
    quickSortOptimized(arr, 0, arr.length - 1);
}

private static void quickSortOptimized(int[] arr, int low, int high) {
    while (low < high) {
        int partitionIdx = partition(arr, low, high);
        // 递归处理较短的子数组，较长的用循环迭代
        if (partitionIdx - low < high - partitionIdx) {
            quickSortOptimized(arr, low, partitionIdx);
            low = partitionIdx + 1;
        } else {
            quickSortOptimized(arr, partitionIdx + 1, high);
            high = partitionIdx;
        }
    }
}

3. 修复分区函数：避免不均或死循环 #

你的分区函数可能存在分区不均的问题，推荐用Hoare分区法（比常见的Lomuto分区效率更高，交换次数更少），配合三数取中基准：

private static int partition(int[] arr, int low, int high) {
    int pivot = medianOfThree(arr, low, high);
    int i = low - 1;
    int j = high + 1;
    while (true) {
        // 找到左侧大于等于基准的元素
        do {
            i++;
        } while (arr[i] < pivot);
        // 找到右侧小于等于基准的元素
        do {
            j--;
        } while (arr[j] > pivot);
        // 指针相遇，返回分区点
        if (i >= j) {
            return j;
        }
        // 交换两侧元素
        swap(arr, i, j);
    }
}

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

4. 小数据集切换插入排序 #

当子数组长度小于某个阈值（比如20），插入排序的效率反而比快速排序高，还能减少递归次数，进一步降低栈使用：

在quickSortOptimized里加个判断：

private static void quickSortOptimized(int[] arr, int low, int high) {
    // 子数组过小时用插入排序
    if (high - low + 1 <= 20) {
        insertionSort(arr, low, high);
        return;
    }
    // 原循环逻辑...
}

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

把这些优化加进去后，别说10000个元素，100万都不会栈溢出，而且排序效率也会提升不少。

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