首页 > 试题广场 >

下列选项中，不可能是快速排序第2趟排序结果的是 （）

[单选题]

下列选项中，不可能是快速排序第2趟排序结果的是 （） 

  • 2,3,5,4,6,7,9
  • 2,7,5,6,4,3,9
  • 3,2,5,4,7,6,9
  • 4,2,3,5,7,6,9
查看正确选项
添加回答
hanfu头像 hanfu
快速排序：每趟排序过后，选定的pre的位置确定；即两趟意味选项中至少有两个位置是确定
发表于 2017-08-13 21:50:09 回复(0)
niukeley头像 niukeley
C.快排的阶段性排序结果的特点是，第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在2个这样的数的选项。A选项中2、3、6、7、9均符合，所以A排除；B选项中，2、9均符合，所以B排除；D选项中5、9均符合，所以D选项排除；最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。
发表于 2020-12-09 09:52:15 回复(0)
影尘头像 影尘
快速排序是一种分治排序的算法，每次划分都是一次将某个数据放入正确的位置
发表于 2019-05-14 21:47:48 回复(0)
Sunny_ivy头像 Sunny_ivy
BC都不对吧
发表于 2016-11-27 16:04:38 回复(1)
philian头像 philian
四个选项都是同样的数组元素，若完全有序，应为2345679
每经过一趟快排，轴点元素都必然就位，也就是说，一趟下来至少有1个元素在其最终位置
所以考察各个选项，看有几个元素就位即可。
A：2、3、6、7、9
B：2、9
C：9
D：5、9
第二趟至少应有2个元素就位，所以C不对。
发表于 2016-12-16 10:59:52 回复(13)
zhaobinw头像 zhaobinw
快速排序，即每趟选择某一关键字X，使所有比X大的移到X右边，比X小的移到X左边。
若进行两趟快速排序，则至少能找出两个关键字符合上述情况。
A选项：9，7
B选项：9，2
C选项：9
D选项：9，5
快排选择关键字的顺序可以随机。不一定要相邻。
发表于 2016-11-27 20:07:19 回复(0)
艾德慕头像 艾德慕
高赞答案有遗漏情况，以2019年408真题第10题为例
第二趟快排结果不可能是（D）
A. 5,2,16,12,28,60,32,72
B. 2,16,5,28,12,60,32,72
C. 2,12,16,5,28,32,72,60
D. 5,2,12,28,16,32,72,60

最终排序位置是2,5,12,16,28,32,60,72
第一趟排序确定一个元素位置
第二趟排序又确定一个或两个元素位置
所以两趟排序共确认2或3个元素位置（低于2个的错误）
当第一趟元素确认的位置为最左或最右时，第二趟排序只能确认一个位置（A，B选项情况）
当第一趟元素确认位置不是最左或最右时，第二趟能确认2个位置（C选项情况）
编辑于 2019-12-16 11:38:32 回复(4)
一艘飞向星的客机头像 一艘飞向星的客机
快速排序选择一个切分元素将数组分成两个子数组，当经过一趟快排后，这个切分元素就会位于最终位置上。所以，第一趟快排之后，切分元素的位置有两种情况：
  1. 位于两端；
  2. 位于中间；
第一种情况：此时原数组被切分成一个子数组（因为此时切分元素的某一边是没有子数组的），继续进行切分，最终这个子数组的切分元素也会就位，所以共 2 个元素就位；
第二种情况：此时原数组被切分成两个子数组，两个子数组都进行切分，那么会有两个切分元素就位，所以共 3 个元素就位。
编辑于 2022-09-05 21:03:25 回复(0)
牛客-鹏程万里头像 牛客-鹏程万里
每经过一趟快排，轴点元素都必然就位，也就是说，一趟下来至少有1个元素在其最终位置
所以考察各个选项，看有几个元素就位即可。
发表于 2018-09-07 09:27:19 回复(0)
rppp头像 rppp
c选项只有9就位，因此，不可能
发表于 2017-07-03 21:59:07 回复(0)
提交观点

问题信息

排序
上传者：城市里的养猫者
难度：
10条回答 19651浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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