第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.稳定性:
快速排序无法保证相等的元素的相对位置不变,因此它是不稳定的排序算法