### 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);
}
~~~
