快速排序递归为什么还要用栈
发布网友
发布时间：2022-04-23 19:21
共2个回答
热心网友
时间：2023-08-01 14:22
首先清楚的是：只要发生函数的调用，肯定需要栈来保存调用函数当前的执行状态等信息。
快速排序是递归的，排序过程中会不断调用自身（作为函数参数，待排序序列的长度在缩短），所以需要借助工作栈来保存每次递归调用的必要信息。
栈的容量：
①最好的情况是：每次PivotPos都在序列的中间，栈深=Dlog₂(n+1)E；
②最坏的情况是：每次PivotPos都在序列的两端，栈深=n-1。
热心网友
时间：2023-08-01 14:23
我看到的快排代码都是用递归实现的，函数递归需要用到栈（虽然这部分对用户是透明，但确实用到了栈）。
