“快速排序”的问题

发布网友发布时间：2022-05-10 11:13

共2个回答

热心网友时间：2023-10-08 18:01

首先你得明白快排的整个过程，就我看来，关键在于划分元的选择上
如果选择的划分元是随机分布于整个元素空间的，那么每次划分后的两个子序列长度很大概率相差不大，也就是说：
T(n)≈2*T(n/2)+常数
这个时候的复杂度就是nlgn；
不然，如果序列是有规律分布，一般来说我们是固定一个位置选择划分元（第一个，中间的，最末等等都是常选的地方），那么每次你的划分都差不多，最坏情况你把n划分为c+(n+c)，c远远小于n，这是很有可能的，此时时间递归式即为：
T(n)≈T(n-c)+常数
复杂度O(n*n)
所以有种快排冠上了随机的名字，意思就是说随机选择划分元，避免陷入上面第二种情况

热心网友时间：2023-10-08 18:01

http://ke.baidu.com/view/115472.html?wtp=tt
这里面的“时空复杂度”和“随机化算法”两章就是在讲你问的内容，还是挺清楚的，如果还有不懂看完了再问