Rah*_*bey 2 sorting algorithm performance quicksort data-structures
在Worst案例中,Quicksort递归深度需要O(n)的堆栈空间.为什么在最坏的情况下它不会导致大型集合的堆栈溢出？(逆序)
如果你在枢轴的两侧递归,那么在最坏的情况下它会导致堆栈溢出以获得足够大的数据.这就是为什么没有人在生产代码中使用天真的QuickSort.
您可以对算法进行简单的更改,以防止Omega(n)最坏情况下的堆栈使用.在每个分区之后,递归地Quicksort"小半部分",然后迭代地循环以执行"大半部分".这需要O(log n)额外的堆栈空间.如果您愿意,可以通过再次修改它来使O(1)堆栈空间和O(log n)额外的非堆栈空间.将"大半部分"推到预先分配的数组(或您选择的其他后进先出数据结构)的末尾,循环执行"小半部分",当您点击底部弹出最后一个关闭数据结构的元素.
您可以进行进一步的更改以避免Omega(n^2)最坏情况的运行时.但是,它不再是一个天真的QuickSort,它是一个QuickSort-with-medien-pivot-pivot-selection,或者是一个Introsort,或者其他什么.