分治的思想是把一个问题分解成几个部分，分别解决，最后再把结果合并起来得到最终的结果，排序算法中的归并排序和快速排序是典型的使用分治思想的算法。也可以是把问题的规模逐渐减小，最后再把解决的小问题逐渐合并起来，最终解决原始问题，比如求从1加到100和是多少，则问题可以简化为：前面99个数的和最后加100，前99和可以进一步简化为：前98个数的和加99，最终简化为前1个数的和加2, 函数可以写成如下：
int Sum(int n) {
if (n < 1) return n;
return n + f(n-1);
}
cout << Sum(100); // 5050归并排序
如下图所示，归并排序先把数组拆分成只有一个单位，这一个单位肯定是排序好的
然后把拆分的两个单位合并起来进行排序，因此每次排序相当于是对两个排序好的数组进行合并排序，如下图
代码如下
#include <iostream>
#include <cstring>
using namespace std;
//排序arr, 中间点是min，长度是len
void merge(int* arr, int mid, int len) {
if (len < 2)
return;
int* pos1 = arr;
int* pos2 = arr+mid;
int pos = 0;
int* rst = new int[len];
//逐个比较，选择小的放入rst
while (pos1 < arr+mid && pos2 < arr+len) {
if (*pos1 < *pos2)
{
rst[pos] = *pos1;
pos1++;
}
else
{
rst[pos] = *pos2;
pos2++;
}
pos++;
}
//剩下的追加到rst后面
while (pos1 < arr+mid) {
rst[pos] = *pos1;
pos1++;
pos++;
}
while (pos2 < arr+len) {
rst[pos] = *pos2;
pos2++;
pos++;
}
//更新到原来的数组中
memcpy(arr, rst, len*sizeof(int));
delete[] rst;
}
void MergeSort(int* arr, int len) {
if (len < 2)
return;
//拆分2部分
int pos = len/2;
MergeSort(arr, pos);
MergeSort(arr+pos, len-pos);
//合并2部分
merge(arr, pos, len);
}
int main() {
int arr[] = {3,4,6,33,7,9,4,6,9,95,3,19,6,8,9,7,4,3};
MergeSort(arr, 18);
for (int i = 0; i < 18; i++)
cout << arr[i] << " ";
return 0;
}
//输出
3 3 3 4 4 4 6 6 6 7 7 8 9 9 9 19 33 95 比赛日程安排
题目：2的N次方的选手进行互相比赛，求日程安排。例：2个选手的时候，意思是选手1第一轮和选手2比赛，选手2第一轮和选手1比赛。
4个选手的时候，如下图，可以把4个选手看成是2组2人的合并，左上角绿色部分是选手1，2一组，左下角红色则是选手3，4一组，合并后，右侧多出的2轮比赛安排是有规律的：右上角的取值其实是左下角红色部分的拷贝，右下角的取值则是左上角绿色部分的拷贝
当有8个选手的时候，也是一样的现象，因此，当有N个选手的时候，赛程表的安排可以利用分治法解。先把问题拆分，8个人拆分成2组4人，4人拆分成2组2人，最后再利用上面说的规律合并起来。这样就利用了典型的分治法思想进行解题，但是分治法只能解出一个解，如果说需要得到所有解，需要使用搜索法。
代码如下：
#include <iostream>
using namespace std;
int lists[8][8] = {0};
//规则：左上角与左下角合并：右下角等于左上角，右上角等于左下角
// 0 1 | 2 3
// 1 0 | 3 2
//-----|--------
// 2 3 | 0 1
// 3 2 | 1 0
void merge(int num, int counts) {
if (counts < 2)
return;
int hafe = counts/2;
//左上角的，填到右下角去
for (int i = num; i < num+hafe ; i++)
{
for (int j = 0; j < hafe; j++)
{
lists[i+hafe][j+hafe] = lists[i][j];
}
}
//左下角的填到右上角去
for (int i = num+hafe; i < num+counts ; i++)
{
for (int j = 0; j < hafe; j++)
{
lists[i-hafe][j+hafe] = lists[i][j];
}
}
}
void Schedule(int num, int counts) {
if (counts < 2)
return;
int pos = counts/2;
Schedule(num, pos);
Schedule(num+pos, pos);
//合并
merge(num, counts);
}
int main() {
for (int i = 0; i < 8; i++)
lists[i][0] = i; //每一行的第0个是自己
Schedule(0, 8);
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++)
cout << lists[i][j] << " ";
cout << endl;
}
return 0;
}
//结果
0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0最大子序列和
求一个数组中的最大子序列的和，如下数组，其最大子序列为： 4，-3，9，-1，-3，5， 和为11。所谓最大子序列就是需要数组中连续的数字，让他们的和最大。
int arr[] = {2, -3, 4, -3, 9, -1, -3, 5, -8, 6};同样可以用分治的思想解题：把数组一分为二，求最大子序列，也就是求左右两个子数组的最大子序列 外加 被左右拆分的子序列，三种序列种的最大值，就如上面这个数组，拆分成左右两个数组后，左数组的最大子序列为4，-3，9，右数组最大子序列为 6，被拆分的最大子序列为 4，-3，9，-1，-3，5，因此最大值是11，左右子数组可以继续拆分，直到只剩一个数字，就是最大子序列，再把他们重新组合起来，求得真正的最大子序列，就是类似归并排序的典型分治法
代码如下：
#include <iostream>
using namespace std;
//从前到后或从后到前的最大值, 如果小于0，则返回0
int maxValue(int* arr, int len, bool rbegin) {
if (len == 1)
return arr[0] > 0 ? arr[0] : 0;
int pos = 0;
int maxval = rbegin ? arr[len-1] : arr[0];
int sum = maxval;
for (int i = 1; i < len; i++)
{
pos = i;
if (rbegin)
pos = len-1-i;
sum += arr[pos];
if (sum > maxval)
maxval = sum;
}
return maxval > 0 ? maxval : 0;
}
int MaxSubSum(int *arr, int len) {
if (len == 1)
return arr[0];
int mid = len/2;
int maxlr = max(MaxSubSum(arr, mid), MaxSubSum(arr+mid, len-mid));
//再求左右之间的最大子序列
int maxmid = maxValue(arr, mid, true) + maxValue(arr+mid, len-mid, false);
return max(maxlr, maxmid);
}
int main() {
int arr[] = {2, -3, 4, -3, 9, -1, -3, 5, -8, 6};
cout << MaxSubSum(arr, 10) << endl;
return 0;
}
//输出结果
11