插入排序是一种简单且有效的比较排序算法。在每次迭代过程中算法从输入序列中移除一个元素，并将该元素插入待排序序列的正确位置。重复该过程，直到所有输入元素都被选择一次。
算法优点：
a.实现简单
b.数据量较少时效率高
c.适应性：如果输入序列已经预排序，则时间复杂度几乎是线性的。
d.稳定性：键值相同时它能够保持输入数据的原有次序。
e.原地：不需要额外的空间。
算法思路：从第二个元素作为当前元素，依次往下标较小的位置遍历，当前一个元素比该元素小，则将该元素放入当前位置，否则前一个元素后移，同理依次遍历；然后以第三个元素作为当前元素，重复上述操作；依次往后直到到达最后一个元素完成排序。
代码：
package insertionsort;
public class InsertionSort {
private static int count;
public static int[] insertionSort(int[] A,int n)
{
int i,j,v;
for(i=1;i<n;i++)
{
v=A[i];
j=i;
while(j>=1&&A[j-1]>v)//此处应该将j>=1的条件限制放在前面，然后用短路与&&,这样使用才不会导致A[j-1]报错;
{
A[j]=A[j-1];//满足条件则需继续遍历，则将j-1位置的元素往后移；
j--;
count++;
}
A[j]=v;//当A[j-1]<v的时候，则将A[j]的位置放v。
print(A);
}
return A;
}
private static void print(int[] A)
{
int n=A.length;
for(int i=0;i<n;i++)
System.out.print(A[i]+" ");
System.out.println();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A= {8,9,1,4,5,3,7,2};
int n=8;
System.out.println("插入排序步骤中插入元素位置变化：");
int[] ans=InsertionSort.insertionSort(A, n);
System.out.println("完成排序后的序列：");
for(int i=0;i<n-1;i++)
System.out.print(ans[i]+" ");
System.out.print(ans[n-1]);
System.out.println();
}
}
测试结果：
插入排序步骤中插入元素位置变化： 8 9 1 4 5 3 7 2 1 8 9 4 5 3 7 2 1 4 8 9 5 3 7 2 1 4 5 8 9 3 7 2 1 3 4 5 8 9 7 2 1 3 4 5 7 8 9 2 1 2 3 4 5 7 8 9 完成排序后的序列： 1 2 3 4 5 7 8 9
插入排序最坏情况下的时间复杂度为O(n^2)，在数据几乎都已经排序或者输入数据规模较小时可以使用插入排序。