快速排序法的性能是什么

快速排序法的性能是什么？

答：我们来分析一下快速排序法的性能。 快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。 如图所示，它是 {50109030 7040806020}在快速排序过程中的递归过程。

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

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

快速排序算法的时间复杂度是多少？

答：然后，获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半）。 于是不断地划分下去，我们就有了下面的不等式推断。 …… 也就是说，在最优的情况下，快速排序算法的时间复杂度为O (nlogn)。 在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。