快速排序的时间复杂度为什么是nlogn

就平均情况而言，快速排序是目前被认为最好的一种内部排序方法，其时间复杂度在平均情况下是nlogn，在最坏的情况下（有序时）时间复杂度是o(n^2)。下面来分析时间复杂度的计算过程：

平均情况下：T(n)=2*T(n/2)+n;      第一次划分

      =2*（2*T(n/4)+n/2）+n;     第二次划分  (=2^2*T(n/4)+2*n)

      =2*(2*(2*T(n/8)+n/4)+n/2)+n;     第三次划分(=2*3*T(n/8)+3*n)

      =.....................

      =2^m+m*n;  第m次划分

因为2^m=n,所以等价于 = n+m*n
所以m=logn，所以T(n)=n+n*logn;