Intro排序(快速排序+堆排序)的实现和复杂性

Question

我读过，C++在内置的std：：排序中使用了内部排序(内省排序)，从快速排序开始，在达到深度限制时切换到堆排序。

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

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

Answer 1

如果您有一个区间(范围或数组)，那么在您得到一个空的(或一个元素)间隔之前，您必须将该间隔分割成两半的次数是log(2,N)，这只是一个数学事实，如果您愿意的话，可以很容易地计算出来。如果在快速排序方面一切都进行得很好，则应该基于同样的原因(在每个递归级别上，它必须处理间隔的所有值，从而导致整个算法的log(2,N)复杂性)。问题是，快速排序可能需要更多的递归(如果它一直在选择支点值时变得“不走运”，这意味着它不会将时间间隔分成两半，而是以一种不平衡的方式)。更糟糕的是，快速排序最终可能会递归N次，这对于生产质量的实现来说绝对是不可接受的。

在2*log(2,N)上切换到堆排序通常是一个很好的启发，可以检测到太多的递归。

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

Answer 2

@Mikael关于为什么深度限制为2*log(2，N)的说法部分是正确的。这不仅是一个好的启发，也不是一个合理的限制。

事实上，正如您可能已经猜到的(从您的第二个问题中描述的)，有一个重要的数学原因:在符号(搜索倾斜符号)中，~2*log(2，N)的比较是平均的。在大-哦表示法中，这相当于O(N*log(2，N))。

这就是为什么当递归的深度超过2*log(2，N)时，内向排序切换到堆排序(它具有渐近O(N*log(2，N))复杂性)。你可以把它看作是一些不常见的事情，而且很可能意味着，仅仅选择枢轴和快速排序就会导致O(N^2)复杂性。

您可以找到一个简单的数学证明，说明这里(幻灯片21)的平均比较数。