我所理解的插入排序算法

插入排序是一种简单的排序方法，因为的实现比较简单，所以在数据量较少时应用很广泛。插入排序根据其插入的不同方式，可以分为直接插入排序，折半插入排序，2-路插入排序，表插入排序和希尔排序。在这里我将一一写出各种插入排序的算法代码。
直接插入排序
template?<class?T>
void?InsertSort(T?a[],?int?len)
{
??????int?i,?j;
??????T?temp;
??????for?(i=1;?i<len;?i++)
??????{
????????????temp?=?a[i];
????????????for?(j=i-1;?j>=0?&&?a[j]>temp;?j--)//元素后移
??????????????????a[j+1]?=?a[j];
????????????a[j+1]?=?temp;??//插入
??????}
}
??????有些算法把a[0]设置为临时数据存放处（即原数组中a[0]未存储元素），这样就可以少进行一些判断，在数据量较大时可以节省一些时间，算法如下：
template?<class?T>
void?InsertSort(T?a[],?int?len)
{
??????int?i,?j;
??????for?(i=1;?i<len;?i++)
??????{
????????????a[0]?=?a[i];
????????????for?(j=i-1;?a[j]>temp;?j--)
??????????????????a[j+1]?=?a[j];
????????????a[j+1]?=?temp;
??????}
}
折半插入排序法
??????由于插入排序的基本操作是在一个有序表中进行查找和插入，则这个查找操作可以利用折半查找来实现。但是折半插入排序仅减少了元素间的比较次数，而元素的移动次数不变，因此折半插入排序法的时间复杂度仍为O(n^2)。算法如下：
template?<class?T>
void?HalfInsertSort(T?a[],?int?len)
{
??????int?i,?j;
??????int?low,?high,?mid;
??????T?temp;
??????for?(i=1;?i<len;?i++)
??????{
????????????temp?=?a[i];
????????????low?=?0;
????????????high?=?i?-?1;
????????????while?(low?<=?high)?//在a[low。。。high]中折半查找有序插入的位置
????????????{
??????????????????mid?=?(low?+?high)?/?2;
??????????????????if?(a[mid]?>?temp)
????????????????????????high?=?mid?-?1;
??????????????????else
????????????????????????low?=?mid?+?1;
????????????}?//while
????????????
????????????for?(j=i-1;?j>high;?j--)//元素后移
??????????????????a[j+1]?=?a[j];
????????????a[high+1]?=?temp;?//插入
??????}//for
}

希尔排序法
??????希尔排序法又称缩小增量排序法，它也是插入排序类的方法，但在时间效率上较前面几种插入排序算法有较大的改进。
??????希尔排序法通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到比较相邻元素的最后一趟排序为止。算法如下：
template?<class?T>
void?ShellSort(T?a[],?int?len)
{
??????for?(int?increment=len/2;?increment>0;?increment/=2)
??????{
????????????for?(int?i=increment;?i<len;?i++)
????????????{
??????????????????T?temp?=?a[i];
??????????????????int?j?=?i;
??????????????????for?(;?j>=increment;?j-=increment)//元素后移
??????????????????{
????????????????????????if?(temp?<?a[j-increment])
??????????????????????????????a[j]?=?a[j-increment];
????????????????????????else
??????????????????????????????break;
??????????????????}
??????????????????a[j]?=?temp;?//插入
????????????}//for
??????}//for
}
注：缺2-路插入排序和表插入排序，有意者请补上！谢谢！

深入 printf / wprintf / console下的unicode output：【上一篇】
VC++.net使用OCCI连接远程Oracle数据库：【下一篇】