快速排序递归深度 O(n) 的堆栈空间不会导致堆栈溢出？

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

如果在枢轴的两侧进行递归，那么在最坏的情况下，它确实会导致足够大的数据的堆栈溢出。这就是为什么没有人在生产代码中使用简单的快速排序。

您可以对算法进行一个简单的更改来防止Omega(n)最坏情况下的堆栈使用。在每个分区之后，递归地快速排序“小一半”，然后迭代循环以完成“大一半”。这需要O(log n)额外的堆栈空间。如果你愿意，你可以做到O(1)堆栈空间和O(log n)通过再次修改此值来增加额外的非堆栈空间。将“大一半”推到预分配数组（或您选择的其他后进先出数据结构）的末尾，循环执行“小一半”，当您到达底部时弹出最后一个元素关闭数据结构下一步要做的事情。

您可以进行进一步的更改来避免Omega(n^2)最坏情况下的运行时间。但它不再是一个简单的快速排序，它是一个带有中位数的中位数枢轴选择的快速排序，或者是一个Introsort，或者其他什么。