尽管quicksort需要o（log n）堆栈空间，但它通常被描述为一种原位（就地）算法。因此，就地意味着“需要小于O（n）的额外空间”，或者堆栈空间一般不被视为空间复杂性（但为什么会是这样？），或者快速排序实际上不是一个原位算法？
最佳答案
快速排序实际上不是一个原位算法吗？
它的标准实施并不到位。这是一个非常常见的误解，但是您应该正确地注意到，由于堆栈空间的消耗，这个概念是错误的。
我之所以说它是“标准实现”，是因为人们已经修改了算法，使其成为O(1)-空间算法。这里有一个例子：Quicksort without a stack。
当然，与经典的space-time tradeoff一致，这种quicksort版本的性能不如标准实现。
关于algorithm - 强制性Quicksort是否就地(就地)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9096787/