所以快速排序的空间效率是O(log(n))。这是维护调用堆栈所需的空间。
现在，根据Quicksort 上的维基百科页面，这符合就地算法，因为该算法只是交换输入数据结构中的元素。
然而，根据此页面，O(log n) 的空间效率使快速排序无法到位，因为它的空间效率大于 O(1)。根据这个定义，任何空间效率大于 O(1) 的算法都不是就地的。所以我假设这意味着所有递归算法都没有按定义到位？
所以很明显这里有两种不同的就地定义。维基百科并不总是一个完全可靠的来源，所以我咨询了我的一位教授。
我的教授同意第二个定义。他说 Quicksort 没有到位。即使数据保留在输入数组中，堆栈所需的额外空间也会使其不合格。我的教授写了一本关于算法的流行书，所以我非常尊重他的意见，但这个答案对我来说似乎并不正确。
我认为就地的属性是相当字面的。数据保持不变。它不会脱离其原始数据结构。对我来说，这个定义更有用，因为它意味着您可以使用指针执行算法，而不是要求您复制数据。这似乎是算法的一个有价值的属性，并且配得上“就地”的名称。
MIT Press的算法简介将QuickSort 限定为就地- 它在任何给定时间对数组内的元素进行排序，最多在数组外进行固定数量的元素。
归根结底，人们总会有不同的意见（自上而下的记忆被认为是动态编程吗？对一些“经典”的人来说不是），站在你最信任的一边。我信任麻省理工学院出版社的编辑和作者（以及我的教授，他认为它是就地的）。
通常，QuickSort 的问题不在于它不能就地排序，而在于它不稳定——卫星数据没有保持有序。
编辑
Kuroi 的观点突出了我认为非常重要的这一论点的一部分。
许多人认为递归调用需要 O(log(n)) 额外内存，并且数据以堆栈索引的形式泄漏，但是对于非常大的 N (log(1,000,000,000) =~ 30 ) 并且它忽略了一个事实，即当 size(data) >> size(index) 时，通常在堆上移动数据需要更长的时间。
数据的索引不是元素本身 - 因此数据的元素不存储在数组之外，除了它们的恒定数量（在每次调用中）。
严格来说，快速排序的空间效率为 O(n)，因为退化的情况需要在堆栈上为数组的每个元素建立一个索引。虽然平均而言它将是 O(log(n))。鉴于我认为没有任何方法可以将其称为“就地”算法，除非您使用“就地”的退化定义，这意味着原始数据未存储在原始数组边界之外（不包括复制/交换操作）。
这种“就地”的定义将是退化的，因为您可以采用任何“不合时宜”的算法，并通过让它使用指向原始数组的所有额外数据存储来满足这种“就地”要求。然后，当找到答案时，您可以使用指针数据“就地”重新排序原始数组。
qsort 确实在原地交换数据，但用于递归的堆栈空间在 log 2 (N) 中。
这两个性质并不矛盾。通常“就地”是指堆内存，即您必须明确分配给算法工作的内存。
但是，对数空间复杂度基本上可以忽略不计，除非在病态情况下（例如，您想在具有 512 字节堆栈的 8 位微控制器上进行快速排序:)）。
这一切都取决于“就地”算法的定义。
如果您将“就地”定义为需要恒定数量的内存，则快速排序不是“就地”，因为它需要 log(N) 内存进行递归。
如果您将“就地”定义为更人性化的“不会将数据移动到输入结构之外”，那么快速排序又不是“就地”。数据以调用快速排序方法的索引的形式泄漏到内存，这是算法工作所必需的。这个额外内存的内容直接依赖于输入，怎么不泄露呢？
如果您将“就地”定义为不复制，那么查找数组总和的愚蠢算法怎么样：创建另一个长度为 (n - 1) 的数组，其中包含 b[i] = a[i + 1 ] + a[0] / n。这有点复制，虽然内容不同，但这个额外内存的内容是输入数据的函数，就像快速排序算法中堆栈上的索引一样。
我认为“就地”的维基百科定义是最有用的，根据它，快速排序不是“就地”，因为它使用非常量的内存。