插入排序的思想是：
1。假设第一个元素是有序的，理解这个有序是针对只有这一个元素。
2。然后依次拿出后面元素插入到前面元素构成的有序序列里面（这个过程保证了算法的稳定性，因为遇到等于小于自己的时候就停止插入操作）。
3。直到最后一个元素插入到插入到前面的有序序列，完毕。
时间复杂度分析：
假设数组有n个元素
最好情况：n个元素是逆序的，则每个元素需要2次比较，3次数据移动
所以总次数为5（n-1）次（第一个元素不用比较了）
时间复杂度为O（n）
最坏的情况，n个元素是已经拍好顺序的，则第i个元素需要比较的次数是i次，0次数据移动，i=0,1,2...(n-1)
所以比较次数总数Cmax=n(n-1)/2
时间复杂度为O（n2）
下面给出C#的通用插入排序算法实现：
startIndex为排序区间的数组元素下标，通常为0，
endIndex为排序区间的数组元素下标，通常为array.Length-1
public class InsertionSort<T> where T : IComparable<T> { public void Sort(T[] array, int startIndex, int endIndex) { //假定startIndex的值已经在正确位置 for (int i = startIndex; i <= endIndex; i++) { T tmp = array[i];//待插入数据 int targetIndex = i;//当前位置为寻找起点 while (targetIndex > startIndex && array[targetIndex - 1].CompareTo(tmp) > 0) { array[targetIndex] = array[targetIndex - 1];//已排好顺序的序列依次向右移位 targetIndex--;//此待选位置空出 } array[targetIndex] = tmp; } } }
作者：Andy Zeng
欢迎任何形式的转载，但请务必注明出处。
http://www.cnblogs.com/andyzeng/p/3684066.html
原文：http://www.cnblogs.com/andyzeng/p/3684066.html