数据结构：下列选项中，不可能是快速排序第2趟排序结果的是（2019年全国试题10）

题目

排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列排序中，不可能是快速排序第二趟结果的是（）【2019年全国试题10（2分）】

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

题解

答案：D，分析如下。

每经过一趟快排，轴点元素都必然就位。也就是说，一趟下来至少有1个元素在其最终位置。所以考察各个选项，看有几个元素就位即可。

最终排序位置是：2, 5, 12, 16, 28, 32, 60, 72，而选项中正确的位置有：

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

• 第一趟排序，确定一个元素位置
• 第二趟排序，又确定一个或两个元素位置
  • 当第一趟元素确认的位置为最左或最右时，第二趟排序只能确认一个位置（A，B选项情况）
  • 当第一趟元素确认位置不是最左或最右时，第二趟能确认2个位置（C选项情况）

所以，两趟排序共确认2或3个元素位置。

总结

以上是生活随笔为你收集整理的数据结构：下列选项中，不可能是快速排序第2趟排序结果的是（2019年全国试题10）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。