题17

题17

题目

Q:【2014 统考真题】下列选项中，不可能是快速排序第二趟排序结果的是( ).
A. 2,3,5,4,6,7,9
B.
C.
D.

分析

A:快速排序-aw每一次排序以后都有一个元素，被放在正确的位置

解

C

• 对 个元素进行第一趟快速排序后,会确定一个基准元素,根据这个基准元素在数组中的位置,有两种情况:
  1. 基准元素在数组的首端或尾端,接下来对剩下的 个元素构成的子序列进行第二趟快速排序, 再确定一个基准元素
  2. 基准元素不在数组的首端或尾端, 第二趟快快速排序对基准元素划分开的两个子序列分别进行一次划分, 两个子序列各确定一个基准元素
• 这样, 两趟排序后就至少能确定两个元素的最终位置, 其中至少有一个元素是在数组的首端或尾端
• 基于上述结论, 观察题中的四个选项, A 项的 符合第一种或第二种情况
• B 项中 2,9 符合第一种情况
• D 项中 5,9 符合第一种情况
• 最后看 项,只有 9 处于最终位置,因此不可能是快速排序第二趟的结果