快速排序的时间复杂度与空间复杂度

我们来分析一下快速排序法的性能。

快速排序的时间性能取决于快速排序递归的深度，

可以用递归树来描述递归算法的执行情况。

如图9‐9‐7所示，它是{50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是50，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。

在最优情况

Partition每次都划分得很均匀,如果排序n个关键字，其递归树的深度就为 log ⁡ 2 ( 2 n + 1 ) , 节 点 个 数 为 n \log_2(2n+1),节点个数为n log2​(2n+1),节点个数为n 例如2个节点，深度为2.

第一次Partiation应该是需要对整个数组扫描一遍，做n次比较。

获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半） 分 成 2 块 ： T （ n ） ≤ 2 T （ n / 2 ） + n ， T （ 1 ） = 0 , 其 中 n = ( log ⁡ 2 2 ) × n 分成2块：T（n）≤2T（n/2） +n，T（1）=0,其中n=(\log_22)\times n 分成2块：T（n）≤2T（n/2）+n，T（1）=0,其中n=(log2​2)×n 不断地划分下去，我们就有了下面的不等式推断 分 成 4 块 ： T （ n ） ≤ 2 （ 2 T （ n / 4 ） + n / 2 ） + n = 4 T （ n / 4 ） + 2 n , 其 中 2 n = ( log ⁡ 2 4 ) × n 分成4块：T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+2n,其中2n=(\log_24)\times n 分成4块：T（n）≤2（2T（n/4）+n/2）+n=4T（n/4）+2n,其中2n=(log2​4)×n

分 成 8 块 ： T （ n ） ≤ 4 （ 2 T （ n / 8 ） + n / 4 ） + 2 n = 8 T （ n / 8 ） + 3 n … … 分成8块：T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+3n …… 分成8块：T（n）≤4（2T（n/8）+n/4）+2n=8T（n/8）+3n……

分 成 n 块 ： T （ n ） ≤ n T （ 1 ） + （ log ⁡ 2 n ） × n = O ( n log ⁡ 2 n ) 分成n块：T（n）≤nT（1）+（\log_2n）×n= O(n\log_2n) 分成n块：T（n）≤nT（1）+（log2​n）×n=O(nlog2​n)

也就是说，在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。

最坏的情况，

待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。

此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为

最终其时间复杂度为O(n^2)。

平均的情况

设枢轴的关键字应该在第k的位置（1≤k≤n），那么： T ( n ) = 1 n ∑ k = 1 n ( T ( k − 1 ) + T ( n − k ) ) + n = 2 n ∑ k = 1 n T ( k ) + n T(n)=\frac{1}{n}\sum_{k=1}^{n}({T(k-1)+T(n-k))+n}=\frac{2}{n}\sum_{k=1}^{n}{T(k)+n} T(n)=n1​k=1∑n​(T(k−1)+T(n−k))+n=n2​k=1∑n​T(k)+n 空间复杂度，

主要是递归造成的栈空间的使用，最好情况，递归树的深度为 l o g 2 n log_2n log2​n 其空间复杂度也就为 O(logn)，

最坏情况，

需要进行n‐1递归调用，其空间复杂度为O(n)，

平均情况，

空间复杂度也为O(logn)。

可惜的是，由于关键字的比较和交换是跳跃进行的，因此，

快速排序是一种不稳定的排序方法。

参考自：快速排序最好，最坏，平均复杂度分析

补充： 文本与公式书写使用typora，但是typora不支持公式左对齐，所以写出来比较难看。 另外，csdn的markdown 界面不够好看。