如何估算该快速排序算法的内存占用量？
2026-7-21
快速排序内存使用量估算指南
核心分析前提
你的代码实现了尾递归优化的快速排序：每次分区后仅递归处理较小的子数组，较大的子数组通过while循环迭代处理，这会大幅降低递归栈的最大深度，是估算的关键。
步骤1：计算单个递归栈帧的大小
递归栈中的每个帧对应一次quickSort函数调用，我们统计其参数与局部变量的内存占用（按主流64位系统为例，32位系统可类比换算）：
- 参数：
int arr[]：本质是指针，占8字节int low/int high：各4字节，共8字节- 3个
long long&引用：每个引用是指针，各8字节，共24字节
- 局部变量：
int pi，占4字节 - 内存对齐后（通常按8字节对齐），单个栈帧总大小约为48字节（未对齐时为44字节，估算时取对齐后值更准确）
32位系统下，指针/引用占4字节，单个栈帧对齐后约为32字节（未对齐28字节）。
步骤2：确定递归最大深度
由于小分区优先递归的优化，递归深度的最坏情况为O(log₂n)（n为数组元素个数），即每次递归的子数组大小最多为原数组的1/2，直到子数组长度为1。对应各数组的最大深度：
- 50k元素：
log₂(50000)≈15.6→ 向上取整为16层 - 100k元素：
log₂(100000)≈16.6→ 向上取整为17层 - 150k元素：
log₂(150000)≈17.2→ 向上取整为18层 - 200k元素：
log₂(200000)≈17.6→ 向上取整为18层
步骤3：计算总递归栈内存
单个栈帧大小 × 最大递归深度，结果如下：
64位系统
- 50k数组：
16 × 48 = 768字节（≈0.75KB） - 100k数组：
17 × 48 = 816字节（≈0.8KB） - 150k数组：
18 × 48 = 864字节（≈0.84KB） - 200k数组：
18 × 48 = 864字节（≈0.84KB）
32位系统
- 50k数组：
16 × 32 = 512字节 - 100k数组：
17 × 32 = 544字节 - 150k数组：
18 × 32 = 576字节 - 200k数组：
18 × 32 = 576字节
与数组内存的对比
int类型占4字节，各数组的内存占用为：
- 50k：
50000×4=200000字节（≈195KB） - 100k：
100000×4=400000字节（≈391KB） - 150k：
150000×4=600000字节（≈586KB） - 200k：
200000×4=800000字节（≈781KB）
显然，递归栈的内存占用远小于数组本身的内存，完全符合“计算结果不应超过数组维度”的要求。
内容的提问来源于stack exchange，提问作者deynchik
相关产品推荐
相关产品推荐
