分治法

1. 解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的： 解决子问题所需的工作总量（由 子问题的个数、解决每个子问题的工作量 决定）
   
2. 合并所有子问题所需的工作量
   
3. 分治法是把任意大小问题尽可能地等分成两个子问题的递归算法
   

CODE:  [Copy to clipboard]

---

begin 　｛开始｝
　　　 if ①问题不可分 then ②返回问题解 　
　　　　 else begin
　　　　　　 　　③从原问题中划出含一半运算对象的子问题1；
　　　　　　 　　④递归调用分治法过程，求出解1；
　　　　　　 　　⑤从原问题中划出含另一半运算对象的子问题2；
　　　　　　 　　⑥递归调用分治法过程，求出解2；
　　　　　　 　　⑦将解1、解2组合成整修问题的解； 　
　　　　　　　end;
　　 end; {结束}

CODE:  [Copy to clipboard]

---

m:=a[1];
for i:=2 to n do
if m < a[i] then m:=a[i];        (或者一次选择排序)
p:=1;
for i:=2 to n do
if a[p]<a[i] then p:=i;
m:=a[p];

CODE:  [Copy to clipboard]

---

｛maxmin｝
　①if 问题不可分：n=2
　②问题的解求得（两个元素时）：对两元素进行比较;return;
　③for i:=1 to n div 2 do b[i]:=a[i]
　④maxmin(n div 2,b,max1,min1)，其中max1和min1为解1
　⑤for i:=1 to n div 2 do b[i]:=a[i+ n div 2]
　⑥maxmin(n div 2,b,max2,min2)，其中max2和min2为解2
　⑦max:=maxnum(max1,max2);
　　min:=minnum(min1,min2);
{maxmin}
其中对函数maxnum的求精：
function maxnum(a,b:integer):integer;
　begin
　　if a>b then maxnum:=a else maxnum:=b;
　end;

1. 分解(Divide) 以元素a[p]为基准元素将a[p：q-1]划分为三段a[p：q-1]，a[q]和a[q+1：r]，使得a[p：q-1]中任何一个元素都小于a[q]，a[q+1：r]中任何一个元素大于等于a[q]，下标q在划分中确定。
   
2. 递归求解(Conquer) 通过递归调用快速排序算法分别对a[p:q-1] 和a[q+1:r]进行排序。
   
3. 合并(Merge) 由于a[p:q-1] 和a[q+1:r]的排序都是在原位置进行的，所以不必进行任何合并操作就已经排好序了。
   

CODE:  [Copy to clipboard]

---

procedure table(k:integer;a:array[1..u1,1..u2] of integer);
var n,i,j,m,s,t:integer;
begin
　　n:=1;
　　for i:=1 to k do n:=n*2;
　　for i:=1 to n do a[1,i]:=i;
　　m:=1;
　　for s:=1 to k do
　　　begin
　　　　n:=n / 2;
　　　　for t:=1 to n do
　　　　for i:=m+1 to 2*m do
　　　　　for j:=m+1 to 2*m do
　　　　　　begin
　　　　　　　a[i,j+(t-1)*m*2]:=a[i-m,j+(t-1)*m*2-m];
　　　　　　　a[i,j+(t-1)*m*2-m]:=a[i-m,j+(t-1)*m*2];
　　　　　　end;
　　　　　m:=m*2;
　　　end;{for s}
end;