STL std::sort() 使用了 Introsort，但它是如何工作的？

Question

我不太了解 Introsort 算法。如您所见，我添加了它的伪代码。最大深度是什么意思？

“⌊log(length(A))⌋ × 2”是什么意思

希望有人能给我解释一下。

 procedure sort(A : array):
        let maxdepth = ⌊log(length(A))⌋ × 2
        introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
    if n ≤ 1:
        return  // base case
    else if maxdepth = 0:
        heapsort(A)
    else:
        introsort(A[0:p], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)

Answer 1

关于 ⌊log(length(A))⌋ × 2 的问题，⌊...⌋ 位仅表示 floor，小于或等于该值的最高整数。

用较少数学的语言，它将是 int(log(length(A))) * 2。

以防万一有人提出 floor（向 -∞ 舍入）和 int（向 0 舍入）之间的区别，这里无关紧要，因为长度必须是 non-negative 整数。如果长度为零，你仍然会运行陷入数学上的麻烦，但这是一个例外情况，因为它可能不需要排序:-)

至于为什么 maxdepth存在，这显然是一种基于树的算法-使用log也支持这一点，因为a的深度平衡树趋于与其中节点数的对数成正比。

似乎正在发生的事情是，如果 introsort 超出了某个深度，它只会切换到剩余部分的堆排序。

而且，只有一个小注意事项：std::sort() 不是使用 Introsort 所必需的（正如您的标题似乎暗示的那样），标准要求的行为例如 至多Nlog<sub>2</sub>N次比较，其中N=last-first但除此之外对算法选择没有要求。

STL std::sort() 使用了 Introsort，但它是如何工作的？

STL std::sort() uses Introsort, but how does it work?

c++

sorting

stl

introsort