算法导论-递归

递归程序在设计时很常见,有时能很大程度上简化问题解决的复杂性.

下面就算法导论的2.3-4习题进行解答.

具体就是写出插入排序的递归版本.

void insert_sort(int a[],int n)
{
    if(n==1) return ;
    else
    {
        insert_sort(a,n-1);
        int i=n-1,temp=a[n];
        while(a[i]>=temp&&i>=1) a[i+1]=a[i],i--;
        a[i+1]=temp;
    }
}

瞧,过程很简洁.

但是要注意这个写法的效率是很低的.不论是空间还是时间都消耗很大.

递归式为:t[n]=t[n-1]+cn,所以时间消耗是n^2的.

另有一点需要说明,调用它时最大消耗递归栈空间有N个栈空间,通常栈空间是有限的,不可能无限制的随意使用递归啊.否则输入数据的变化多端很容易导致系统崩溃.

另延伸一点:2.3-5习题:

习题要求我们做出有关有序二分搜索的例子.

大致思想在题目中就给出了.下面我用代码实现一下子.

void binary_search(int a[],int le,int ri,int x)
{
    while(le<=ri)
    {
        int mid=(le+ri)/2;
        if(a[mid]==x) return mid;
        else if(a[mid]<x) le=mid+1;
        else ri=mid-1;
    }
    return -1;
}

int binary_sear(int a[],int le,int ri,int x)
{
    int mid=(le+ri)/2;
    if(le>ri) return -1;
    if(a[mid]==x) return mid;
    else if(a[mid]>x) return binary_sear(a,le,mid-1,x);
    else return binary_sear(a,mid+1,ri,x);
 }

以上仅限于有序数组的数字的二分搜索.  具体的搜索可视情况而定.

至于2.3-6习题.

显然是不能用二分搜索来优化结果的.这是源于数组自身的缺陷,导致其不能在常数时间内完成数据的插入和删除.

不过我们还是可以用二分搜索来尝试一下的.

但是我是不会去尝试的.

最后,2.3-7习题的解答是有点复杂的.

我能想到的就是先用归并排序,在对其进行遍历,对每一层遍历都尝试用二分搜索来看看是否有能够匹配的?时间也是nlogn