首页 > 试题广场 >

采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，

[单选题]

采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（） 

  • 递归次数与初始数据的排列次序无关
  • 每次划分后，先处理较长的分区可以减少递归次数
  • 每次划分后，先处理较短的分区可以减少递归次数
  • 递归次数与每次划分后得到的分区处理顺序无关
查看答案及解析
添加回答
philian头像 philian
这道题混淆了递归深度和递归次数，无论是先长还是先短，递归次数是不变的，但递归深度依据给定数据会在O(logN)~O(N)之间变化。
原因是对两部分待排序区间进行递归形成的是二叉树，递归深度取决于二叉树的高度。
如果轴点恰好平分两个待排序部分，那么递归深度达到最优，即O(logN)，但如果轴点使两部分极不平衡，那么二叉树就会退化为单链表，其深度会达到O(N)。
发表于 2016-12-17 10:05:54 回复(2)
wanlanwalan头像 wanlanwalan
递归次数与各元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少；如果划分后分区不平衡，则递归次数多。递归次数与处理顺序无关。
发表于 2017-04-21 10:05:04 回复(2)
epsilon_47头像 epsilon_47
我觉得递归树的深度是不变的，它与选取的基准元素有关。先处理分区较短的影响的是递归树的宽度，也就是递归树占用的栈空间，较短的先结束返回，释放栈。
发表于 2019-04-13 17:43:37 回复(0)
阳光下的米雪头像 阳光下的米雪
递归深度是每次划分后先处理短的
递归次数应该是固定的
发表于 2019-05-02 09:53:42 回复(0)
天蚕变头像 天蚕变
选短的（影响递归的深度）
发表于 2017-07-08 20:14:46 回复(0)
提交观点

问题信息

递归
上传者：城市里的养猫者
难度：
5条回答 4290浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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