首页 > 试题广场 >

对N个记录的线性表进行快速排序为减少算法的归递深度,以下叙述

[单选题]

对N个记录的线性表进行快速排序为减少算法的归递深度,以下叙述正确的是（）. 


  • 每次分区后.先处理较短的部分:
  • 毎次分区后,先处理较长的部分:
  • 与算法毎次分区后的处理顺序无关:
  • 以上三者都不对
查看答案及解析
添加回答
clear_rain头像 clear_rain
选C
【分析】

快排的递归深度和分区的处理顺序没有关系，递归栈深度才和处理的先后顺序有关，先处理短部分时栈深度更小。

快速排序的本质是首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。
快速排序就是递归调用此过程——在以上一个基准点为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对序列进行快速排序的全过程。

有关递归栈深度的讨论参考：

发表于 2019-04-11 20:36:35 回复(0)
更多回答
推荐
白驹之过隙头像 白驹之过隙
选C。该题考查的是快速排序的原理以及函数执行中压栈弹栈的原理。
快速排序的思想是：找出序列的一个关键字作为枢纽，大于枢纽的元素放到枢纽之后，小于枢纽的元素放到枢纽之前，这样一趟排序将源数列分成两个子序列。然后对这两个子序列递归进行快速排序，直到每个子序列都包含一个元素为止。
递归次数与各元素的初始排列有关，如果每一次划分后分区比较平衡，则递归次数少；如果划分后分区不平衡，则递归次数多。递归次数与处理顺序无关。

编辑于 2019-04-13 16:29:56 回复(0)
天天向上201809021801368头像 天天向上201809021801368
B
发表于 2018-09-10 09:55:45 回复(0)
牛客635945676号头像 牛客635945676号
上面解析一大堆的都是扯淡，深度与次序有关，次数与次序无关
发表于 2022-10-05 20:19:41 回复(0)
提交观点

问题信息

排序
上传者：zsw3
难度：
4条回答 4747浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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