GESP 五级 · GESP 202412 C++ 五级 第 14 题

关于分治算法，以下说法中不正确的是（ ）。

快速排序的核心是划分（partition）：选定基准，将数组分为小于和大于基准的两部分，再递归处理。注意最坏情况发生在数组已有序时。

快排在数组已有序时退化为O(n²)。选基准尽量用三数取中法避免最坏情况。分区时注意边界处理。

【考点】分治法定义｜排序算法分类｜算法思想辨析

🎯 考纲定位 GESP五级《算法基础》模块排序与查找专题。命题人专门在此处设坑，卡住大量考生对"分治"概念边界的模糊认知——把"递归解决子问题"等同于"分治"，却忽略了分治必须包含"合并结果"这一核心步骤。

🧠 解题思维 首判定义：分治=递归分解问题→独立求解子问题→合并子结果。次判经典：归并排序（分两半递归排再合并）与快速排序（分区递归排）均完美契合，B、C正确。末判冒泡：它逐对比较相邻元素，仅局部交换，无分解、无递归、更无合并，纯属贪心迭代，D错。

🪤 陷阱拆解 A项看似正确实则冗余——命题人故意把分治三步骤全写出来，诱导学生只关注"分""解"而忽略"合"；B、C项是教材高频考点，考生若背过"分治经典案例=归并+快速"，自然排除；D项阴险处在于"采用了分治思想"这五个字，考生看到"排序""递归""分解"就下意识选，却忘了冒泡是典型的"原地迭代"算法，根本不符合分治的"合并"环节。

🔄 反命题思维 若将D改为"插入排序采用了分治思想"，答案仍为D（插入排序也是迭代）；若将题干改为"以下算法中，不属于分治思想的是"，答案不变；若将题干改为"以下算法中，属于贪心思想的是"，则D正确。刷到此类题，先默念"分治三步骤缺一不可"，再逐个比对。