最近公司组织所有人参加「技术能力认证」，被迫刷题，遇到个挺意思的问题，完全搞明白还是花了点时间的，这里记录一下，免得以后忘了...
假设一个数组采用快速排序，则下面的选项中，不可能是第 3 趟排序结果的是？
忘记了快速排序的朋友可以在这里复习下，确保清楚算法的每一步操作，这是完成本题的基本条件。
先来明确两个概念：
[0, 9, 7, 5] 从小到大排序，0 最小并且已经在第一位了，就可以说 0 已经在「最终位置」上了。接下来咱们分析快速排序的「趟」和「最终位置」的关系。
第 1 趟可以确定 1 个最终位置，就是「基准数」的位置。
第 2 趟开始，分两种情况：
所以，第 3 趟完成后，确定了多少最终位置呢？—— 最少 3 个，最多 5 个。
其实是有可能大于 5 个的，有些数在交换的过程中，可能凑巧落在了最终位置上，但这不影响解题
基于上面的分析，咱们来看看题目中的选项，落在最终位置的数字用「加粗红色」标了出来（显然，最终排序结果是 4, 6, 8, 10, 12, 14, 16）：
C 和 D 不可能，小于 3 个最终位置。
B 可能，B 属于上面说的最倒霉情况，基准数每次都选了最大值。
A 稍微复杂一些，但按上面的思路分析：
所以 A 不可能
综上：答案是 A、C、D
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。