首页 > 试题广场 >

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

[单选题]
下列选项中，不可能是快速排序第2趟排序结果的是 （） 
  • 4 14 10 12 8 6 18
  • 4 6 10 8 12 14 18
  • 6 4 10 8 14 12 18
  • 8 4 6 10 12 14 18
查看正确选项
添加回答
寻找offer头像 寻找offer
只需要掌握一点就可以解出这个问题：
每趟排序就有一个元素排在了最终的位置上。那么就是说，第n趟结束，至少有n个元素已经排在了最终的位置上。

所以我们把最终排序结果写出来：然后计算在最终位置上的个数就可以

发表于 2018-05-29 22:45:54 回复(12)
0ffff头像 0ffff
参考 链接：https://www.nowcoder.com/questionTerminal/0e322ea03d0d4b318403c7119a18e5a1
四个选项都是同样的数组元素，若完全有序，应为  4 6 8 10 12 14 18
每经过一趟快排，轴点元素都必然就位，也就是说，一趟下来至少有1个元素在其最终位置
所以考察各个选项，看有几个元素就位即可。
A：4 、18
B：4、6、12、14、18
C：18
D：10、12、14、18
第二趟至少应有2个元素就位，所以C不对。
发表于 2019-08-02 19:31:45 回复(0)
睶头像 睶

1）.n趟后至少有n个是处在正确位置，故先把最终排序结果排好，再挨个比较哪些是满足此条件的
不足n个的肯定不可能是快速排序第n趟排序结果
2）.在1）的基础，找到n个处在正确位置的，必须满足左小右大（如果题目是求升序）或者左大右小（如果题目是求降序），如果找不到至少n个这样的位置，那么肯定不可能是快速排序第n趟排序结果
编辑于 2020-03-08 11:48:51 回复(0)
223s头像 223s
快排每次排序结束，最少有一个元素在最终位置，第二趟就最少2个元素在最终位置，C不符合
发表于 2020-08-08 13:51:20 回复(0)
Williambaozk头像 Williambaozk
如果能找到两个数字，每个数字前面的数字都比它小，后面的都比它大，那么就可能是快速排序第2趟排序结果。
发表于 2019-04-08 00:15:32 回复(0)
提交观点

问题信息

网易 2018 Java工程师
上传者：小小
难度：
5条回答 2035浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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