题目
排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列排序中,不可能是快速排序第二趟结果的是()【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个元素位置。