我想针对这个给定的问题再次提出：
考虑随机快速排序算法的一种变体，其中随机选择枢轴，直到以较低的子数组L和较大的子数组G包含数组元素的3/4。例如，如果随机选择的枢轴对数组进行分区，以使L包含1/10的元素，然后再包含另一个枢轴是随机选择的。分析该算法的预期运行时间。
起初，我把这个问题当作只是一个常规的快速排序问题，并在以下位置重复出现：
T(n) = T(3/4n) + T(n/4) + Θ(n) (where Θ(n) comes from the partition)
如果我们有一个算法总是将拆分始终为1/4：3/4，这是很有意义的。但是我们在这里使用随机旋转，每当不满足分配条件时旋转旋转。我知道随机快速排序的最坏情况运行时间仍为O（n ^ 2），但我认为在这种情况下，最坏情况现在有所不同（比O（n ^ 2）还差）。到目前为止，我走在正确的轨道上吗？
快速排序的时间复杂度永远不会超过O(n^2)，除非您选择一些需要花费O(n)时间来选择枢轴的逻辑。