快排的最差情况以及快排平均复杂度的计算

原创
2018/03/20 20:18
阅读数 7.2W

最近突然讨论了这两个问题,有点忘记了,记录了一下网上的比较好的说法,参见Reference

快排的相关知识请参考排序总结

快排的最差情况以及如何避免

首先,快排的最差情况什么时候发生?

1. 已排序

2. 数值全部相等(1的特殊情况)

快排最好的情况是,每次正好中分,复杂度为O(nlogn)。最差情况,复杂度为O(n^2),退化成冒泡排序

为了尽量避免最差情况的发生,就要尽量使每次选择的pivot为中位数。

一般常用的方法是,对每一个数列都取一次中位数(O(n)),这样总体的快排时间复杂度仍为O(nlogn)。

更为简化的方法是,取头、中、尾的中位数(O(1))作为pivot

另一个问题:

如果有元素等于pivot,是换还是不换呢?

1. 如果换,那当遇到全是一样的数,每一次都要交换,但是有一个好处是,pivot会移动到中间的地方,正好中分,符合快排最好的情况,复杂度为O(nlogn)

2. 如果不换,同样是全是一样的数,的确不用交换,i指针一直移到最后遇到j指针,pivot被移动到最后一位。分治时,右边没有元素,左边n-1个元素,重复一下。符合快排最坏情况,复杂度为O(n^2)

综上,还是换吧。

对于最差情况的第2种数据,即数值全部相等,或者存在大量相等的数值时,Java的sort方法中使用三向切分快排来优化这个问题,详情请看Java中的排序

快排平时时间复杂度计算

计算方式来源于算法导论

主定理: T [n] = aT[n/b] + f (n)

其中 a >= 1 and b > 1 是常量 并且 f (n) 是一个渐近正函数, 为了使用这个主定理,您需要考虑下列三种情况:

快速排序的每一次划分把一个 问题分解成两个子问题,其中的关系可以用下式表示:

T[n] = 2T[n/2] + O(n) 其中O(n)为PARTITION()的时间复杂度,对比主定理,

 T [n] = aT[n/b] + f (n)

我们的快速排序中:a = 2, b = 2, f(n) = O(n)

Reference:

1. https://www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/

2.《算法导论》

展开阅读全文
打赏
0
3 收藏
分享
加载中
2018/03/28 11:19
回复
举报
更多评论
打赏
1 评论
3 收藏
0
分享
返回顶部
顶部