哪个成功的人不是一路坎坷过来的，只有这样你才知道珍惜，知道成功的不易。有时候太容易得到的东西反而不知道珍惜。
直接插入排序：
我们的记录本身就是基本有序的，我们只需要少量的插入操作，就可以完成整个记录集的排序工作，此时直接插入很高效。还有就是记录数比较少时，直接插入的优势也比较明显。
void InsertSort(int b[],int n) //直接插入排序
{
int i,j,t;
for(i=0; i<n; i++)
{
t=b[i+1];
j=i;
while(j>=0&&t<b[j])
{
b[j+1]=b[j];
j--;
}
b[j+1]=t;
}
}
折半插入排序
算法的流程就是：比如此时顺序为5,3,2,4,1。分别对应数组的a[0]...a[4]。
那么当我们进入第一次插入算法时，low=0；high=0；所以mid=0；此处用a[mid]即a[0]与我们所要插入的数a[1]即3进行比较。有a[mid]>3所以此时。我们就要在mid的左边即low到mid之间进行比较了，但是mid又如何更新呢，就是要把high减1；然后再求mid就可以了，这时的新的mid就在low与原来的mid之间了。然后我们再次进行比较，但是此时因为high已经小于1了，所以循环终止，故将原有的数据后移一位，再将要插入的元素插入low处即可。
void BinInsertSort(int b[],int n)
{
int i,j,t,mid,low,high;
for(i=0; i<n; i++)
{
t=b[i+1];
low=0;
high=i;
while(low<=high)
{
mid=(low+high)/2;
if(b[mid]>t)
high=mid-1; //在小于中间值的那部分寻找
else
low=mid+1; //在大于中间值的那部分寻找
}
for(j=i; j>=low; j--)
{
b[j+1]=b[j]; //整体数组后移
}
b[low]=t;
}
}
希尔排序：
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1、插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。/
2、但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
希尔排序不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。比O( n²)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。希尔排序算法的发明，使得我们终于突破了慢速排序的时代（超越了时间复杂度为O(n2)），之后，相应的更为高效的排序算法也就相继出现了。
希尔排序的思想就是，每隔一定增量的两个数进行比较排序，然后得到一个得到一个基本有序的序列。这其实就是希尔排序的精华所在，它将关键字较小的记录，不是一步一步地往前挪动，而是跳跃式地往前移，从而使得每次完成一轮循环后，整个序列就朝着有序坚实地迈进一步。
void ShellSort(int b[],int n)
{
int i,j,t;
int increment=n;
do
{
increment=increment/3+1; // 增量序列
for(i=increment; i<=n; i++)
{
if (b[i]<b[i-increment]) //需将b[i]插入有序增量子表
{
t=b[i]; // 暂存在t
for(j=i-increment; j>=0 && t<b[j]; j-=increment)
b[j+increment]=b[j]; // 记录后移，查找插入位置
b[j+increment]=t; //插入
}
}
}
while(increment>1);
}
测试程序如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void InsertSort(int a[],int n) //直接插入排序
{
int i,j,t;
int b[n];
memcpy(b, a, n * sizeof(int));
for(i=0; i<n; i++)
{
t=b[i+1];
j=i;
while(j>=0&&t<b[j])
{
b[j+1]=b[j];
j--;
}
b[j+1]=t;
}
for(i=0; i<n; i++)
printf("%4d",b[i]);
}
void BinInsertSort(int a[],int n)
{
int i,j,t,mid,low,high;
int b[n];
memcpy(b,a,n*sizeof(int));
for(i=0; i<n; i++)
{
t=b[i+1];
low=0;
high=i;
while(low<=high)
{
mid=(low+high)/2;
if(b[mid]>t)
high=mid-1; //在小于中间值的那部分寻找
else
low=mid+1; //在大于中间值的那部分寻找
}
for(j=i; j>=low; j--)
{
b[j+1]=b[j]; //整体数组后移
}
b[low]=t;
}
for(i=0; i<n; i++)
printf("%4d",b[i]);
}
void ShellSort(int a[],int n)
{
int i,j,t;
int b[n];
memcpy(b,a,n*sizeof(int));
int increment=n;
do
{
increment=increment/3+1; // 增量序列
for(i=increment; i<=n; i++)
{
if (b[i]<b[i-increment]) //需将b[i]插入有序增量子表
{
t=b[i]; // 暂存在t
for(j=i-increment; j>=0 && t<b[j]; j-=increment)
b[j+increment]=b[j]; // 记录后移，查找插入位置
b[j+increment]=t; //插入
}
}
}
while(increment>1);
for(i=0; i<n; i++)
printf("%4d",b[i]);
}
int main()
{
int i;
int p[5]= {5,3,2,4,1};
printf("原序：");
for(i=0; i<5; i++)
printf("%4d",p[i]);
printf("\n直接插入排序：");
InsertSort(p,5);
printf("\n折半插入排序：");
BinInsertSort(p,5);
printf("\n希尔排序：");
ShellSort(p,5);
return 0;
}
结果：
