问题描述
所以快速排序的空间效率为O（日志（N））。这是为了维持调用堆栈所需的空间。
So the space efficiency of Quicksort is O(log(n)). This is the space required to maintain the call stack.
现在，根据对快速排序的维基百科页面，这有资格作为一个原地算法，因为算法只是调换输入数据结构内的元素
Now, according to the Wikipedia page on Quicksort, this qualifies as an in-place algorithm, as the algorithm is just swapping elements within the input data structure.
然而，根据该页面，O（log n）的空间效率快速排序不够格从到位，因为它的空间利用率大于O（1）。根据该定义的任何算法以比O空间效率更高的（1）是不同的地方。所以，我认为这意味着所有的递归算法被定义不到位？
According to this page however, the space Efficiency of O(log n) disqualifies Quicksort from being in place, as it's space efficiency is greater than O(1). According to this definition any algorithm with space efficiency greater than O(1) is not in-place. So I assume this means that all recursive algorithms are by definition not in place?
所以，很显然也有就地这里有两个不同的定义。维基百科并不总是一个完全可靠的来源，所以我咨询了我的教授之一。
So obviously there are two different definitions of in-place here. Wikipedia is not always an entirely reliable source, so I consulted with one of my professors.
我的教授同意第二个定义。他说，快速排序不是就地。即使数据保持输入数组中，所需要的堆栈中的额外的空间不够格它。我的教授写了一本畅销书的算法，所以我尊重他的意见很大，但这个答案似乎并不正确的给我。
My professor agreed with the second definition. He said Quicksort is not in-place. Even though the data remains in the input array, the extra space needed for the stack disqualifies it. My professor wrote a popular book on Algorithms so I respect his opinion greatly, but this answer just does not seem correct to me.
我看到在位的财产是相当的文字。该数据仍留在原位。它不会从它的原始数据结构移动。对我来说，这个定义是比较有用的，因为这意味着你可以使用指针执行需要你复制的数据你的算法来代替。这似乎是一个算法的宝贵财产，无愧于就地的美称。
I see the property of in-place as being quite literal. The data stays in place. It does not move from it's original data structure. To me, this definition is more useful, because it means you can perform your algorithm with pointers instead of requiring you to copy data. This seems like a valuable property of an algorithm and worthy of the name "in-place".
推荐答案
简介算法来自MIT preSS资格快速排序为就地的 - 它排序与阵列中的元素的至多的它们中的任何给定时间的恒定量的阵列外部。
Intro to Algorithms from MIT Press qualifies QuickSort as in-place - it sorts the elements within the array with at most a constant amount of them outside the array at any given time.
在一天结束的时候，人们总会有不同的意见（是自顶向下的记忆化考虑动态规划？不给一些经典的人），方用谁，你最信任的人。我相信编辑和作者在麻省理工学院preSS（连同我的教授，谁限定它为就地）。
At the end of the day, people will always have differing opinions (is Top-Down Memoization considered Dynamic Programming? Not to some "classical" folks), side with who you trust the most. I trust the editors and the authors at MIT Press (along with my professor, who qualifies it as in-place).
典型地，对于快速排序的问题不在于它不就地排序，但它不是的稳定的 - 卫星数据没有保存在顺序
Typically, the problem with QuickSort is not that it doesn't sort in-place, but that it is not stable - satellite data is not kept in order.
修改
这种说法我觉得黑井的角度黑体字部分是非常重要的。
Kuroi's point highlights part of this argument I think is very important.
许多人认为，它需要递归调用为O（log（n））的额外内存，数据被泄露在栈上的指数的形式，然而，这是微不足道的非常大的大小的N（日志（10亿） =〜30），它忽略了一般移动数据堆中花费，更长的时间，事实上，当大小（数据）>>的大小（指数）。
Many argue that it requires O(log(n)) extra memory for recursive calls and the data is leaked in the form of the indices on the stack, however this is negligible for very large sizes of N (log(1,000,000,000) =~ 30) and it ignores the fact that typically moving data on the heap takes much, much longer, when size(data) >> size(index).
是数据的索引而非元件本身。 - 这样的数据元素没有保存在数组外，比他们的恒定量的其他（在每个呼叫）
The indices of the data are not the elements themselves - so the elements of the data are not stored outside the array, other than a constant amount of them (in each call).
这篇关于是快速排序就地或不？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！