文档介绍：递归与分治算法
递归插入排序
Void insert_sort(type A[ ],int n)
{
int k;
type a;
n=n-1;
if (n>0)
{ insert_sort(A,n);
a=A[n];
k=n-1;
while (k>=0)&&A[k]>a))
{ A[k+1]=A[k];
k=k-1;
}
A[k+1]=a;
}
}
合并排序
public static void parable a[], int left, int right)
{
if (left<right) {//至少有2个元素
int i=(left+right)/2; //取中点
mergeSort(a, left, i);
mergeSort(a, i+1, right);
merge(a, b, left, i, right); //合并到数组b
copy(a, b, left, right); //复制回数组a
}
}
template <class Type>
void merge(Type c[],Type d[],int l,int m,int r)
{
int i = l,j = m + 1,k = l;
while((i<=m)&&(j<=r))
{
if(c[i]<=c[j])
{
d[k++] = c[i++];
}
else
{
d[k++] = c[j++];
}
}
if(i>m)
{
for(int q=j; q<=r; q++)
{
d[k++] = c[q];
}
}
else
{
for(int q=i; q<=m; q++)
{
d[k++] = c[q];
}
}
}
快速排序
private static void qSort(int p, int r)
{
if (p<r) {
int q=partition(a,p,r); //以a[p]为基准元素将a[p:r]划分成3段//a[p:q-1],a[q]和a[q+1:r],使得a[p:q-1]中任何元素小于等于a[q],//a[q+1:r]中任何元素大于等于a[q]。下标q在划分过程中确定。
qSort (p,q-1); //对左半段排序
qSort (q+1,r); //对右半段排序
}
}
int partition (int s[], int l, int r) //返回调整后基准数的位置
{
int i = l, j = r;
int x = s[l]; //s[l]即s[i]就是第一个坑
while (i < j)
{
// 从右向左找小于x的数来填s[i]
while(i < j && s[j] >= x)
j--;
if(i < j)
{
s[i] = s[j]; //将s[j]填到s[i]中,s[j]就形成了一个新的坑
i++;
}
// 从左向右找大于或等于x的数来填s[j]
while(i < j && s[i] < x)
i++;
if(i < j)
{
s[j] = s[i]; //将s[i]填到s[j]中,s[i]就形成了一个新的坑
j--;
}
}
//退出时,i等于j。将x填到这个坑中。
s[i] = x;
return i;
}
整数划分
 public static int divide(int n, int m){
        if (n < 1 || m < 1) {
            return 0;
        } else if (n == 1 || m == 1) {
            return 1;
        } else if (n == m) {
            return 1 + divide(n, n - 1);
        } else if (n < m) {
            return divide(n, n);
        } else {