在最坏的情况下，快速排序递归深度需要O（n）的堆栈空间。为什么它不会引发大集在最坏情况下堆栈溢出？ （颠倒顺序）

In Worst case Quicksort recursion Depth requires Stack space of O(n). Why it doesn't cause a stack overflow for large set in the worst case? (reversed sequence)

推荐答案

如果您递归在枢轴的两侧然后它确实产生堆栈溢出为在最坏的情况下足够大的数据。这就是为什么没有人使用的生产code天真的快速排序。

If you recurse on both sides of the pivot then it does cause stack overflow for sufficiently large data in the worst case. That's why nobody uses a naive QuickSort in production code.

有一个简单的变化，你可以对算法prevent 欧米茄（N）最坏情况下的堆栈使用。每个分区后，递归快速排序的小半，然后反复地循环身边做大半壁江山。这就要求 O（log n）的额外的堆栈空间。如果你愿意，你可以把它 O（1）堆栈空间和 O（log n）的额外的非再次修改此堆栈空间。按大半壁江山到pre-分配的数组的末尾（或其他后进先出您所选择的数据结构），环周围做了小半，当你触底弹出最后一个元素关数据结构下一步。

There is a simple change you can make to the algorithm to prevent Omega(n) worst-case stack use. After each partition, recursively Quicksort the "small half" and then iteratively loop around to do the "big half". This requires O(log n) additional stack space. If you want to, you can make it O(1) stack space and O(log n) additional non-stack space by modifying this again. Push the "big half" onto the end of a pre-allocated array (or other last-in-first-out data structure of your choice), loop around to do the "small half", and when you hit bottom pop the last element off the data structure to do next.

有进一步的改变，你可以避开欧米茄（N ^ 2）最坏情况下的运行时间。但是，那就不是一个天真的快速排序更多，这是一个快速排序与 - 中位数的中位数支点选择，或Introsort，或什么的。

There are further changes you can make to avoid Omega(n^2) worst-case runtime. But then it's not a naive QuickSort any more, it's a QuickSort-with-median-of-medians-pivot-selection, or an Introsort, or whatever.