2

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

4

3 回答 3

6

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

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

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

于 2012-10-19T09:12:43.493 回答
2

那么为什么在最坏的情况下它不会导致大量有序数据的堆栈溢出

确实如此。为什么你会认为它没有？

（但请注意，快速排序的最坏情况输入取决于您选择的枢轴。它通常不是反向序列 - 事实上，对于枢轴的天真选择，另一个最坏情况输入是已经排序的序列，它没有要反转。）

但是现在排序算法的库实现实际上很少是快速排序，正是因为这个原因。例如，C++std::sort使用introsort代替，这是一种修改过的快速排序，一旦递归太深，就会切换到不同的排序算法。

于 2012-10-19T09:11:49.983 回答
1

在顺序相反的情况下（最坏的情况），它可能会导致堆栈溢出。因为数组对于内部函数堆栈来说可能太大了。（例如 99,000,000 个元素）您可以将递归替换为stack数据结构。你会循环while (stck.empty() == false)

function quicksort(arr[0,1,...n-1])
     stack.push(pair(0, n - 1))
     while stack not empty
          interval = stack.pop()
          ...
          ...
          stack.push(interval(0, pivot - 1))
          stack.push(interval(pivot + 1, n - 1))
于 2012-10-19T08:57:25.017 回答