快速排序（Quick sort）是否属于原地算法（in-place）？

其实这个争议的核心在于in-place算法的定义边界，不同资料的表述差异主要来自对「额外空间」的判定标准，咱们拆解来看：

• 那个Stack Overflow回答的视角：它把递归调用产生的栈空间也算作了算法的额外空间。快速排序的递归调用在最坏情况下（比如数组已经有序时）深度是O(n)，这部分栈帧占用的空间如果被严格纳入“辅助空间”的范畴，那确实会被判定为非in-place算法。
• MIT课程的视角：这也是算法界的主流认知——in-place算法的核心判定是是否需要开辟与输入规模同量级的额外辅助数据结构（比如另一个数组）。递归调用的栈空间属于程序调用栈的隐式开销，不算作算法本身主动申请的辅助空间。我们平时实现的原地快速排序，都是在原数组上通过指针交换元素完成分区，完全不需要额外开辟数组存储中间结果，符合in-place算法的核心特征。

结论 #

主流算法界的共识是：快速排序属于in-place算法。如果纠结递归栈的问题，我们还可以通过尾递归优化或者迭代实现的方式，把递归栈的空间开销降到O(logn)（平均情况）甚至常数级，进一步贴合in-place的定义。

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