为什么QuickSort使用O（log（n））额外空间？
我已经实现了以下快速排序算法。 在线我已经读过它的空间要求为O（log（n））。 为什么会这样？ 我没有创建任何额外的数据结构。
是因为我的递归会在堆栈上使用一些额外的空间吗？ 如果是这种情况，是否可以通过不使用递归（而是使其迭代）来减少内存？
private static void quickSort (int[] array, int left, int right) { int index = partition(array, left, right); //Sort left half if (left < index - 1) quickSort(array, left, index - 1); //Sort right half if (index < right) quickSort(array, index , right); } private static int partition (int array[], int left, int right) { int pivot = array[(left + right) / 2]; //Pick pivot point while (left <= right) { //Find element on left that should be on right while (array[left] pivot) right--; //Swap elements and move left and right indices if (left <= right) { int temp = array[left]; array[left] = array[right]; array[right] = temp; left++; right--; } } return left; } 正确，额外的空间是log（n）堆栈帧。 来自维基百科的Quicksort文章 ：
有一个更复杂的版本，它使用就地分区算法，并且可以使用平均（对于调用堆栈）使用O（log n）空间（不计入输入）来实现完整排序。
虽然你可以迭代地实现快速排序（即，使用循环而不是递归），然后你需要维护一个辅助堆栈，因为Quicksort有两个递归调用而不只是一个。
最后，正如其他答案所指出的那样，O（log（n））几乎所有实际应用都非常非常小。 每个常量因素（如数据结构的开销）都会对内存使用产生更大的影响。
要摆脱递归调用，您必须在代码中使用堆栈，它仍然会占用log(n)空间。
如果您在维基百科文章中进一步阅读，您会发现有关空间复杂性的更全面的讨论 。 他们特别写道：
具有就地和不稳定分区的Quicksort在进行任何递归调用之前仅使用恒定的额外空间。 Quicksort必须为每个嵌套的递归调用存储恒定数量的信息。 由于最佳情况最多使O（log n）嵌套递归调用，因此它使用O（log n）空间。 但是，如果没有Sedgewick限制递归调用的技巧，在最坏的情况下，quicksort可以进行O（n）嵌套递归调用并需要O（n）辅助空间。
实际上，O（log n）内存不算什么。 例如，如果你要排序10亿个int，那么存储它们需要4 GB，但是堆栈只需要大约30个堆栈帧，大约40个字节，所以总共大约1200个字节。
是的，这是因为堆栈帧，是的，有可能通过做一些非常聪明的事情将它转换为迭代算法（虽然没有什么东西立即出现在我身上）。 但为什么？ O（log（n））空间几乎没有。 作为参考，即使你有一个Java允许的最大大小的数组，也就是2 ^ 31个元素，大约是8 GB。 Quicksort需要31个堆栈帧。 棒球场，每帧可能100个字节？ 总共3 KB，与实际arrays的内存相比没什么。
实际上，几乎任何时候都是O（log（n）），它与常数几乎相同。
很抱歉恢复这个老问题，但我刚刚在planetmath.org上找到了一个完全不同（但有些愚蠢）的问题答案：
在连续数组上运行的任何排序算法都需要O （ logn ）额外空间，因为这是表示数组索引所需的bite [ sic ]数。