2019 408真题 第10题 快速排序

仔细想了一下，一楼应该是对的

     再来扩展一下一楼的意思，一楼的意思是，第一趟快速排序至少确定1个点的最终位置，第二趟快速排序一般再会确定2个点的位置(也可能是1个点)，因为是在第一次排序后的基准点的2侧分别再进行一次快排，那么再确定2个基准点的最终位置，如果恰好第一次排序后的这个基准点在恰好在序列的最左边或者最右边，那么只能确定左边或者右边1个基准点位置。所以可能是第二趟下来可能是确定2个基准点也可能是3个基准点位置。如果一直是这样只能确定1个基准点位置，那么就退化成了冒泡，就成了O(n2)了。      再简单一点想，快速排序每一趟都可以确定一个元素的最终位置，冒泡是不是也是这样，如果快排仅仅是这样，那为什么还需要快排呢，快排的意义在于，轮询一遍可能会确定多个基准点的最终位置。

他这个第二趟我是这么理解的:把快排想象成二叉树分割，第一趟是确认根节点和左右树区间，第二趟是确认左右子树的根节点和继续分割。由于有可能第一次有一侧为空，所以可能确认的是两个或三个点，而且两个点的情况必须有一侧是空的。ab没问题，c还有个2，d找不到第3个点，所以选d

首先应当明确，C的第一趟应该以2或28为枢轴进行划分区间，以32为第一趟的枢轴元素作划分会犯等同于D的一个错误。 题目说的是 对未确定最终位置的所有元素进行一遍处理称为一“趟”，那么，D的第一趟在确定为以32枢轴的前提下，第一趟划分的结果是不是得到了左小右大的两个子区间α=【5,2,12,28,16】和β=【72,60】？ 这个时候进行第二趟划分应当①选择两个子区间各自的新枢轴，②并把两个子区间的元素，根据各自的新枢轴作进一步的划分呢？此时第二趟D的快排中，左子区间α以12为枢轴将左子区间进一步划分是没问题的，但是右子区间β的却不能按左小右大的规则得出新枢轴，于是D是错的。 同理，A、B的第一趟分别是以72、72作为枢轴元素时，得出各自第二趟的划分区间，而这个区间只有左子区间一个。于是可以很轻易的看出进行第二趟时，依据的枢轴元素分别为28和2。 而于C而言，我分成三种情况： 1. 考虑以2为第一趟划分的情况，这时第二趟若以28或32作为枢轴元素划分，则都可以分为左小右大的两个子区间； 2. 同理，考虑第一趟以28为划分的枢轴，则划分出了两个子区间，同时这两个子区间可以分别以2和32作为第二趟划分的枢轴元素，于是存在第二趟快排的结果为C的可能性。 3. 但是C第一趟以32为枢轴时，犯了和D一样的错误，导致C第一趟结果的右区间不能在第二趟时看出是以哪个元素为枢轴的——因为右区间根本没有合理的枢轴。因此C是万万不能以32为第一趟的枢轴元素进行快排的。 综上，A、B、C都存在成为快排第二趟结果的可能性，唯独D是因为第一趟划分出的右子区间，在经历第二趟快排后仍不能找出一个枢轴元素，使得这个右子区间满足枢轴元素左侧均小于它、右侧大于它，故而D是不可能成为快排第二趟的结果的 表达能力有限，如果觉得结果太啰嗦还请见谅

楼下说的都不太对，这就是一个审题问题罢了： 对未确定最终位置的所有元素进行一遍处理称为一“趟” 未确定最终位置的所有元素 所有元素（我们平时一趟是单左或单右） 所以D错的原因就是要么2 5要么60 72；（很巧合地第一枢轴无论取哪一个，剩余两个元素都需要归位） ABC你只要取在最左或者最右作为第一枢轴，剩余一个枢轴任取 审题题目😉

还是不明白