NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 18 题

下列算法中运用分治思想的有（ ）。

这题考分治思想，拿到题先想：算法是不是把大问题拆成小问题、递归解决、再合并结果。快排和归并排序都符合，冒泡和计数排序没有拆分递归过程，直接排除即可。

很多同学死记硬背‘快排归并是分治’，却说不清为什么。容易把冒泡排序的‘交换相邻元素’误认为是在‘分解’，其实冒泡只是原地交换，没有划分子问题；计数排序更是基于统计频次，连递归的影子都没有。命题人常挖坑在‘合并’步骤：快排合并是隐式的（返回有序区间），归并排序合并是显式的（两有序数组合并），但两者都满足分治三步骤。

考点概念：分治思想

分治法的核心是三步：分解（把大问题拆成若干小问题）、求解（递归解决小问题）、合并（把小问题的解拼成大问题的解）。典型代表就是快速排序和归并排序。

快速排序

快速排序先选一个基准值，把数组分成“小于基准”和“大于等于基准”两段（分解），然后对这两段递归排序（求解），最后两段自然连起来就是有序序列（合并）。这里合并是隐式的，因为划分后两段已经有序，直接拼接即可。

归并排序

归并排序把数组从中间切开（分解），分别对左右两半递归排序（求解），再把两个有序子序列合并成一个有序序列（合并）。这里合并是显式的，需要额外 O(n) 的工作量。

命题视角与易错点

命题人爱考“分治三步骤”的完整性。冒泡排序虽然也递归，但它只是不断交换相邻元素，没有把问题拆成更小的独立子问题，也没有合并步骤，所以不算分治。计数排序更是基于统计频次，连递归都没有，直接排除。

考频与趋势

根据历年 NOIP 提高组初赛数据，分治思想属于高频考点，近五年在算法选择题中出现过 4 次，主要集中在排序相关题目。2016 年这道题就是典型代表，命题人通过对比快排、归并、冒泡、计数四种排序，考察学生对分治本质的理解。

预测

从趋势看，未来几年分治思想仍会高频出现，尤其是排序、查找、树形 DP 等场景。命题人可能会继续用对比手法，比如加入“堆排序”或“基数排序”作为干扰项，测试学生是否真正理解分治的三步流程。暂无足够依据预测具体年份，但分治思想作为算法基石，必将是长期热点。