第1个回答 2022-07-17
1.时间复杂度
考虑到最好情况，每次都是均匀划分，则运算成本为：
T(n) =2 * T(n/2) + n
递归展开后：
T(n) = 2 * 2[T(n/4) + n/2] + n = 2^kT(n/(2^k)) + kn
最后结束于T(1), 即：2^k=n
可得：
T(n) = Cn + nlogn
不难看出复杂度为O(nlogn)。
但如果是最坏情况，比如[1,2,3,4,5]，若一数组末尾元素作为划分标准，那么计算的成本就变为了：
T(n) = T(n-1) + n = 1 +2 +....+5 = n(n+1)/2
很明显，复杂度变成了O(n^2)。
为了防止这种情况，在选取基准元素的地方可以再进行优化，比如三数取中法(随机取三个不相等的元素，取中间大小的那个元素作为基准值)
并且当待排序序列的长度分割到一定大小后，使用插入排序（在数组长度较小时，插入排序大效率会高于快速排序）。
2.空间复杂度
快速排序使用递归，递归使用栈
最好情况： 每次左右都是均匀划分 ， 递归树的深度为：logn，其空间复杂度也就为 O(logn)，
最坏情况： 每次只能排除一个元素，要递归剩下n-1个元素，如：[1,2,3,4,5]，或[5,4,3,2,1]
需要进行n‐1次递归调用，其空间复杂度为O(n)，
平均情况： 空间复杂度也为O(logn)。
3.稳定性：
快速排序无法保证相等的元素的相对位置不变，因此它是不稳定的排序算法