分治算法学习笔记。

1. 分治的基本概念

把一个任务，分成形式和原任务相同，但规模更小的几个部分任务 (通常是两个部分)，分别完成，或只需要选一部分完成。然后再处理完成后的这一个或几个部分的结果，实现整个任务的完成。

2. 分治的典型应用

2.1. 二分查找

二分查找函数中，为了防止 $L + R$ 过大溢出，建议使用 $mid = L + (R - L)/2$.

例题

2.2. 归并排序

数组排序任务可以如下完成：

  • 把前一半排序
  • 把后一半排序
  • 将两半归并到一个新的有序数组，然后再拷贝回原数组，排序完成。

2.3. 快速排序

数组排序任务可以如下完成：

  • 设 $k = a[0]$，将 $k$ 挪到适当位置，使得比 $k$ 小的元素都在 $k$ 左边,比 $k$ 大的元素都在 $k$ 右边，和 $k$ 相等的，不关心在 $k$ 左右出现均可 ($O(n)$ 时间完成)
  • 把 $k$ 左边的部分快速排序
  • 把 $k$ 右边的部分快速排序

3. 例题