插入排序算法主要分为：直接插入算法，折半排序算法（二分插入算法），希尔排序算法，后两种是直接插入算法的改良。因此直接插入算法是基础，这里先进行直接插入算法的分析与编码。
直接插入算法的排序思想：假设有序数组从小到大为array[0],array[1],array[2],….,array[n-2],array[n-1]，那么将待排数值array[n]与前面的有序数组从后向前依次比较，直到在有序数组中找到小于待排数值array[n]的位置，将array[n]插入到此位置，并入组合成新的有序数组。
直接插入算法–代码如下所示：
//直接插入排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）
privatestaticvoid InsertSortionFunction(int[] array)
{
try
{
int temp =; //临时变量，存储待排的数值
for (int i =; i < array.Length; i++) //将无序的所有数值依次插入到有序数组中，注：下标从1开始，因为操作的是同一个数组
{
temp = array[i]; //记录待插入前面有序数组的数值
int index = i -; //记录前方有序数组的末尾位置
while (index >=&& array[index] > temp) //循环遍历前面的有序数组，并且从大到小依次与待排数值进行比较
{
array[index +] = array[index]; //如果index>=0并且此时的值大于待排数值，将此处的值向后移动一位
index--; //index--向前遍历有序数组
}
array[index +] = temp; //由于前面的index--，所以temp插入的位置是index+1
}
}
catch (Exception ex)
{ }
}
折半排序算法是对直接插入算法的一种优化，优化的核心是：通过折半查看有序数组中间位置的数值（a）与待插入的数值（temp）的大小，如果a>=temp，则转向折半的左区间继续折半查找； 如果a<temp，则转向折半后的右区间继续折半查找。直到左右下标相同时，此时折半的下标也指向相同的位置，再做最后一次循环，最终的结果是：左右下标相差1，并且原来左侧的下标指向大于temp的位置，原来右侧的下标指向了小于temp的位置，即：array[biggerIndex] < temp < array[smallerIndex]。
折半排序算法–代码如下：
//折半排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）
privatestaticvoid BinaryInsertionSortFunction(int[] array)
{
try
{
int smallerIndex =; //记录有序数组的起始位置
int biggerIndex =; //记录有序数组的终止位置
int midIndex =; //记录获取有序数组的中间位置（折半法的关键：折半的位置）
int temp; //记录带排的数值
for (int i =; i < array.Length; i++) //循环向有序数组中插入数值（i从1开始，因为操作的是同一个数组）
{
temp = array[i]; //记录待插入有序数组的数值
biggerIndex = i -;
//当smallerIndex==biggerIndex时，进入最后一次循环：smallerIndex指向大于temp的数组位置，biggerIndex指向小于temp的数组位置
while (smallerIndex <= biggerIndex)
{
midIndex = (smallerIndex + biggerIndex) /; //确定折半的位置
if(array[midIndex] >= temp) //折半位置的数值 >= temp
{
biggerIndex = midIndex -; //biggerIndex以midIndex为基础向前移动一位
}
else
{
smallerIndex = midIndex +; //smallerIndex以midIndex为基础向后移动一位
}
}
for (int j = i -; j >biggerIndex; j--) //将有序数组中大于temp的数值分别向后移动一位
{
array[j +] = array[j]; //
}
array[biggerIndex +] = temp; //将temp插入biggerIndex + 1，因为此时array[biggerIndex]<temp<array[smallerIndex]
}
}
catch (Exception ex)
{ }
}
希尔排序同样是直接插入排序算法的一种改进，基本思想是：将无序的数列划分为若干小的子序列，然后对子序列进行直接插入排序。
时间性能优于直接插入排序算法，但是一种不稳定的排序，时间复杂度为O(nlogn)。
希尔排序算法主要分为3重循环：
第一重循环–>按照gap的大小进行分组，初始化从array.Length/2开始，依次递减到1
第二重循环–>对所有分组进行排序
第三重循环–>组内进行直接插入排序
希尔排序算法–代码如下：
privatestaticvoid ShellSortFunction(int[] array)
{
try
{
int length = array.Length;
int temp =;
for (int gap = length /; gap >; gap--) //第一重循环，按照gap的大小进行分组
{
for (int i =; i < gap; i++) //第二重循环，对所有分组进行排序
{
for (int j = i; j < length; j = j + gap) //第三重循环，组内进行直接插入排序
{
temp = array[j];
int index = j - gap;
while (index >=&& array[index] > temp)
{
array[index + gap] = array[index];
index = index - gap;
}
array[index + gap] = temp;
}
}
}
}
catch (Exception ex)
{ }
}
