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

快速排序的时间复杂度为O(nlogn)。

快速排序是一种分治算法，其基本思想是通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小。然后再分别对这两部分记录进行排序，从而达到整个序列有序的目的。

在快速排序算法中，每一趟排序都会选择一个基准元素（pivot），将所有小于等于基准元素的元素放在基准元素的左边，将所有大于基准元素的元素放在基准元素的右边。这样，每一趟排序后，基准元素就处于其最终的位置上。

因此，快速排序的时间复杂度可以通过递推关系式来推导。设n表示待排序序列的长度，T(n)表示快速排序的时间复杂度，则有：

T(n) = 2T(n/2) + O(n)

其中2T(n/2)表示对两个子序列进行排序的时间复杂度，O(n)表示将两个子序列合并的时间复杂度。

根据主定理（Master Theorem）可知，对于递推关系式T(n) = aT(n/b) + f(n)，其中a>=1，b>1，f(n)是一个多项式函数，如果存在正常数ε，使得f(n) = O(n^logb(a-ε))，那么：

对于快速排序算法，a=2，b=2，f(n)=O(n)。由于log2(2) = 1，因此logb(a) = 1。根据上述主定理的第2条情况可知，T(n) = Θ(nlogn)。

因此，快速排序的时间复杂度为O(nlogn)。