快速排序处理已排序大数组时崩溃的技术问题求助

看起来你碰到了快速排序经典的最坏场景问题——递归栈溢出！

核心原因拆解 #

当你先通过quickSortDSC把大数组（50k、100k量级）处理成完全降序的状态，再调用quickSortASC时，标准快速排序如果是选择固定位置（比如第一个或最后一个元素）作为基准的话，会直接触发最坏时间复杂度场景：

• 每一轮分区只能把基准放到数组的一端，递归深度会达到O(n)级别
• 操作系统默认的线程栈大小通常只有几MB，这么深的递归会直接撑爆栈，导致程序崩溃

而如果跳过quickSortDSC，随机数组的递归深度平均是O(logn)，完全在栈的承载范围内，所以程序能正常运行。

针对性修复方案 #

1. 优化基准元素选择（最常用、最有效的修复） #

别再用固定位置当基准了，改用以下两种策略之一，就能避免最坏场景：

• 三数取中法：选数组首、尾、中间位置元素的中位数当基准
• 随机基准法：随机挑数组里的一个元素当基准

这里给你一个三数取中法的升序快速排序实现示例：

// 找到三数中位数并放到合适位置，简化分区逻辑
int medianOfThree(int arr[], int low, int high) {
    int mid = low + (high - low) / 2;
    // 排序三个位置的元素，把中位数放到high-1
    if (arr[low] > arr[mid]) swap(arr[low], arr[mid]);
    if (arr[low] > arr[high]) swap(arr[low], arr[high]);
    if (arr[mid] > arr[high]) swap(arr[mid], arr[high]);
    swap(arr[mid], arr[high-1]);
    return arr[high-1];
}

void quickSortASC(int arr[], int low, int high) {
    if (low < high) {
        int pivot = medianOfThree(arr, low, high);
        int i = low, j = high - 1;
        // 分区循环
        while (true) {
            while (arr[++i] < pivot);
            while (arr[--j] > pivot);
            if (i < j) swap(arr[i], arr[j]);
            else break;
        }
        // 把基准放到正确的分区位置
        swap(arr[i], arr[high-1]);
        // 递归处理左右分区
        quickSortASC(arr, low, i-1);
        quickSortASC(arr, i+1, high);
    }
}

2. 小数组切换插入排序+递归深度限制 #

当递归处理的数组长度小于某个阈值（比如16）时，直接改用插入排序——小数组下插入排序比快速排序更快，还能避免递归深度问题：

// 插入排序实现
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;
    }
}

void quickSortASC(int arr[], int low, int high) {
    const int THRESHOLD = 16;
    if (high - low + 1 > THRESHOLD) {
        // 这里放优化后的快速排序分区逻辑（比如搭配三数取中）
        // ...
        quickSortASC(arr, low, partitionIdx - 1);
        quickSortASC(arr, partitionIdx + 1, high);
    } else {
        insertionSort(arr, low, high);
    }
}

3. 改用非递归版本的快速排序 #

用手动栈模拟递归过程，完全避开系统栈的限制，适合处理超大数组：

void quickSortASC(int arr[], int low, int high) {
    stack<pair<int, int>> sortStack;
    sortStack.push({low, high});
    
    while (!sortStack.empty()) {
        auto [currLow, currHigh] = sortStack.top();
        sortStack.pop();
        
        if (currLow >= currHigh) continue;
        
        // 随机选基准，避免最坏场景
        int pivotIdx = currLow + rand() % (currHigh - currLow + 1);
        swap(arr[pivotIdx], arr[currHigh]);
        int pivot = arr[currHigh];
        
        // 分区操作
        int i = currLow - 1;
        for (int j = currLow; j < currHigh; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i+1], arr[currHigh]);
        int partitionIdx = i + 1;
        
        // 先压入较大的分区，保证栈的大小稳定在O(logn)
        sortStack.push({currLow, partitionIdx - 1});
        sortStack.push({partitionIdx + 1, currHigh});
    }
}

验证步骤 #

1. 先单独测试优化后的quickSortASC对完全降序大数组的处理能力，确认不会崩溃
2. 对比优化前后的排序耗时——优化基准选择后，最坏场景的时间复杂度会从O(n²)降到O(nlogn)，性能也会有明显提升

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