c++ - 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 舍入)，这里无关紧要，因为长度必须是非负整数。如果长度为零，你仍然会遇到数学问题，但这是一个异常(exception)情况，因为它可能不需要排序:-)

---

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

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

---

而且，只有一个小注释:std::sort() 不需要使用 Introsort(正如您的标题似乎暗示的那样)，标准要求行为，例如 at most Nlog<sub>2</sub>N comparisons, where N=last-first但除此之外对算法选择没有要求。