1. 插入排序
什么是插入排序？
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
1.1 简单插入排序
代码实现如下：
void InsertSort(int*a,int length){
int i,j;
for(i=1;i<length;i++){ //从1开始是因为下标为0之前没有元素
if(a[i]<a[i-1]){
int key=a[i];
j=i-1;
while(j>=0&&key<a[j]){ //直到找到大于a[j]的数 或者j=-1，插入在第一个位置
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
}
int main(){
int a[]={1,2,7,4,5,9,6};
int length=sizeof(a)/sizeof(a[0]);
InsertSort(a,length);
for(int i=0;i<length;i++){//打印
printf("%d ",a[i]);
}
return 0;
} 但我们认为这种插入的方法仍有改进的可能，所以我们创建了一种新的插入方法? -- 折半插入
注意：我们这里实现的都是从小到大排序！
代码实现如下：
void InsertSort(int*a,int length){
int i,j,left,right;
for(i=1;i<length;i++){ //从1开始是因为下标为0之前没有元素
int key=a[i];
left=0;
right=i-1;
while(left<=right){
int mid = (left+right)/2;
if(a[mid]>key){
right=mid-1;
}else{
left=mid+1;
}
}
for(j=i-1;j>=right+1;j--){
a[j+1]=a[j];
}
a[right+1]=key;
}
}1.2 希尔排序
希尔排序也是一种插入排序，我们发现在排序前越接近基本有序，插入排序的效率就越高，为了提高我们的效率，我们可以进行多次跨越排序，尽可能的使得我们的排序速率更快。
实现代码如下:
void ShellSort(int*a,int d,int length){
int i,j;
for(;d>=0;d-=2){//逐渐减少步幅，直到为1就成为了普通插入排序
for(i=d;i<length;i++){
if(a[i]<a[i-d]){
int key=a[i];
for(j=i-d;j>=0&&key<a[j];j-=d){
a[j+d]=a[j];
}
a[j+d]=key;
}
}
}
}
int main(){
int a[]={1,2,7,4,5,9,6};
int length=sizeof(a)/sizeof(a[0]);
ShellSort(a,5,length);
for(int i=0;i<length;i++){
printf("%d ",a[i]);
}
return 0;
} 
