NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 5 题

如果不在快速排序中引入随机化，有可能导致的后果是（ ）。

拿到题先想：快速排序最坏情况何时发生？命题人挖坑在‘后果’二字——不是功能错，而是性能崩。

很多学生会把‘时间复杂度退化’和‘算法错误’混淆，误选C；也有人以为基准选不好会死循环或越界，其实只是分区极不平衡。记住：快速排序逻辑没错，只是运气太差导致效率暴跌。

这道题考查的是快速排序在最坏情况下的时间复杂度退化问题。

快速排序的核心思想是“分治”：选一个基准元素（pivot），把数组分成小于和大于基准的两部分，然后递归排序。关键在于“选基准”这一步。如果每次选的基准都是当前区间的最小值或最大值，那划分就会极度不平衡——一边只有1个元素，另一边剩下n-1个。这样递归深度就变成n层，每层都要遍历整个区间，总时间复杂度就从平均的O(n log n)退化成最坏的O(n²)。

如果不引入随机化，比如固定选第一个元素当基准，那对已经排好序或逆序的数组简直是“灾难现场”：每次划分都极不平衡，性能直接崩盘。但要注意，算法本身并没有错，排序结果依然是正确的，只是太慢了。所以A（越界）、B（死循环）、C（结果错误）都不成立，只有D（排序时间退化为平方级）符合事实。

命题人爱在这里挖坑：把“效率问题”包装成“错误问题”，诱导学生选C。其实快速排序逻辑没错，只是运气太差导致效率暴跌。记住：快速排序最坏情况是O(n²)，但不会导致越界、死循环或结果错误。

从考频看，快速排序在NOIP/GESP等比赛里非常常见，题库共考过53题，覆盖7个考试级别，逐年分布：2008年1题、2009年3题、2011年1题、2012年1题、2019年1题、2020年1题、2023年6题、2024年15题、2025年14题、2026年7题、null年3题；分赛事：GESP五级29题、GESP八级7题、GESP七级5题、NOIP提高组初赛4题、CSP提高级4题、GESP六级2题、NOIP普及组初赛2题。可见快速排序是高频考点，尤其近年（2023-2026）出题量激增，说明命题人持续重视这个知识点。

基于数据与经验，未来可能继续考“快速排序最坏情况”“随机化快速排序的优势”“平均vs最坏时间复杂度对比”等变体，尤其是结合具体数组样例让考生分析划分过程。暂无足够依据预测具体题型变化，但快速排序作为经典算法，其核心概念（基准选择、分区、递归深度）必将继续被考察。