快速排序的最好最坏时间复杂度

快速排序最坏时间复杂度和平均时间复杂度的区别是什么？

答：其中 ,是一趟快排需要的比较次数，一趟快排结束后将数组分成两部分 和. 最好时间复杂度: 核心点:最好情况下，每一次划分都正好将数组分成长度相等的两半. 最坏时间复杂度: 核心点:最坏情况下，每一次划分都将数组分成了0和n-1两部分. 平均时间复杂度: 核心点:任意一种划分情况出现的概率都相等. 所有的划分情况为：. 综上 :快速排序最好时间复杂度为 ,最坏时间复杂度为 ,平均时间复杂度为.

快速排序的时间性能取决于什么？

答：快速排序的 时间 性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。 最 好情况如图9‐9‐7所示，它是 {50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。

为什么快速排序比其他排序算法更有优势？

答：因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分割的平均。 这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。 这意味着，它比最坏情况较接近最好情况。 这个快速的平均运行时间，是快速排序比其他排序算法有实际的优势之另一个原因。 空间的消耗主要是递归造成的栈空间使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O (logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O (n)，平均情况，空间复杂度也为O (logn)。