首页 > 试题广场 >

快速排序在最坏情况下的时间复杂度为？

[单选题]
快速排序在最坏情况下的时间复杂度为（） 
  • O(log(n))
  • O(n*log(n))
  • O(n)
  • O(n^2)
添加回答
牛客874504号头像 牛客874504号
D
快排平均情况O(nlogn)
最好情况O(nlogn)
最坏情况O(n的平方)
发表于 2015-03-31 22:55:26 回复(0)
更多回答
推荐
MyGoodHelper头像 MyGoodHelper
D
在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为  ，最终其时间复杂度为O(n*n)。
编辑于 2015-01-31 10:45:10 回复(0)
ellie2dina头像 ellie2dina
快排最坏情况，退化成冒泡排序
发表于 2015-08-31 17:04:54 回复(0)
程序猿Go师傅头像 程序猿Go师傅

编辑于 2019-10-21 20:56:27 回复(0)
牛客-007头像 牛客-007
答案：D
快速排序是不稳定的排序，平均情况下时间复杂度为O(nlog2n)最坏情况下时间复杂度为O(n*n)
发表于 2015-01-12 16:00:13 回复(0)
kiracici头像 kiracici
最坏情况下是D 
发表于 2015-05-20 14:14:47 回复(0)
提交观点

问题信息

复杂度 欢聚集团 排序
上传者：小牧魔法袋
难度：
6条回答 25143浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号