1. 折半搜索

折半搜索是分治算法思想的一典型例子，要解决输入规模很大的问题时可以将该问题分解，得到k个不同的可独立求解的子问题，求出字问题的解之后再用合适的方法合并求出整个问题的解。将整个问题分解成若干小问题来处理的方法称为分治法.比如：找一个学校里身高最高的同学，可以现在每个班找出最高的，把每个班里最高的汇合在一起，找出全校最高的。
二分查找也叫折半搜索，在数组a[1…n]中搜索x,数组a中的元素不递减.如果找到x，则返回x所在的位置下标，否则返回-1.解决思想就是先讲x与数组中中间位置的元素相比较，x比中间元素值大，说明x取值在数组右半部分范围内，否则在左半部分，如此不断分割求解将x的范围不断缩小最后就可求出x的位置.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//二分查找
int bin_search(int a[],int n,int key){
   int left=1,right=n,middle;
   while(left<right){
      middle=(left+right)/2;
      if (key==a[middle])
      {
         return a[middle];
      }else if(key>a[middle]){
          left=middle+1;
      }else{
          right=middle-1;
      }
   }
   return -1;
}
int main(){
    int a[11]={0,1,2,3,4,5,6,7,8,9,10};
    printf("%d\n",bin_search(a,11,7) );
    printf("%d\n",bin_search(a,11,11) );

}

归并排序是在插入排序的基础上应用分治的思想而来的，先看插入排序.

2.冒泡排序

#include <stdio.h>

// 打印数组a
void printArr(int a[],int n){
    for (int i = 0; i < n; ++i)
    {
        printf("%d\t",a[i]);
    }
    printf("\n");
}

//冒泡排序
int bubble_sort(int a[],int n){
   int i,j;
   for (int i = 0; i < n-1; ++i)
   {
       for (j= i+1; j<n; ++j)
       {
          if (a[i]>a[j])
          { 
              int temp=a[i];
              a[i]=a[j];
              a[j]=temp;
          }
       }
   }

   return 1;
}


int main(){
    int a1[]={1,4,2,15,6,37,28};
    printf("排序前：");
    printArr(a1,7);
    bubble_sort(a1,7);
    printf("排序后：");
    printArr(a1,7);
}
输出结果：
yaopans-MacBook-Pro:algorithm yaopan$ gcc bubble_sort.c 
yaopans-MacBook-Pro:algorithm yaopan$ ./a.out 
排序前：1   4   2   15  6   37  28  
排序后：1   2   4   6   15  28  37

折半搜索和插入排序都是在非递减数组中进行的，对于无序数组可以先冒泡排序.

3.插入排序

向有序数组中插入元素

//向有序数组中插入元素

void insertArr(int a[],int n,int e){
     int i; 
     for (i = n-1; i>0; --i)
     {
        if (a[i]>e){
            a[i+1]=a[i];
        }else{
            break;
        }

     }
     a[i+1]=e;
}

插入排序就是利用向有序数组中插入元素的思想进行排序，数组中第一个元素a[0]放在最开始，a[1]比a[0]小，则交换a[0]和a[1]的位置，否则a[1] 插在a[0] 的后面.这样第一次插入a[0]和a[1] 已经排列好了，再来第三个元素插入到前两个元素中去，以此类推.下面是插入排序的代码：

#include <stdio.h>
// 打印数组a
void printArr(int a[],int n){
    for (int i = 0; i < n; ++i)
    {
        printf("%d\t",a[i]);
    }
    printf("\n");
}

//插入排序，参数为数组a和数组长度n
void insertSort(int a[],int n){
    int i,e,j;
    for (i = 1; i < n; ++i)
    {
        e=a[i];
        for (j=i-1;j>=0;--j)
        {
            if (e<a[j])
            {
                a[j+1]=a[j];
            }else{
                break;
            }
        }
        a[j+1]=e;
    }
}
int main(){
    int a1[]={556,90,6,89,1,4,2,15,6,37,28};
    printf("排序前：");
    printArr(a1,11);
    insertSort(a1,11);
    printf("排序后：");
    printArr(a1,11);

}
yaopans-MacBook-Pro:algorithm yaopan$ ./a.out 
排序前：556 90  6   89  1   4   2   15  6   37  28  
排序后：1   2   4   6   6   15  28  37  89  90  556

4.归并排序

#include <stdio.h>
#include <stdlib.h>
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;

    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);    //左边有序
        mergesort(a, mid + 1, last, temp); //右边有序
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    }
}

bool MergeSort(int a[], int n)
{
    int *p= new int[n];
    if (p == NULL)
        return false;
    mergesort(a, 0, n - 1, p);
    delete[] p;
    return true;
}
//打印数组
void printArr(int a[],int n){
    for (int i = 0; i < n; ++i)
    {
        printf("%d\t",a[i]);
    }
    printf("\n");
}
int main(){
    int a[]={1,4,5,7,3,10,56,23,54};
    int c[]={};
    MergeSort(a,9);
    printArr(a,9);
}