递归调用快速排序时如何计算最大栈内存分配？

核心问题修正 #

你的代码里有两个关键问题导致无法正确计算最大栈内存：

• 局部maxmemory变量：每个递归调用都会重新初始化，根本没法记录全局最大值
• MEMORY只加不减：递归返回后栈帧会被释放，MEMORY必须减去对应内存才能反映当前真实栈使用量

修改后的代码 #

首先在函数外定义全局变量（确保所有递归调用共享状态）：

#include <algorithm> // 用标准库swap需要这个头文件

int MEMORY = 0;
int maxmemory = 0;
int headoperators = 0;
int SIDE_OPERATIONS = 0;

然后修改QuickSort函数：

void QuickSort(int* a, int n)
{
    int x, i, j; 
    // 定义当前栈帧的内存大小，你原来的7*sizeof(int)假设包含参数、局部变量和栈帧开销
    const size_t stack_frame_size = 7 * sizeof(int); 

    // 进入函数，栈内存增加当前帧的大小
    MEMORY += stack_frame_size;
    // 更新最大栈内存：如果当前总内存超过之前的最大值，替换
    if (MEMORY > maxmemory) {
        maxmemory = MEMORY;
    }

    x = a[n / 2];
    i = 0; j = n - 1; 
    do
    {
        while (a[i] < x) 
        {
            headoperators++;
            i++;
        }
        headoperators++;

        while (x < a[j]) 
        {
            headoperators++;
            j--;
        }
        headoperators++;

        SIDE_OPERATIONS++;
        if (i <= j) 
        {
            std::swap(a[i], a[j]); // 也可以自己实现swap函数
            i++;
            j--;
        }
        SIDE_OPERATIONS++;
    } while (i < j); 

    SIDE_OPERATIONS++;
    if (j > 0) 
        QuickSort(a, j + 1); 

    SIDE_OPERATIONS++;
    if (i < n - 1) 
        QuickSort(a + i, n - i); 

    // 函数退出，栈帧释放，减去当前帧的内存
    MEMORY -= stack_frame_size;
}

关键逻辑说明 #

1. 全局变量共享状态：把MEMORY和maxmemory设为全局，确保所有递归调用都操作同一个数值，这样才能跟踪整个递归过程中的内存变化和最大值。
2. 栈帧的增减对应：进入函数时加栈帧内存，退出时减，保证MEMORY始终等于当前递归栈的总内存使用量。
3. 实时更新最大值：每次增加栈内存后立即检查，只要当前总内存比maxmemory大，就更新maxmemory，这样就能记录递归过程中栈内存的峰值。

额外注意点 #

• 如果你不确定7*sizeof(int)的栈帧大小是否准确，可以改成更精确的计算：sizeof(int*) + sizeof(int) + 3*sizeof(int)（参数int* a、int n，加上局部变量x,i,j），如果要包含栈帧的隐藏开销（比如返回地址、栈基址），再加上对应字节数。
• 如果你不想用全局变量，也可以把maxmemory和MEMORY用static局部变量，但全局变量对新手来说更直观。

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