分治算法

早在几百年前，我国的古书《群经平议·周官二》里就有记载“分而治之”的思想。

数学归纳法与递归思想

\large{\color{orange}\texttt{To iterate is human,to recurse divine.\ —— \texttt{L. Peter Deutsch}}}

L. Peter Deutsch 这句话的意思是：“迭代的是人，递归的是神”。

数学归纳法的证明方式如下：
1. 证明当n= 1时命题成立。
2. 假设n=m时命题成立，那么可以推导出在n=m+1时命题也成立。（m代表任意自然数）

这个证明方式显然是用到了我们 OI 入门时讲到的一个很基础的算法：递归算法。

什么是分治？

但是，我们的主角并不是递归，而是在递归时通过划分区间，然后进行区间合并统计答案的算法：分治。

“分治”，即“分而治之”，先“分”，然后“治”，形象地说就是对于区间 $[l,r]$ ，先分区间，取区间中点 $\lfloor\frac{l+r}{2} \rfloor$ ，将其分为 $[l,mid]$ 和 $(mid,r]$ 分别进行操作，递归回溯时，对于两个区间进行合治，就是通过两个区间得到的我们想要的结果来合并出答案。

归并排序

背景介绍

在本世纪的前十几年里，pascal 时信息学竞赛的主流，由于没有 stl 和很多其他库函数的帮助，pascal 中必须手写一些数据结构和算法，归并排序就是当年没有 sort 时，选手们常写的一种排序。

实现思路

在这里拿归并先讲，主要原因是它是一个十分简单、易于理解、具有代表性的分治应用。

归并排序的思路是：当给一个数组排序的时候，先将数组分为两段，然后对两段分别进行归并排序，当分隔到每段长度为 $1$ 时，结束递归，然后对每两个区间进行合并（由于两个区间都是有序的，合并时使用双指针算法，将两个有序区间合并为一个有序区间，然后返回上一级递归，每次合并时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ ），所以整个归并排序时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$ 。

归并排序代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int zc[N];
void msort(int a[], int st, int ed) {
  if (st == ed) return;
  int mid = (st + ed) >> 1; //用 mid 分区间
  msort(a, st, mid), msort(a, mid + 1, ed); //分别处理两区间
  for (int i = st, j = mid + 1, k = 1; k <= ed - st + 1; ++k)
    if (i > mid) zc[k] = a[j], ++j;
    else if (j > ed) zc[k] = a[i], ++i;
    else if (a[i] > a[j]) zc[k] = a[j], ++j;
    else zc[k] = a[i], ++i; //合并两区间结果
  for (int i = 1, j = st; j <= ed; ++i, ++j)
  		a[j] = zc[i];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  msort(a, 1, n);
  for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
  return 0;
}