GESP 五级 · GESP 202512 C++ 五级 第 21 题

通过在数组的第一个、最中间和最后一个这 3 个数据中选择中间值作为枢轴（比较基准），快速排序算法可降低落入最坏情况的概率。

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】快速排序｜三数取中枢轴策略｜最坏情况概率

🎯 考纲定位 GESP 五级算法设计与分析，考查快速排序最坏情况规避策略。命题人卡住死记结论的考生——不理解为何选中间值能降低排序代价。

🧠 解题思维 快速排序最坏情况发生在已排序数据，每次划分极不平衡导致 O(n²) 复杂度。选首末中三数中间值作枢轴，能提升枢轴代表整体水平的概率，使左右子数组规模更均衡，从而降低落入最坏情况的概率。这是经典优化技巧。

🪤 陷阱拆解 陷阱在于混淆"最坏情况必然发生"与"概率降低"。题目明确说"降低概率"，这是针对已排序数据的经典优化——三数取中。若只背结论不理解本质，会误以为这是无效操作。

🔄 反命题思维 命题人视角：若换成"随机选枢轴"，答案仍为正确，但考察点变为概率论。本题专门针对"三数取中"这一确定性优化。刷到类似题先问：命题人想考我哪种枢轴策略？