快速排序处理60万+已排序大数组时栈溢出的解决方法

你的快速排序实现每次选数组末尾元素作为基准值（pivot），在已排序数组场景下，每次partition后基准值都会落在数组最右端，导致递归调用深度变为O(n)。Java默认栈深度通常只有几百到几千，60万级别的递归深度直接触发StackOverflowError。第一次排序时数组无序，递归深度为O(logn)，因此正常；第二次数组完全有序，触发了快速排序的最坏情况。

解决方案1：优化基准值选择（避免最坏情况） #

最常用的是三数取中法：取数组起始、中间、末尾三个位置的元素，选它们的中位数作为基准值，再将基准值交换到末尾（兼容原partition逻辑）。这样在已排序或接近有序的数组中，能有效平衡递归深度。

修改后的代码：

private static void quickSort(String[] arr, int start, int end) {
    if (end <= start) return;

    // 三数取中选基准值
    int mid = start + (end - start) / 2;
    // 交换中位数到末尾，作为pivot
    if (arr[start].compareTo(arr[mid]) > 0) swap(arr, start, mid);
    if (arr[start].compareTo(arr[end]) > 0) swap(arr, start, end);
    if (arr[mid].compareTo(arr[end]) > 0) swap(arr, mid, end);

    int pivot = partition(arr, start, end);
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
}

// 新增交换工具方法
private static void swap(String[] arr, int i, int j) {
    String temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 原partition方法不变
private static int partition(String[] arr, int start, int end) {
    String pivot = arr[end];
    int i = start - 1;
    for (int j = start; j < end; ++j) {
        if (arr[j].compareTo(pivot) < 0) {
            ++i;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, end);
    return i + 1;
}

解决方案2：尾递归优化（减少栈帧占用） #

快速排序的第二个递归调用是尾调用（调用后无其他操作），可将其改为循环，避免创建新栈帧，把递归深度降到O(logn)。

修改后的quickSort方法：

private static void quickSort(String[] arr, int start, int end) {
    while (end > start) {
        int pivot = partition(arr, start, end);
        // 优先递归处理较小的子数组，进一步减少栈深度
        if (pivot - start < end - pivot) {
            quickSort(arr, start, pivot - 1);
            start = pivot + 1; // 循环处理较大的子数组
        } else {
            quickSort(arr, pivot + 1, end);
            end = pivot - 1; // 循环处理较大的子数组
        }
    }
}

解决方案3：小数组切换插入排序 #

当子数组长度小于某个阈值（比如20），插入排序的效率比快速排序更高（递归开销小，且插入排序在有序/接近有序数组上是O(n)时间），同时能减少递归次数。

修改后的quickSort方法：

private static final int INSERTION_SORT_THRESHOLD = 20;

private static void quickSort(String[] arr, int start, int end) {
    if (end - start + 1 <= INSERTION_SORT_THRESHOLD) {
        insertionSort(arr, start, end);
        return;
    }

    // 结合三数取中优化基准值
    int mid = start + (end - start) / 2;
    if (arr[start].compareTo(arr[mid]) > 0) swap(arr, start, mid);
    if (arr[start].compareTo(arr[end]) > 0) swap(arr, start, end);
    if (arr[mid].compareTo(arr[end]) > 0) swap(arr, mid, end);

    int pivot = partition(arr, start, end);
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
}

// 插入排序实现
private static void insertionSort(String[] arr, int start, int end) {
    for (int i = start + 1; i <= end; i++) {
        String temp = arr[i];
        int j = i - 1;
        while (j >= start && arr[j].compareTo(temp) > 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

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