快速排序第 N 趟的可能结果

最近公司组织所有人参加「技术能力认证」，被迫刷题，遇到个挺意思的问题，完全搞明白还是花了点时间的，这里记录一下，免得以后忘了...

题目#

假设一个数组采用快速排序，则下面的选项中，不可能是第 3 趟排序结果的是？

• A：4, 8, 6, 10, 12, 16, 14
• B：10, 4, 6, 8, 12, 14, 16
• C：8, 4, 6, 12, 10, 14, 16
• D：4, 8, 6, 12, 10, 16, 14

解析#

忘记了快速排序的朋友可以在这里复习下，确保清楚算法的每一步操作，这是完成本题的基本条件。

先来明确两个概念：

• 趟：把未排序的元素遍历一遍就是 1 趟
• 最终位置：就是指一个数字在排序好的数组内的位置，比如 [0, 9, 7, 5] 从小到大排序，0 最小并且已经在第一位了，就可以说 0 已经在「最终位置」上了。

接下来咱们分析快速排序的「趟」和「最终位置」的关系。

第 1 趟可以确定 1 个最终位置，就是「基准数」的位置。

第 2 趟开始，分两种情况：

1. 如果前 1 趟比较倒霉，基准数选中了未排序数字中的最小值或者最大值，那么 left 和 right 只存其一，本趟还是只能确定 1 个基准位置
2. 第二种情况就比较正常了，前 1 趟的基准数在数组里靠中间的位置，那么可以在 left 和 right 中分别再确定 1 个基准位置，本趟一共能确定 2 个基准位置

所以，第 3 趟完成后，确定了多少最终位置呢？—— 最少 3 个，最多 5 个。

其实是有可能大于 5 个的，有些数在交换的过程中，可能凑巧落在了最终位置上，但这不影响解题

基于上面的分析，咱们来看看题目中的选项，落在最终位置的数字用「加粗红色」标了出来（显然，最终排序结果是 4, 6, 8, 10, 12, 14, 16）：

• A：4, 8, 6, 10, 12, 16, 14
• B：10, 4, 6, 8, 12, 14, 16
• C：8, 4, 6, 12, 10, 14, 16
• D：4, 8, 6, 12, 10, 16, 14

C 和 D 不可能，小于 3 个最终位置。

B 可能，B 属于上面说的最倒霉情况，基准数每次都选了最大值。

A 稍微复杂一些，但按上面的思路分析：

• 如果第 1 趟确定的是 4 的最终位置，第 3 趟完成后只确定了 3 个最终位置（4、10、12），那只能和 B 类似，最终位置集中在数组两端
• 如果第 1 趟确定的是 10 或者 12 的最终位置，第 3 趟后不可能只存在 3 个最终位置

所以 A 不可能

综上：答案是 A、C、D