如何构造输入使快速排序运行时间符合Θ(T(n))（nlogn≤T(n)≤n²）

先明确我们要解决的核心命题：

对于任意满足Ω(nlogn)且O(n²)的运行时间T(n)，存在快速排序的输入序列，使其运行时间增长为Θ(T(n))。

目前我们已经完成了两个边界情况的证明：

• 用主方法验证了：当输入是长度为n的有序序列时，快排的运行时间为Θ(nlogn)
• 用代入法验证了：当输入数组全为相同元素时，快排的运行时间为Θ(n²)

接下来我们尝试用主方法的第三种情况来拓展到一般情况——也就是递推式 S(n)=aS(n/b)+f(n) 中，运行时间由f(n)主导的场景。我们的初步思路是直接令T(n)=f(n)，但这里碰到了一个绕不开的障碍：没办法保证每次递归都能把问题规模稳定缩小到原规模的固定分数比例。毕竟快排的子问题大小完全由pivot的选择决定，如果没法稳定地把数组切分成固定比例的两部分，主方法的适用前提就不成立，这个思路也就没法继续推进下去。

内容的提问来源于stack exchange，提问作者Addem