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

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

时间复杂度o(nlogn)的算法是采用“分治思想”，将要排序的数组从中间分成前后两个部分，然后对前后两个部分分别进行排序，再将排序好的两部分合并在一起，这样数组就有序。

每次划分区域都选择中间点进行划分，所以递归公式可以写成：T(n) = T(n/2) + T(n/2) + n， T(1) = C(常数)    //每次合并都要调用Merge()函数，时间复杂度为O(n)，等价T(n) = 2kT(n/2k) + k * n， 递归的最终状态为T(1)即友搭n/2k = 1，所以k = log2n。

原理分析：

1、运用了分治的思想。选取分区值，将待排序列分为两个前后两部分，前部分数据元素的值小于等于分区值，后部分的数据元素的逗枯值大于等于好指拿分区值；继续对前后两部分分别进行分区，直到分区大小为1。

2、交换 *** 作的执行次数可以由时间复杂度分析过程得出，Merge()中总的交换次数为n * logn，因为不管两个子序列的大小，子序列中的各个元素都会先放入临时数组temp中，再重新放回原序列；比较 *** 作的次数小于等于交换 *** 作次数，最大交换次数为n * logn。

---