分治法：将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解就可得到原问题的解。
递归二分法：O(log(2下标)N)
public int recFind(int search, int low, int high) {
int curIn = (low + high) / 2;
if(arrays[curIn] == search)
return curIn;
else if (low > high)
return mError;
else {
if(arrays[curIn] < search)
return recFind(search, curIn + 1, high);
else
return recFind(search, low, curIn - 1);
}
}
汉诺塔：
当只有一个盘子的时候，只需要从将A塔上的一个盘子移到C塔上。
当A塔上有两个盘子时，先将A塔上的1号盘子（编号从上到下）移动到B塔上，再将A塔上的2号盘子移动的C塔上，最后将B塔上的小盘子移动到C塔上。
当A塔上有3个盘子时，先将A塔上编号1至2的盘子（共2个）移动到B塔上（需借助C塔），然后将A塔上的3号最大的盘子移动到C塔，最后将B塔上的两个盘子借助A塔移动到C塔上。
当A塔上有n个盘子是，先将A塔上编号1至n-1的盘子（共n-1个）移动到B塔上（借助C塔），然后将A塔上最大的n号盘子移动到C塔上，最后将B塔上的n-1个盘子借助A塔移动到C塔上。
综上所述，除了只有一个盘子时不需要借助其他塔外，其余情况均一样（只是事件的复杂程度不一样）。
public static void hanNouta(int top, char from, char inter, char to) {
if(top == 1) {
System.out.println("Disk 1 from " + from + " to " + to);//直接放入目标塔
} else {
hanNouta(top - 1,from,to,inter);//借助目标塔将初始塔的n-1个放到借用塔
System.out.println("Disk " + top + " from " + from + " to " + to);//将最后一个盘子放到目标塔
hanNouta(top - 1, inter, from, to);//借用塔n-1个移到目标塔
}
}
归并排序：O(N*logN)
归并的顺序是这样的：先将初始数组分为两部分，先归并低位段，再归并高位段。对低位段与高位段继续分解，低位段分解为更细分的一对低位段与高位段，高位段同样分解为更细分的一对低位段与高位段，依次类推。
上例中，第一步，归并的是6与2，第二步归并的是7和4，第三部归并的是前两步归并好的子段[2,6]与[4,7]。至此，数组的左半部分（低位段）归并完毕，然后归并右半部分（高位段）。
所以第四步归并的是8与1，第四部归并的是5与3，第五步归并的是前两步归并好的字段[1,8]与[3,5]。至此，数组的右半部分归并完毕。
最后一步就是归并数组的左半部分[2,4,6,7]与右半部分[1,3,5,8]。
归并排序结束。
public void merge(int[] data, int low,int mid, int hight){
int j = 0;
int lowBegin = low;//低位段的起始下标
int lowEnd = mid; //低位段的结束下标
int hightBegin = mid + 1;//高位段的起始下标
int hightEnd = hight;//高位段的结束下标
int n = hight - low + 1; //归并的元素总数
while(lowBegin<=lowEnd && hightBegin<=hightEnd){
if(arrays[lowBegin]<arrays[hightBegin]){
data[j++] = arrays[lowBegin++];
}else{
data[j++] = arrays[hightBegin++];
}
}
// 若第一段序列还没扫描完，将其全部复制到合并序列
while(lowBegin<lowEnd){
data[j++] = arrays[lowBegin++];
}
// 若第二段序列还没扫描完，将其全部复制到合并序列
while(hightBegin<hightEnd){
data[j++] = arrays[hightBegin++];
}
for(j=0; j<n; j++){//将归并好的元素复制到array中
arrays[low] = data[j];
}
}
public void recMergeSort(int[] arrays,int low, int high) {
if(low == high)
return;
else {
int mid = (low + high)/2;
recMergeSort(arrays, low, mid);//对低位段归并排序
recMergeSort(arrays, mid + 1, high);//对高位段归并排序
merge(arrays, low, mid + 1, high);
}
}
