performance - 快排递归深度O(n)的栈空间不会造成stackoverflow？

Question

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

Answer 1

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

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

您可以进行进一步的更改以避免 Omega(n^2) 最坏情况下的运行时。但它不再是简单的 QuickSort，它是一个 QuickSort-with-median-of-medians-pivot-selection，或 Introsort，或其他什么。