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

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

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

快速排序的空间复杂度是多少？

答：快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的 空间复杂度 为 O (logn) ，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O (n) 。 所以我们一般认为快速排序的空间复杂度为 O (logn) 。

什么是快速排序的最坏情况？

答：什么是快速排序的最坏情况，那就是， 对于每一个区间，我们在处理的时候，选取的轴刚好就是这个区间的最大值或者最小值 。 比如我们需要对 n 个数排序，而每一次进行处理的时候，选取的轴刚好都是区间的最小值。

快速排序时间复杂度和冒泡排序一样吗？

答：但是快速排序在最坏情况下的 时间复杂度 和冒泡排序一样，是 O (n 2) ，实际上每次比较都需要交换，但是这种情况并不常见。 我们可以思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是 O (nlogn) ，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。