分治算法

把一个大问题分为好几个小问题，然后再把结果合并。

特征：

分解后的小问题比较容易解决

可以分解为规模较小的相同问题

分解出来的子问题的接可以合并

各个子问题是相互独立的

二分查找的递归算法：

Fun(a[ ],left,right,key)

{

If(left > right)

Return -1

Int mid = (left+right)/2

If(a[mid]==key)

Return mid

Else if(key<[mid])

Return fun(a[ ],left,mid-1,key)

Else

Return fun(a[ ],mid+1,right,key)

}

归并排序：

MERGE-SORT(A, left, right)

if left < right

mid = (left + right) / 2

MERGE-SORT(A, left, mid)

MERGE-SORT(A, mid + 1, right)

MERGE(A, left, mid, right)

合并：

MERGE(A, left, mid, right)

创建临时数组 B

i = left

j = mid + 1

k = 0

while i ≤ mid and j ≤ right

if A[i] ≤ A[j]

B[k] = A[i]

i = i + 1

else

B[k] = A[j]

j = j + 1

k = k + 1

while i ≤ mid

B[k] = A[i]

i = i + 1

k = k + 1

while j ≤ right

B[k] = A[j]

j = j + 1

k = k + 1

将 B 中元素复制回 A[left…right]