直观证明
1.划分点按照1：9划分时，用递归树分析时间复杂度：
T（n）=T(n/10)+T(9n/10)+O(n)
不难得出：对于任意划分只要是常数倍数的，不管是1:99,1:999,1:9999，只要不是1：(n-1) ,我们的时间复杂度都是O(nlogn)。
2.在平均情况下，好的划分（常数比例划分）和坏的划分（1:n-1）是平均出现在划分树上的，当好、差划分交替在各层时，快排的运行时间就如全是好的划分一样，为θ(nlgn).
以上图a) 、b)为例，运行时间递推式都为T(n)=2T（n/2）+O(n)
参考：算法导论7.2
公式证明
转自知乎
注：Hn为调和数 Harmonic Number
参考：https://www.zhihu.com/question/22393997
