c++ - Introsort (quicksort + heapsort) 实现和复杂度

Question

我读到 C++ 对其内置的 std::sort 使用 introsort(内省(introspection)排序)，它从快速排序开始，并在达到深度限制时切换到堆排序。

我还读到深度限制应该是 2*log(2,N)。

这个值纯粹是实验性的吗？或者它背后有一些数学理论？

Answer 1

如果你有一个区间(范围或数组)，在你得到一个空(或一个元素)区间之前你必须将区间分成两半的次数是 log(2,N) ，这只是一个数学事实，如果你愿意，你可以很容易地计算出来。如果快速排序一切顺利，它应该递归 log(2,N)次，出于同样的原因(并且在每个递归级别，它必须处理间隔的所有值，这导致整个算法的复杂度为 O(N*log(2,N)))。问题是快速排序可能需要更多的递归(如果它在选择枢轴值时一直“不走运”，这意味着它不会将间隔分成两半，而是以一种不平衡的方式)。更糟糕的是，快速排序最终可能会递归 N 次，这对于生产质量的实现来说绝对是 Not Acceptable 。

在 2*log(2,N) 切换到堆排序一般而言，这只是一个很好的启发式方法，可以检测到过多的递归。

从技术上讲，您可以根据堆排序与快速排序的经验性能来确定最佳限制。但是这样的测试高度依赖于应用程序(你在排序什么？你如何比较元素？元素交换有多便宜？等等)。所以，大多数一刀切的实现，比如 std::sort , 只会选择一个合理的限制，例如 2*log(2,N) .