排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中,不可能是快速排序第二趟结果的是()
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选项5,60都没有归位
解答:
这道题关键的难点在于...
用户登录可进行刷题及查看答案
这道题关键的难点在于理解一“趟”,就是递归的一轮,画出递归树,就是递归树中的一层。
第一步:
检查快速排序,首先利用快速排序的性质,快速排序每一趟至少能够保证一个元素落在最终位置,即枢轴一定落在最终位置。这里进行了两趟快速排序,至少两个元素落在最终位置。
我们求出排好序后的序列为:2, 5, 12, 16, 28, 32, 60, 72,然后依次和四个选项进行比对,看有没有不符合要求的。
A中有两个落位。
B中有两个落位。
C中有三个落位。
D中有两个落位。
均符合。
第二步:
检查枢轴左边的元素是否都小于枢轴,右边元素是否都大于枢轴。
到这里一般人就卡住了,找不到正确答案吗?
第三步:
画出递归树,明显选项D无法构造。
如果第一趟枢轴为12,第二趟左右两段分别递归产生新的枢轴,明显左边段枢轴缺失。
如果第一趟枢轴为32,第二趟左右两段分别递归产生新的枢轴,明显右边段枢轴缺失。
无法构造出递归树。
本题选D。
登录后提交答案