0

我正在尝试了解 introsort 并找到稀缺的资源。我的理解是它使用快速排序，但是当递归变得很深时切换到堆排序。这是因为快速排序通常比堆排序快，除非调用深度变得很深。

我的问题是，切换到堆排序之前的深度是如何计算的？维基百科有floor(log(length_of_data))x2，但我见过其他的东西。原因是什么？我是否正确的算法想要坚持使用快速排序，直到由于内存原因需要切换到堆排序？

4

1 回答 1

0

我已经看到范围从 ~ 1.5 * log2(n) 到 ~2.0 * log2(n) 的深度限制。这样做是为了避免 O(n^2) 的最坏情况时间复杂度，而不是出于空间原因。

通过使用循环和递归的组合，可以将空间复杂度限制为 O(log2(n))，仅在每个分区的较小“一半”上使用递归，然后循环返回以拆分较大的分区并继续该过程。环回还减少了深度计数器，因为它被用来替换另一个级别的递归。

于 2016-10-11T07:31:24.123 回答