分治策略的基本思想

基本思想

将一个难以直接解决的大问题，分解成一些规模较小的相同的子问题，各个问题相互独立；递归地解决各个子问题，将子问题的解归并成原问题的解

分治策略

1. 将原始问题划分或者归结为规模较小的子问题
2. 递归或者迭代求解每个子问题
3. 将子问题的解 综合 或者 不综合 得到原问题的解

注意

1. 子问题和原问题性质完全一样
2. 子问题之间可彼此独立地求解
3. 递归停止时子问题可直接求解

二分查找

设计思想：

• 通过x与中位数比较，将原问题归结为规模减半的子问题，对子问题进行二分检索
• 当子问题规模为1时，继续比较x与T[m]，若相等则返回m，否则返回特殊值
  非递归写法：

BinarySearch(T,l,r,x)
T：数组；l：左边界；r：右边界；x：目标数。

伪代码：

l <- 1; r <-n;
while l<=r do
	m <- [(l+r)/2]	// m为中间位置
	if T[m] = x then return m	// 中位数就是目标值，直接返回中位数下标
	else if T[m] > x then r <- m-1
	else l <- m+1

return 0

递归写法：

BinarySearch(s[n],x,int low, int high)
s[n]：数组；x：目标数；low：左边界；high：右边界。

输入：查找序列s，要查找的元素x，查找范围
输出：查找结果：元素所在位置 或 -1

伪代码：

if(low < high) then return -1;
middle <- (low+high)/2;	// 分解
if(x=s[middle]) then return middle;
else if(x>s[middle]) then
	return BinarySearch(s,x,middle+1, high);
else 
	return BinarySearch(s,x,low, middle-1);

使用递归的话，时间复杂度为O(logn)，空间复杂度为O(logn)（由于递归深度是O(logn)）

循环赛日程表

题目：

2个运动员：

4个运动员:

8个运动员:

伪代码：

算法： arrange(p, q, n, arr)， 其中 n=2^k
输入：子问题的位置（p,q）， 子问题的规模n，循环赛日程表arr[0][i]。这里==（p,q）是左上角的坐标==
输出：arr[][]

if(n>1) then
{
	arrange(p, q, n/2, arr)		// 左上角递归
	arrange(p, q+n/2, n/2, arr)		// 右上角递归
}

for i<- p+n/2 to p+n do				// 右上 拷贝到 左下
	for j<- q to q+n/2 do
	arr[i][j] <- arr[i-n/2][j+n/2]

for i<- p+n/2 to p+n do				// 左上 拷贝到 右下
	for j<- q+n/2 to q+n do
	arr[i][j] <- arr[i-n/2][j-n/2]

return arr

为了方便，其实我们实际代码编写的时候，并非按照我们上边介绍的那样 左上 -> 右下， 右上 -> 左下
而是按照 1、右上 -> 左下 2、左上 -> 右下 的顺序

时间复杂度 O(n^2)
空间复杂度 O(logn)

归并排序

详细可以看我这篇文章：【八大排序算法】
算法思想：
合并排序是采用分治策略实现对n个元素进行排序的算法，采用二分分治策略

1. 分解：将待排序元素分为大小大致相同的两个子序列，从中间一份二
2. 合并：分别对两个子序列递归，将排好序的两个子序列进行合并，得到一个有序序列

C++代码实现：

主方法MergeSort

合并方法Merge（核心逻辑）：

时间复杂度 O(nlogn)
空间复杂度 O(n)（需要临时数组，以及栈空间）

快速排序

• 分：选定一个元素作为基准元素，小于基准元素的放左边，大于基准元素的放右边
• 递归求解子问题

详细可以看我这篇文章：【八大排序算法】

书上伪代码：(这个效率不是太高哈)
算法Quicksort(A, p, r) // p, r为待排序元素下标
输入：数组A[p…r]
输出：排好序的数组A

Quicksort：

if p<r
then q <- Partition(A,p,r)	// 划分后返回q为基准的位置
A[p] <-> A[q]	// 首元素和对应位置元素交换
Quicksort(A,p,q-1)
Quicksort(A,q+1,t)

初始值 p=1， r=n

Partition方法：

改进版：（了解即可）

交换不正确元素的位置，我们只交换 左边不符合的值 和 右边不符合的值，这样就不需要再与轴点去交换了，减少不必要的交换次数

Partition(A,p,r)从左右两方扫描，交换不正确位置的元素，直到扫描结束，将基准元素换到正确的位置
输入：数组A[p,r]
输出： j，（基准元素在排好序的数组中的位置）

Partition(A,p,r)伪代码：

x <- A[p]
i <- p
j <- r+1
while true do
	repeat j <- j-1
	until A[j] <= x		// 不超过基准元素的
	repeat i <- i+1
	until A[i] > x		// 比基准元素大的
	if i<j
	then A[i] <-> A[j]
	else return j

最坏时间复杂度：O(n^2)

子问题划分的越均匀，时间复杂度越好

平均时间复杂度：O(nlogn)