首页 > 试题广场 >

如果待排序的数组近似递减排序，则此时使用快排算法进行递增排序

[单选题]
如果待排序的数组近似递减排序，则此时使用快排算法进行递增排序的时间复杂度为() 
  • O(n)
  • O(n^2)
  • O(nlogn)
  • O((n^2)*logn)
查看答案及解析
添加回答
程序员不是猿头像 程序员不是猿
如果序列接近递增或递减，那么一边肯定为空树，所以是n^2
发表于 2017-05-08 23:49:24 回复(0)
枫の伤头像 枫の伤
题目说近似...，这样的话无论是随机还是选定某一个主元素，上界都是nlogn吧？如果是全部有序且选定头尾元素，那才算最坏情况，即n方
发表于 2017-05-08 08:05:06 回复(0)
搞事情头像 搞事情
最坏的情况，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个的子序列，另外一个为空。如果递归树画出来，就是一颗斜树。此时需要执行n-1次递归调用，且第i次划分需要经（n-i）次关键字比较才能找到才能找到第i个记录，因此比较的次数为(n-1)+(n-2)+...+1 = n*(n-1)/2，最终时间复杂度为O(n^2).
发表于 2016-03-09 09:36:27 回复(1)
orzOrzorzOrz头像 orzOrzorzOrz
如果本来就是要排成递增，已经近似递增，用快排还是O（n^2）?
如果，采取随机枢纽值呢》？
发表于 2015-11-10 18:12:25 回复(2)
倚杖听江声头像 倚杖听江声
退化为了冒泡排序，而冒泡排序的时间复杂度为O（n2）。
发表于 2018-08-28 15:20:34 回复(0)
侯卿头像 侯卿
题目没说清楚要排序成什么样哈，无语。。。
如果是要降序则问的是最坏情况B。如果是要升序问的就是最优情况C。
发表于 2018-01-23 15:55:44 回复(0)
起风啦~头像 起风啦~
题目是什么意思呢？数列接近递增，但是要最终拍成递减的？？是这个意思吗？
发表于 2018-01-14 14:40:48 回复(0)
提交观点

问题信息

排序
来自：完美世界2016研发工...
上传者：SunburstRun
难度：
7条回答 9041浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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