GESP 七级 · GESP202609 C++ 七级 第 21 题

快速排序的平均时间复杂度为 O(n log n)，最坏时间复杂度也为 O(n log n)。

看到题先想快速排序的分治过程。平均情况每次划分均衡，递归深度logn，每层O(n)，故平均O(nlogn)。最坏情况划分极度不均，退化为O(n²)。但题目说最坏也为O(nlogn)，这明显矛盾。因此选B。

易错点在于混淆快速排序与归并排序。归并排序无论何种情况都是O(nlogn)，而快速排序最坏是O(n²)。许多考生凭印象选A，忽略了最坏情况的存在。

考纲定位

在《GESP 考试大纲》七级算法部分，快速排序是必考内容，其平均与最坏时间复杂度是高频考点。命题人放这道题，就是要卡住那些只背结论、不真正理解分治过程的学生。他们往往把快速排序与归并排序混为一谈，导致对最坏情况的判断失误。

解题思维

快速排序通过选取枢轴进行划分，平均情况下递归深度为logn，每层处理O(n)元素，故平均时间复杂度为O(nlogn)。最坏情况发生在每次划分都极度不均，递归深度退化为n，总复杂度为O(n²)。题目声称最坏也是O(nlogn)，这直接违背了算法的基本性质，因此答案只能是B。