一尘不染

Introsort什么时候从quicksort转变为heapsort?

algorithm

Introsort从quicksort开始,并在递归深度超过基于要排序的元素数量的级别时切换到堆排序。那是几号
是否有特定范围或极限值?


阅读 203

收藏
2020-07-28

共1个答案

一尘不染

在该点内省排序算法从快速排序切换到堆排序由下式确定
depth_limit

depth_limit = 2·⎣log 2( )⎦

其中 是要被排序的序列的长度,所以 = Ñ 整个序列。对于每个递归调用, depth_limit 都会减一。当
depth_limit 达到0时,它将从Quicksort切换到Heapsort。

2020-07-28