内部排序之插入排序，希尔排序

<pre name="code" class="cpp">排序算法
 排序有内部排序和外部排序
 内部排序：数据记录在内存中排序
 外部排序：因排序的数据很大，一次不能容纳全部 的排序记录，在排序的过程中需要访问外存
插入排序 
 将一个记录插入到已排序好的有序表中，从而得到一个新记录数增1的有序表。
 即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。
直接插入排序
 基本思想： 1、首先把第一个元素单独看做一个有序序列，依次将后面的元素插入到该有序序列中；

 2、插入的时候，将该元素逐个与前面有序序列中的元素进行比较，找到合适的插入位置，形成新的有序序列；

<p> 3、当有序序列扩大为整个原始序列的大小时，排序结束。</p>

void insert_sort1(int *arr,int len){int i;//从第1个元素开始循环执行插入for(i=1;i<len;i++){//将第i个元素分别与前面的元素比较，插入适当的位置if(arr[i]<arr[i-1]){//一直向左进行比较，直到插入到适当的位置int key=arr[i];int count=0;//用来记录key在与前面元素时向左移动的位置while(i>0&&key<arr[i-1]){arr[i]=arr[i-1];arr[i-1]=key;i--;count++;}//将待插入的数字定位到下一个元素//i+=count;}}}void insert_sort2(int *arr,int len){int j,i;for(i=1;i<len;i++)for(j=i-1;j>=0&&arr[j]>arr[j+1];j--){//交换元素数值//由于不会出现自己与自己交换的情况//因此可以安全的用该交换方法arr[j]^=arr[j+1];arr[j+1]^=arr[j];arr[j]^=arr[j+1];}}void insert_sort3(int *arr,int len){int i,j;for(i=1;i<len;i++)if(arr[i]<arr[i-1]){//向前逐个比较，直到需要插入的地方int key=arr[i];for(j=i-1;j>=0&&arr[j]>key;j--)arr[j+1]=arr[j];arr[j+1]=key;//插入key}}
折半插入排序

直接插入排序算法简单，且容易实现，当待排序的长度n很小时，是一种很好的排序方法，尤其当原始序列接近有序时，效率更好。如果待排序的长度n很大，则不适宜采用直接排序。这时我们可以考虑对其做些改进，我们可以从减少比较和移动的次数入手，因此可以采用折半插入排序，其思想类似于折半查找
void binsert_sort(int *arr,int len)
{
int i;
for(i=1;i<len;i++)
{
int low=0;
int high=i-1;
int key=arr[i];
//循环直至要插入的两个点之间
while(low<=high)
{
int mid=(low+high)/2;
if(key<arr[mid])
high=mid-1;
else
low=mid+1;
}
//循环结束low=high+1;并且low位置即为key要插入的位置
//从low到i的元素依次后移一位
int j;
for(j=i;j>low;j--)
arr[j]=arr[j-1];
//将key插入到low位置
arr[low]=key;
}
}
折半插入排序减少了比较的次数，但是元素的移动次数并没有减少。
希尔排序
又称“缩小增量排序”，也是一种属于插入排序类的方法
基本思想：
先将这个待排记录序列分割成为若干个子序列分别进直接插入排序，待整个序列中的记录
基本有序时，再对全体记录进行直接插入排序
void shell_insert1(int *arr,int len,int ader)
{
int i,k;
//循环对ader个子序列进行插入操作
for(k=0;k<ader;k++)
for(i=ader+k;i<len;i+=ader)//对一个子序列进行插入排序操作
{
//将第i个元素分别与前面的每隔ader个位置的元素进行比较，插入适当的位置
if(arr[i]<arr[i-ader])
{//一直向左进行比较，直到插入到适当的位置
int key=arr[i];
int count=0;//用来记录key在与前面元素比较时向左移动了几个ader长度； while(i>k&&key<arr[i-ader])
{
arr[i]=arr[i-ader];
arr[i-ader]=key;
i-=ader;
count++;
}
//将待插入的数定位到下一个元素，执行下一次插入排序
//因为后面还要执行i+=ader，所以这里回到原位置即可
i+=count*ader;
}
}
}

void shell_insert2(int *arr,int len,int ader)
{
int i,j,k;
//循环对ader个子序列各自进行插入排序
for(k=0;k<ader;k++)
for(i=ader+k;i<len;i+=ader)
for(j=i-ader;j>=k&&arr[j]>arr[j+ader];j-=ader)
{
//交换元素数值
arr[j]^=arr[j+ader];
arr[j+ader]^=arr[j];
arr[j]^=arr[j+ader];
}
}
void shell_insert2_1(int *arr,int len,int ader)
{
int i,j;
//交叉对ader个子序列进行插入排序
for(i=ader;i<len;i++)
for(j=i-ader;j>=0&&arr[j]>arr[j+ader];j-=ader)
{
//交换元素数值
//由于不会出现自己与自己交换的情况
//因此可以安全地用该交换方法
arr[j]^=arr[j+ader];
arr[j+ader]^=arr[j];
arr[j]^=arr[j+ader];
}
}

void shell_insert3(int *arr,int len,int ader)
{
int i,j,k;
//循环对ader个子序列各自进行插入排序
for(k=0;k<ader;k++)
for(i=ader+k;i<len;i+=ader)
if(arr[i]<arr[i-ader])
{
int key=arr[i];
for(j=i-ader;j>=k&&arr[j]>key;j-=ader)
arr[j+ader]=arr[j];
ader[j+ader]=key;
}
}

void shell_insert3_1(int *arr,int len,int ader)
{
int i,j;
//对ader子序列交叉进行插入排序
for(i=ader;i<len;i++)
if(arr[i]<arr[i-ader])
{
int key=arr[i];
for(j=i-ader;j>=0&&arr[j]>key;j-=ader)
arr[ader+j]=arr[j];
arr[j+ader]=key;
}
}