分治思维的几个算法：二分检索、快排、归并排序

分治思想的几个算法：二分检索、快排、归并排序

/*分治思想的各种算法*/
#include <stdlib.h>
#include <stdio.h>

/*二分检索算法*/
int BinarySearch(int a[],int n,int e)
{
    int index;
    int low=0,high=n-1, mid;

    while(low <= high)
    {
        mid = (low + high) / 2;
        if(e == a[mid])return mid;
        else if(e > a[mid])low = mid + 1;
        else high = mid - 1;
    }

    if(low >= high)return -1;
}

/*归并排序算法*/
void MergeSort(int a[],int low,int high)
{
    int mid;
    int temp[100],i,j,k;

    if(high == low)return;

    /*先细分排序*/
    mid = (low + high)/2;
    MergeSort(a,low,mid);
    MergeSort(a,mid+1,high);

    /*再归并*/
    i=low,j=mid+1,k=0;
    while(i<=mid && j<=high)
    {
        if(a[i] < a[j])temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    for(;i<=mid;)temp[k++] = a[i++];
    for(;j<=high;)temp[k++] = a[j++];

    for(i=low,j=0;i<=high;)a[i++] = temp[j++];
}
/*快排,快速划分*/
int Partion(int a[],int low,int high)
{
    int v = a[low];

    if(low >= high)return;

    while(low < high)
    {
        while(a[high] >= v && high > low)high--;
        a[low] = a[high];

        while(a[low] <= v && high > low)low++;
        a[high] = a[low];
    }
    a[low] = v;

    return low;
}
void QuickSort(int a[],int low,int high)
{
    int index;
    if(low >= high)return;
    index = Partion(a,low,high);
    QuickSort(a,low,index-1);
    QuickSort(a,index+1,high);
}
/*打印出来*/
void print(int a[],int n)
{
    int i = 0;
    while(i < n)printf("%d\t",a[i++]);
    printf("\n");
}
int main(int argc, char *argv[])
{
    //int a[] = {0,1,2,3,4,5,6,7,8,9};
    int a[] = {2,4,6,8,9,7,5,3,1,0};
    int n = 10;

    QuickSort(a,0,9);
    print(a,10);
    printf("Position : %d\n",BinarySearch(a,n,4));

    return 0;
}