1.思想：

递归调用是用相同的方法去解决更小的问题，直到问题规模小于或等于某个边界条件时，不再进行递归（递归的出口），而是直接处理，然后不断向下执行函数返回结果。

2.分治法

1.当问题小到一定规模时，可以直接求解；

2.当问题规模较大时，可以分解为若干个相互独立的子问题，这些子问题与原问题具有相同的特征。若不能直接解决，则可分别递归求解；

3.原问题的解是子问题的解的组合。

3.折半查找

递归实现如下：

int BinSearch(int *arr,int key,int low,int high){

int mid = (low + high)/2; //取中

if(low>high)

return -1; //找不到目标关键字，也就是递归程序的出口

if(key = mid) //找到返回，出口

return mid;

else if(key

return BinSearch(arr,key,low,mid-1); //递归调用

else

return BinSearch(arr,key,mid+1,high);

}

4.归并排序

要点：采用分治法的策略，将已有的有序子序列合并为完全有序的序列，首先要让子序列有序，然后再使子序列间有序，最后等到完全有序的序列。

思想：将待排序序列R[0,...n-1]分为n个长度为1的子序列，讲相邻的子序列进行归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的 有序序列。

首先要做两步：

1.分解 ——将序列每次折半划分。

2.合并 ——将划分后的序列段两两合并后排序。

那么现在我们就要解决两个问题，怎么分解和合并？

分析： 在某趟归并中，设各子文件长度为length(最后一个子文件的长度可能小于length)，则归并前R[1..n]中共有n/length个有序的子文件：R[1..length]，R[length+1..2length]，…。 注意： 调用归并操作将相邻的一对子文件进行归并时，必须对子文件的个数可能是奇数、以及最后一个子文件的长度小于length这两种特殊情况进行特殊处理： ① 若子文件个数为奇数，则最后一个子文件无须和其它子文件归并(即本趟轮空)； ② 若子文件个数为偶数，则要注意最后一对子文件中后一子文件的区间上界是n。

一趟归并代码：

void Merge(int * a,int low,int mid,int high)

{

int i=low,j=mid+1,p=0;

int * r=new int[high-low+1];

while(i<=mid && j<=high)

{

r[p++]=(a[i]<=a[j])?a[i++]:a[j++];

}

while(i<=mid)

r[p++]=a[i++];

while(j<=high)

r[p++]=a[j++];

for(p=0,i=low;i<=high;p++,i++)

a[i]=r[p];

delete [] r;

}

void MergePass(int *a,int n,int length)

{

int i=0;

for(;i+2*length

{

Merge(a,i,i+length-1,i+2*length-1);

}

if(i+length<=n-1)

Merge(a,i,i+length-1,n-1);//尚有两个子文件，其中后一个长度小于length,归并最后两个子文件

//注意：若i≤n-1且i+length-1≥n-1时，则剩余一个子文件轮空，无须归并

}

二路归并代码：

//自底向上

void MergeSort(int *a,int n)

{

for(int length=1;length

MergePass(a,n,length);

}

5.快速排序

基本思想：首先从待排序中选定一个基数，通过关键字和基数的比较将待排序列划分为两个子序列，其中在基数前的都不大于基数；我们发现每次都是把基数归位。

划分算法：

int Partition(int arr[],int low,int high){

int temp =arr[low];

while(low

while(low=temp) --high;

arr[low] = arr[high]; //将 比temp小的移到低端

while(low

arr[high] = arr[low]; //将比temp大的移到高端

}

arr[low] = temp;

return low;

}

递归核心代码：

void QSort(int arr[],int s,int t){

int pirvotloc;

if(s

pirvotloc = Partition(arr,s,t); //进行划分并返回基数位置

QSort(arr,s,pirvotloc-1); //对基数前的子序列进行递归排序

QSort(arr,pirvotlov+1,t); //对基数后的子序列进行递归排序

}

}