【背景】
插入排序（Insertion Sort）是一种简单有效的比较排序算法，属于原地排序。
【源码运行环境】
操作系统：Windows 10
编译环境：Dev C++(基于C99标准)
【基本思想】
在每次迭代过程中从输入序列中取出一个元素插入到一个有序序列中，形成新的有序序列。重复该过程，直到序列中所有元素都被取出。
【动态图解】
【源码实现】
简单插入排序算法实现如下：
/*
*方法名：InsertToRightPosition
*作用：将插入数插入合适位置
*参数：待查找数组 array; 待排序数字符下标 i
*返回值：void
*Author: WellLee
*最后一次修改时间：2018年12月8日 00:53:37
*/
void InsertToRightPosition(int array[],int i)
{
int inserted = array[i];
int j;
for(j = i - 1; j >= 0 && array[j] > inserted; j--)
{
array[j+1] = array[j];
}
array[j+1] = inserted;
}
/*
*方法名：InsertToSort
*作用：插入排序主算法，遍历划分排序与未排序数组。
*参数：待查找数组 array; 数组长度length
*返回值：void
*Author: WellLee
*最后一次修改时间：2018年12月8日 00:54:27
*/
void InsertSort(int array[], int length)
{
int i;
for(i = 1 ; i < length; i++)
{
InsertToRightPosition(array, i);
}
}
折半插入排序算法如下：
/*
*方法名：Binary_InsertSort
*作用：折半插入排序主算法，遍历划分排序与未排序数组。
*参数：待查找数组 array; 数组长度length
*返回值：void
*Author: WellLee
*最后一次修改时间：2018年12月8日 01:03:55
*/
void Binary_InsertSort(int array[], int length)
{
int i,j,inserted;
int low,high,mid;
for(i = 2; i <= length; i++)
{
array[0] = array[i];
low = 0;
high = i - 1;
while(low <= high)
{
mid = (low + high) / 2;
if(array[0] < array[mid])
{
high = mid - 1;
}else
{
low = mid + 1;
}
}
for(j = i - 1; j >= high + 1 && j >= 0; j--)
{
array[j+1] = array[j];
}
array[high+1] = array[0];
}
}
【分析】
1、插入排序在数据量较少时效率高。但总的时间复杂度为\(O(n^2)\)
2、适应性（adaptive）：如果输入的序列已经预排序，则时间复杂度为O（n+d）,d是反转次数（交换次数）。
3、由于它的适应性算法的实际运行效率优于选择排序和冒泡排序。
4、折半插入排序与直接插入排序区分点是，查找步骤利用折半查找完成，减少了在查找空间过程中时间支出成本。
5、而折半插入排序算法因折半算法的限制，导致它并不适用于链式顺序表（简单插入排序是适用于链式顺序表的）。
【总结】
本文给出一种不需要哨兵位的简单插入排序算法和一种需要哨兵位的折半插入排序算法，但实际上两种区别于哨兵位的算法大同小异。进一步理解了两种插入算法。（简单插入、折半插入）。
【参考文献】
-
《数据结构》.严蔚敏,李冬梅,吴伟民.人民邮电出版社
-
《大话数据结构》.程杰.清华大学出版社