什么情况下使用快速排序比较快
3个回答
展开全部
在分区时两个子分区最平衡时。
因为两个子分区大小不可能同时大于n/2，所以一个分区大小为n/2的下界，另一个分区大小为n/2的上界加1时，快速排序的运行速度最快。
这时，表达其运行时间的递归式为
T(n) <= 2T(n/2) + O(n)
根据定理
T(n) =
if n = 1 , then O(n)
if n > 1, then 2T(n/2) + O(n)
的解为T(n) = O(nlgn)
由于在每一层递归上，划分的两边都是对称的。所以，从渐进意义上来看，算法运行得最快。
因为两个子分区大小不可能同时大于n/2，所以一个分区大小为n/2的下界，另一个分区大小为n/2的上界加1时，快速排序的运行速度最快。
这时，表达其运行时间的递归式为
T(n) <= 2T(n/2) + O(n)
根据定理
T(n) =
if n = 1 , then O(n)
if n > 1, then 2T(n/2) + O(n)
的解为T(n) = O(nlgn)
由于在每一层递归上，划分的两边都是对称的。所以，从渐进意义上来看，算法运行得最快。
本回答被提问者采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
展开全部
双向排序是最快的
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
更多回答（1）
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
