快速排序处理长数组遇栈溢出及计时方法优化求助

一、栈溢出问题修复 #

栈溢出的核心原因是递归深度超过程序栈的限制，结合你的代码来看，有几个关键错误和优化点：

1. 修正递归终止条件 #

原代码的start + 1 < end会漏掉长度为2的子数组排序，还可能导致无效递归调用。正确的逻辑是：当子数组元素数量大于1时才继续递归，即：

if (start < end) { // 子数组长度>1时处理
    // ... 分区与递归
}

2. 修复递归范围错误 #

原代码递归左侧子数组时用了quickSort(arr, start, p)，但p是pivot的最终位置（已经处于正确排序位置），左侧子数组应该是[start, p-1]，右侧是[p+1, end]。这个错误会导致重复处理pivot元素，加剧栈压力，甚至引发无限递归。

3. 优化递归顺序（控制栈深度） #

默认先递归大的子数组会让栈深度达到O(n)（最坏情况），改成先递归较小的子数组，再用循环处理较大的，可以把栈深度控制在O(log n)级别，彻底避免栈溢出：

void quickSort(int arr[], int start, int end) {
    while (start < end) {
        int p = partition(arr, start, end);
        // 优先处理更小的子数组，减少栈占用
        if (p - start < end - p) {
            quickSort(arr, start, p - 1);
            start = p + 1;
        } else {
            quickSort(arr, p + 1, end);
            end = p - 1;
        }
    }
}

4. 优化pivot选择（避免最坏情况） #

直接选第一个元素当pivot，在数组接近有序时会导致分区极不平衡，递归深度飙升。用三数取中法（取start、mid、end的中位数）作为pivot，能避免这种最坏情况：

int partition(int arr[], int start, int end) {
    // 三数取中选pivot
    int mid = start + (end - start) / 2;
    // 交换三个位置的元素，把中位数放到start位置
    if (arr[mid] < arr[start]) swap(arr, start, mid);
    if (arr[end] < arr[start]) swap(arr, start, end);
    if (arr[end] < arr[mid]) swap(arr, mid, end);
    swap(arr, start, mid);
    
    int pivot = arr[start];
    int i = start + 1;
    int j = end;

    while (i <= j) {
        while (i <= j && arr[i] < pivot)
            i++;
        while (i <= j && arr[j] > pivot)
            j--;
        if (i < j)
            swap(arr, i, j);
        else
            break;
    }
    swap(arr, start, j);
    return j;
}

5. 简化swap函数（可选） #

你的swap函数逻辑没问题，但可以去掉引用参数，简化实现：

static void swap(int arr[], int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

二、替换为高精度计时 #

clock()精度有限，用C++11的std::chrono库可以实现纳秒级计时，替换main函数中的计时部分：

// 快速排序计时
auto start_time = std::chrono::high_resolution_clock::now();
quickSort(arrC1, 0, size - 1);
auto end_time = std::chrono::high_resolution_clock::now();

// 计算毫秒级耗时
auto ms_duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time);
// 计算纳秒级耗时
auto ns_duration = std::chrono::duration_cast<std::chrono::nanoseconds>(end_time - start_time);

cout << "\nTime Elapsed (ms): " << ms_duration.count();
cout << "\nTime Elapsed (ns): " << ns_duration.count();

修复后的核心代码片段 #

static void swap(int arr[], int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

int partition(int arr[], int start, int end) {
    int mid = start + (end - start) / 2;
    if (arr[mid] < arr[start]) swap(arr, start, mid);
    if (arr[end] < arr[start]) swap(arr, start, end);
    if (arr[end] < arr[mid]) swap(arr, mid, end);
    swap(arr, start, mid);
    
    int pivot = arr[start];
    int i = start + 1;
    int j = end;

    while (i <= j) {
        while (i <= j && arr[i] < pivot)
            i++;
        while (i <= j && arr[j] > pivot)
            j--;
        if (i < j)
            swap(arr, i, j);
        else
            break;
    }
    swap(arr, start, j);
    return j;
}

void quickSort(int arr[], int start, int end) {
    while (start < end) {
        int p = partition(arr, start, end);
        if (p - start < end - p) {
            quickSort(arr, start, p - 1);
            start = p + 1;
        } else {
            quickSort(arr, p + 1, end);
            end = p - 1;
        }
    }
}

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