认识“分治”思想

⚡ 30 秒速记

• 分治把原问题拆成规模更小、结构相同的子问题，分别求解后再合并结果
• 递归函数必须有可直接求解的基线，并保证每次子问题规模严格缩小
• 切分点和区间开闭要全程统一，合并步骤必须覆盖所有子结果

分治的本质是把一个大问题拆成若干个规模更小、结构相同的子问题，分别求解后再合并成原问题的答案。 使用递归实现时必须设置可直接求解的边界，并保证每次拆分后问题规模都会缩小，否则无法正常结束。落到排序问题里，我一般会重点检查切分区间是否统一，以及合并过程是否完整覆盖每个子问题的结果。

本节我们要学习的两个排序算法都是对“分治”思想的应用。 “分治”，分而治之。其思想就是将一个大问题分解为若干个子问题，针对子问题分别求解后，再将子问题的解整合为大问题的解。

利用分治思想解决问题，我们一般分三步走：

• 分解子问题
• 求解每个子问题
• 合并子问题的解，得出大问题的解

下面我们一起来看看分治思想是如何帮助我们提升排序算法效率的。

💬 面试官追问

• 评审一个排序页面时，有人把数组切成两半并分别排好序，却直接拼接左右结果；为什么这还不能算完整的分治？

  左右子数组各自有序并不能保证拼接后的整体有序，例如左侧最大值可能大于右侧最小值。分治必须包含分解、求解和整合三个环节，整合规则还要能把子问题的解可靠地转化为原问题的解；缺少合并就只完成了局部求解。

• 你要在代码库里实现一种分治排序，递归函数的输入、返回值和终止条件会怎样设计，才能让团队容易验证？

  递归函数应接收边界明确的待排序区间或数组，并返回该范围的有序结果；规模缩小到单个元素时直接返回。调用方只依赖“返回结果有序”这一约定，合并逻辑集中处理子结果；若区间开闭混用，可能出现漏项或递归不收敛。

• 如果数据规模增大后递归层数成为运行环境的约束，分治思想是否必须放弃？

  不必放弃分治，受限的是递归实现形式，而不是分解、求解、合并的结构。可以改成自底向上的迭代流程，从小规模子问题开始逐层合并；代价是控制逻辑更显式，也需要谨慎处理末尾不足一个完整分组的区间。

• 线上排序接口偶发返回缺少元素的数组，日志显示每个叶子子问题都正常，你会优先检查分治流程的哪一段？

  应优先检查合并阶段，因为叶子结果正确只说明分解和最小子问题求解没有明显异常。核对每个子结果是否都被消费、某一侧耗尽后剩余部分是否保留，并对比分解前后的元素数量；若切分本身存在重叠或空洞，还需回查区间边界。

• 同事主张把问题尽可能多切几份，另一位坚持每次只切两份；你会依据什么决定，而不是把“分得更多”当成更高效？

  切分数量应服从子问题是否易解以及结果是否易于合并，而不是越多越好。二分通常让边界和合并过程更直观，多分可能减少层数却增加一次整合的参与方；最终还要结合执行环境、数据访问方式和合并成本判断。

归并排序

⚡ 30 秒速记

• 分到单元素，再用双指针合并两个有序段。
• 每层处理 n 个元素，共 log n 层：时间稳定为 O(n log n)。
• 数组版本通常需 O(n) 辅助空间；相等时先取左段可保持稳定。
• 适合链表、外部排序和需要稳定性的场景。

归并排序会先把数组不断拆到单个元素，再通过双指针把两个有序区间线性合并，真正的排序发生在合并阶段。 每一层都会处理全部 n 个元素，一共有 log n 层，所以时间复杂度稳定为 O(n log n)，数组实现通常还需要 O(n) 辅助空间。合并时若元素相等就先取左侧，可以保持稳定性，因此它适合链表、外部排序或明确要求稳定排序的场景。