什么时候从快速排序introsort转移到堆排序？ [英] When does introsort shift from quicksort to heapsort?

问题描述

Introsort ，并开始快速排序和交换机时，递归深度超过基于A级到堆排序被排序的元素数量。那是什么号码？是否有一个具体的范围或限制值？

Introsort begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on the number of elements being sorted. What is that number? Is there a specific range or a limiting value?

推荐答案

该点时的的 Introsort算法交换机从快速排序到堆排序由以下因素决定的 depth_limit 的：

The point at which the Introsort algorithm switches from Quicksort to Heapsort is determined by depth_limit:

depth_limit = 2·⎣log ₂ （→的）⎦

depth_limit = 2 · ⎣log₂(l)⎦

其中升的是序列是要排序的长度，所以升 = N 的整个序列。每次递归调用的 depth_limit 的减一。当 depth_limit 的到达0，从快速排序切换到堆排序。

Where l is the length of the sequence that is to be sorted, so l‍=‍n for the whole sequence. With each recursive call depth_limit is decremented by one. When depth_limit reaches 0, it switches from Quicksort to Heapsort.

这篇关于什么时候从快速排序introsort转移到堆排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！