插入排序
插入排序是以一种对少量元素进行排序的有效算法，插入排序工作原理跟多人打牌时，整理手中的牌差不多。对于未排序的数据，在已排序序列从后往前扫描，找到相应位置并插入。
即把将要插入的元素与前面已经有序的序列一一比较，找到合适的位置。
伪代码表示
for j<- 1 to length[A]
do key <- A[j]
i<- j-1
while(i>0&&A[i]>key)
do A[i+1] = A[i]
i<- i-1
A[i+1] = key
java实现
class Insertion_Sort{
public static void main(String []args){
int[] A = new int[]{2,4,3,6,1,1,7,4};//未排序序列
int len = A.length;
for(int j = 0; j < A.length; j++){
int key = A[j]; //待插入的元素
int i = j - 1; //0 - j-1为已排序序列，将A[j] 插入到A[0]-A[i]中
while(i>0&&A[i]>key){ //一一比较
A[i+1] = A[i];
i--;
}
A[i+1] = key; //插入
}
}
}
算法复杂度
插入排序最好情况是待排序列已经有序，这时候只需要比较n-1次即可，不需要交换操作，时间复杂度为O(n)
最坏情况下为待排元素全部逆序，此时需要比较n(n-1)/2次，即0+1+.....+n-1次，时间复杂度为O(n²),平均来说插入排序的时间复杂度为O(n²)
算法分析
从时间复杂度来看，插入排序不适合数据量较大的排序应用。但在排序量规模较小的情况下，插入排序的效果比较理想，优于归并排序，冒泡排序的。
因为插入排序的常量因子c1小于归并排序的常量因子c2, c1n²在小规模时小于c2log2 n。因此在小规模排序时我们可以选择插入排序，到一定规模改用快排，归并等排序。
插入排序还可以配合二分查找来减少比较次数得到优化。
原文：https://www.cnblogs.com/binhuang01/p/11367718.html