直接插入排序 (稳定）O(
)
希尔排序（不稳定）O(
)
冒泡排序（稳定）O()
快速排序（不稳定）O()
直接选择排序（不稳定）O()
堆排序（不稳定）O()
归并排序（稳定）O()
基数排序（稳定）
二分查找在最下面....
直接插入：
分析：
1，从第一个数的下一个数开始外层遍历
2，然后用当前这个数和这个数前面的所有数进行比较，比他大的数就向后移动移动，提前把这个数弄到一个temp中存储起来。
3，一直到这个数碰到比他小的数就退出，并把temp的值赋予退出这个位置
具体举例：
5,6,1,7,4,8,3,2,9
第一次：从6开始往后遍历，用6和5比较
5,6,1,7,4,8,3,2,9
第二次：用1和6比，6>1,所以6向后移动一位，1然后和5比，5>1,所以5也向后移动一位
1,5,6,7,4,8,3,2,9
第三次：用7和前面的比较
....一直类似的比较到最后
1,2,3,4,5,6,7,8,9
具体算法：
int a[6]={1,2,3,2,1,6};
int i,j,temp;
// 插入排序
for(i=1;i<N;i++){
temp=a[i];
for(j=i-1;j>=0;j--){
if(a[j]>temp){
a[j+1]=a[j];
}else{
break;
}
}
a[j+1]=temp;
}
希尔排序：
分析：他是一种缩小增量排序，将相隔某个增量的记录组成一个子序列，这个序列采用的直接插入排序，增量一趟一趟都在减少，知道减少到1，进行最后一次排序
比如：49 38 65 97 76 13 27 49 55 04
增量是5,3,1
一趟排序：49 38 65 97 76 13 27 49 55 04
其中 49和13,38和27,65和49...
13 27 49 55 04 49 38 65 97 76
二趟排序：
13,55,38,76排序，27,04,65排序，49,49,97排序
13 04 49 38 27 49 55 65 97 76
三趟排序：
14 13 27 38 49 49 55 65 76 97
折半插入：
void b_insert(int *a,int len){
int i,j,temp,m,low,high;
for(i=1;i<len;i++){
low=0;
high=i-1;
while(low<=high){
m=(low+high)/2;
if(a[m]>a[i]){
high=m-1;
}else{
low=m+1;
}
}
temp=a[i];
for(j=i;j>high+1;j--){
a[j]=a[j-1];
}
a[high+1]=temp;
}
}
冒泡排序：
分析：记录两两比较关键字，如果前面的比后面的大，就交换，每一次排序，都保证有最大的升上去了，有n个记录，外层比较次数，n-1，内层每次比较n-i-1
这个比较简单，就不举例了，直接上算法：
for(i=0;i<N-1;i++){
int leap=1;
for(j=0;j<N-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
leap=0;
}
}
if(leap){
break;
}
}
快速排序：
分析：
1，找一个中枢记录，一般是第一个值
2，i指向第一个值，j指向最后一个值
3，如果j==i，就把中枢记录赋值给a[i]
4，如果j>i,一直循环，如果a[j]>=中枢，j--，否则，a[i]=a[j]
5，如果j>i,一直循环，如果a[i]<=中枢，i++，否则，a[j]=a[i]
6，采用递归的形式，进行排序
比如：49 38 65 97 76 13 27 49
取p=49
i=0,j=7,分别指向第一个和最后一个值
第一趟排序的过程：
27(i) 38 65 97 76 13 _j_ 49
27 38 _i_ 97 76 13 65(j) 49
27 38 13(i) 97 76 _j_ 65 49
27 38 13 _i_ 76 97(j) 65 49
完成一趟排序：27 38 13 49(i,j) 76 97 65 49
第二趟排序：
{27 38 13 } 49 { 76 97 65 49}
{13(i) 38 _j_} 49 { 49(i) 97 65 _j_}
{13 _i_ 38(j)} 49 {49 _i_ 65 97(j)}
{13 27 38} 49 { 49 65(i) _j_ 97}
完成两趟排序：{13 27(i,j) 38} 49 {49 65 76(i,j) 97}
......{13 27 38 49 49 65 76 97}
具体代码，有递归和非递归算法：
#include <iostream>
using namespace std;
int zhixing(int *a,int low,int high){
int key=a[low];
int i=low;
int j=high;
while(i<j){
while(i<j && a[j]>=key){
j--;
}
if(i<j){
a[i]=a[j];
i++;
}
while(i<j && a[i]<=key){
i++;
}
if(i<j){
a[j]=a[i];
j--;
}
}
a[i]=key;
return i;
}
void kp(int *a,int low,int high){
if(low<high){
int p=zhixing(a,low,high);
kp(a,0,p-1);
kp(a,p+1,high);
}
}
//非递归算法
void fei_kuaipai(int *a,int low,int high){
//使用栈，来存储每次分开的列的头和尾
//使用上面的zhixing(a,low,high)这个方法，把每次的列都排好序，low和high从栈中取出，一直到栈为空，就排完序了
int mid=zhixing(a,low,high);//首先把这个数组分开，mid左边都是比他小的，右边都是比他大的
//定义一个栈
stack<int> s;
if(low<mid-1){
s.push(low);
s.push(mid-1);
}
if(high>mid+1){
s.push(high);
s.push(mid+1);
}
while(!s.empty()){//栈为空退出循环
low=s.top();
s.pop();
high=s.top();
s.pop();
mid=zhixing(a,low,high);//在对子序列进行排序
if(low<mid-1){
s.push(low);
s.push(mid-1);
}
if(high>mid+1){
s.push(high);
s.push(mid+1);
}
}
}
int main()
{
//快速排序
int a[6]={1,2,3,4,2,1};
kp(a,0,5);
fei_kuaipai(a,0,5);
int i;
for(i=0;i<6;i++){
cout<<a[i]<<" ";
}
return 0;
}
选择排序：
分析：
1，每次保证确定是最小的，从0开始遍历，每次都假设第一个数是最小的，向后遍历
2，如果碰到比这个数小的，就把下标赋值给min
3，判断一下看这个最小的是否还是刚开始的，如果不是，就把最小的和这个数交换位置
4，然后进行下次遍历，保证最前面是最小的
代码如下：
for(i=0;i<N;i++){
int min=i;
for(j=i+1;j<N;j++){
if(a[j]<a[min]){
min=j;
}
}
if(min!=i){
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
堆排序：
构建大顶堆（父大于子），或构建小顶堆（父小于子），然后进行调整，再构建，在调整，....直到最后的根节点，排序完成。
归并排序：
2路归并排序---先对子集排序，归并
比如：
3 2 5 1 6 8 4
第一趟：{2 3} {1 5} {6 8 } {4}
第二趟：{1 2 3 5 } { 4 6 8}
第三趟：{1 2 3 4 5 6 8}
基数排序（桶排序）：
分析：
从个位开始进行第一趟，下来的是从小到大排序的，每次依序进入桶中，进入完成之后，从下面依次出来，然后在从十位开始进入，...直到最后一趟，排序完成
二分查找：
分析：必须是有序序列，才可以进行二分查找，在做题的过程中可以构造折半二叉树，就是一颗二叉排序树。每次找的中间的数都是下标(a+b)/2向下取整的下标对应的数。
算法：
int min=0,max=N-1,mid=(min+max)/2;
int n;
scanf("%d",&n);
while(min<=max){
if(a[mid]==n){
printf("%d ",mid);
break;
}else if(n>a[mid]){
min=mid+1;
}else if(n<a[mid]){
max=mid-1;
}
mid=(max+min)/2;
}
