Introsort从快速排序开始，当递归深度超过基于被排序元素数量的级别时，切换到堆排序。那个号码是多少？是否有特定范围或限制值？
问问题
4708 次
2 回答
8
Introsort算法从 Quicksort 切换到 Heapsort 的点由depth_limit确定：
depth_limit = 2 · ⎣log 2 ( l )⎦</p>
其中l是要排序的序列的长度，所以l =<em>n 代表整个序列。每次递归调用depth_limit减一。当depth_limit达到 0 时，它会从 Quicksort 切换到 Heapsort。
于 2012-06-24T07:13:44.750 回答
2
我刚刚尝试阅读介绍性的Wikipedia 文章。它说
它计算递归深度。如果超过对数深度，算法会从 Quicksort 切换到 Heapsort，以保持 Quicksort 的最坏情况结果下降
并通过 Musser 关于 Introsort 的原始论文。
它说 introsort 比 heapsort 慢，因为它在切换到 heapsort 之前执行 2*log(2,N) 计算。
我的理解是递归深度是 2*log(2,N)
对于要排序的 N=300 个元素，它将是 2*8 = 16
于 2012-06-24T07:16:25.620 回答