算法学习（一）：递归与分治策略（2）

几个经典题目

1.二分搜索：给定已排好序的n个元素a[0:n-1]，现要在这n个元素中找出一指定元素x。

比较简单，直接贴代码

int binary_search(int a[],int x)//二分搜索，找到x返回角标，不存在则返回-1；
{
   int low=0,high=n-1;
   while(low<=high)
   {
       int mid=(low+high)/2;
       if(a[mid]==x)
        return mid;
       else if(a[mid]>x)
        high=mid-1;//左搜索
       else
        low=mid+1;//右搜索
   }
   return -1；
}

对于两个有序数组，可通过一重循环，将其排序。将数组逐次分割，最后分割n个数组，可以认为此数组有序。然后在往回归并，最终得到有序数列。

完整代码如下：

#include <iostream>

using namespace std;
void merge_div(int low,int high);//分割，归并
void merge_sort(int low,int high,int mid);//排序
int a[10]={3,16,2,19,75,38,76,1};
void input();
int main()
{
    merge_div(0,7);
    input();
    return 0;
}
void merge_div(int low,int high)
{
    if(low>=high)
        return ;
    int mid=(low+high)/2;
    merge_div(low,mid);
    merge_div(mid+1,high);
    merge_sort(low,high,mid);
}
void merge_sort(int low,int high,int mid)
{
    int i=low,m=mid;
    int j=mid+1,n=high;
    int k=0;
    int t[20];
    while(i<=m&&j<=n)//对两个有序数组进行排序，并存到临时数组中
    {
        if(a[i]<a[j])
            t[k++]=a[i++];
        else
            t[k++]=a[j++];
    }
    while(i<=m)
        t[k++]=a[i++];
    while(j<=n)
        t[k++]=a[j++];
    k=0;
    for(int i=low;i<=high;i++)//将临时数组中的有序数列复制到原数组中
        a[i]=t[k++];
}
void input()
{
    for(int i=0;i<7;i++)
        cout<<a[i]<<" ";
    cout<<a[7]<<endl;
    return ;
}

3.快速排序

所谓快速排序，就是用最快的速度，将数组排好序。对于数组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在划分过程中确定。

②：排序:递归调用快速排序算法，分别对分好的区间排序

③：合并：在找点的过程中，以排好序，所以合并后已然排好序。

完整代码如下：

#include <iostream>
/*
    快速排序算法
*/
using namespace std;
int n;
int a[100];
void readdata();
void quicksort(int low,int high);
int position(int low,int high);
void input();
int main()
{
    readdata();//读入数据
    quicksort(0,n-1);//调用快速排序算法
    input();//输出已排好序的数列
    return 0;
}
void readdata()
{
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];
}
void quicksort(int low,int high)
{
    int pos;
    if(low<=high)
    {
        pos=position(low,high);//此点将数组分为两组，左边都比此点数据小，右边都比此点数据大
        quicksort(low,pos-1);//对左边调用快排
        quicksort(pos+1,high);//对右边调用快排
    }
    return ;
}
int position(int low,int high)
{
    int num=a[low];
    int i=low,j=high;
    while(i<j)
    {
        while(i<j&&a[j]>num)//从右向左找比num小的点。注意i<j是必要条件，否则会出bug
            j--;
        if(i<j)//将此点赋值给当前目标点位置
        {
            a[i]=a[j];
            i++;
        }
        while(i<j&&a[i]<num)//从左向右找比num大的点。注意i<j是必要条件，否则会出bug
            i++;
        if(i<j)//将此点赋值给当前目标点位置
        {
            a[j]=a[i];
            j--;
        }

    }
    a[i]=num;//将num赋值给找到的位置
    return i;//返回位置点
}
void input()
{
    for(int i=0;i<n-1;i++)
        cout<<a[i]<<" ";
    cout<<a[n-1]<<endl;
}