尽管快速排序需要O（log n）堆栈空间，但通常将它描述为 原位 （就地）算法。那么 ，原位 意味着“所需的额外空间少于O（n）”，还是堆栈空间通常不算作空间复杂度（但是为什么会这样呢？），或者Quicksort实际上不是 原位 算法吗？
Quicksort实际上不是原位算法吗？
它的标准实现 不是 就地的 。这是一个非常普遍的误解，但是您正确地注意到由于堆栈空间的消耗，这种概念是错误的。
我之所以说它的“标准实现”，是因为人们已经修改了该算法以使其成为O(1)-space算法。这是一个示例：不带堆栈的Quicksort。
O(1)
当然，与经典的时空权衡相一致，这种快速排序版本的性能要低于标准实现。
