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