我正在自学 CLRS 第 3 版，这是我遇到的更棘手的问题之一及其答案，作为对所有人的服务。
7.4-5
我们可以通过利用
当其输入“接近”排序时，插入排序的快速运行时间。打电话时
对元素少于 k 的子数组进行快速排序，让它简单地返回而不返回
对子数组进行排序。在对快速排序的顶级调用返回后，运行插入排序
在整个数组上完成排序过程。争论这个排序算法
在 O(nk+nlg(n/k)) 预期时间内运行。我们应该如何选择k，理论上都是
在实践中？
最佳答案
如果你计算方程 nlgn > nk + nlog(n/k) 你会得到 log k > k。这是不可能的。所以理论上是不可能的。但在实践中，插入排序和快速排序涉及常数因素。查看此 pdf 中讨论的解决方案.您可能想要更新您的答案。 .
关于algorithm - 快速排序和插入排序混合预期运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9564200/