快速排序时间复杂度

快排的时间复杂度计算有很多种方法，规范的有数学主定理公式进行证明。这里简单通俗讲下O(n*logn)复杂度是怎么得出的。

在最优情况下，快排的每次划分都很均匀，假设有n个关键字，完整的排序需要T(n)时间，则一次划分需要对整个数组进行扫描，做n次比较，然后将数组一分为2，各自还需要T(n/2)的时间。

于是就有了下面的不等式：

T（n）≤2T（n/2） +n，T（1）=0  
T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+2n  
T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+3n  
……  
T（n）≤nT（1）+（log2n）×n= O(nlogn)

也就是说，在最优的情况下，快速排序算法的时间复杂度为O(n*logn)。
再来看看最坏的情况，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，另一个为空。
时间复杂度为:

(n-1)+(n-2)+...+1=n(n-1)/2= O(n2)

因此，如果关键字序列是大部分有序的情况，不推荐使用快排。