分治

定义

分治（英语：Divide and Conquer），字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

过程

分治算法的核心思想就是「分而治之」。

大概的流程可以分为三步：分解 -> 解决 -> 合并。

1. 分解原问题为结构相同的子问题。
2. 分解到某个容易求解的边界之后，进行递归求解。
3. 将子问题的解合并成原问题的解。

分治法能解决的问题一般有如下特征：

• 该问题的规模缩小到一定的程度就可以容易地解决。
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

快速排序模板

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序模板

void merge_sort(int q[], int l, int r)
{
    if (l >= r)
	{
		return;
	}

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if (q[i] <= q[j])
		{
			tmp[k++] = q[i++];
		}
        else
		{
			tmp[k++] = q[j++];
		}
    	
	}

    while(i <= mid)
	{
		tmp[k++] = q[i++];
	}
    while(j <= r)
	{
		tmp[k++] = q[j++];
	}

    for(i = l, j = 0; i <= r; i++, j++) 
	{
		q[i] = tmp[j];
	}
}