快速排序中三个分区的中位数如何提高大约5%的效率？

Question

最近我正在学习算法。本书是Mark Allen Weiss的“C中的数据结构和算法分析”。

当我阅读快速排序部分时，书中说三个分区的中位数将提高快速排序效率约5%。5%是从哪里来的？有人能帮我一把吗？

Answer 1

这个问题将其归因于Robert，但没有给出解释。

在此页上，您将看到几种排序方法的讨论，包括带和不带三个中间值的快速排序方法。

下面是一个名为“经验结果”的表格，不难发现5%的改进。考虑到对所有可能的输入进行分析的巨大复杂性，我认为可以肯定地说，Sedgewicks的断言也是基于测量的。