时间复杂度为O(nlogn) n为元素个数
1. 快速排序的三个步骤:
1.1. 找到序列中用于划分序列的元素
1.2. 用元素划分序列
1.3. 对划分后的两个序列重复1,2两个步骤指导序列无法再划分
所以对于n个元素其排序时间为
T(n) = 2*T(n/2) + n (表示将长度为n的序列划分为两个子序列,每个子序列需要T(n/2)
的时间,而划分序列需要n的时间)
而 T(1) = 1 (表示长度为1的序列无法划分子序列,只需要1的时间即可)
T(n) = 2^logn + logn * n (n被不断二分最终只能二分logn次(最优的情况,每次选取
的元素都均分序列))
= n + nlogn
因此T(n) = O(nlogn)
以上是最优情况的推导,因此快速排序在最优情况下其排序时间为O(nlogn),通常平均情况
我们也认为是此值。
在最坏情况下其会退化为冒泡排序,T(n) = T(n - 1) + n (每次选取的元素只能将序列划分为
一段,即自身是 最小元素或最大元素)
因此T(n) = n * (n-1) / 2 相当于O(n^2)
追问n被不断二分最终只能二分logn次 什么意思?
追答在最优的情况下,即每次二分序列时都将序列平均的分为两部分,此时n被不断二分最终只能二分logn次。
即起始为n,第一次分为两个n/2,第二次分为四个n/4...第m次分为2^m个1,
意思就是在最优的情况下对n进行二分时最多二分m次即会出现2^m个全为1的序列。
所以此时2^m * 1 = n 因此显然m=logn。
推倒方式如下:
T(n) = 2*T(n/2) + n
T(n) = 2 * (2 * T(n/4) + n/2) + n
......
T(n) = 2^mT(1) + mn
其中m即等于logn,所以T(n) = nT(1) + nlogn = n + nlogn