简介
插入排序也是一种思想很简单的排序方法，它通过比较当前元素和其之前已排好序的元素的大小，找到合适的位置插入，并把插入位置后的元素往后移动。
复杂度
时间复杂度
1.最好的情况就是已经排好序的数组，这样一次都不用交换
2.最坏的情况就是完全逆序的数组，这样每个元素都要挪动，每次都要交换，次数为1+2+3+…+n-1=n(n-1)/2，时间复杂度为O（n2）（即n的平方）
3.平均时间复杂度为O（n2），是一种稳定的排序方法
空间复杂度
插入排序和冒泡排序一样是时间换空间的排序方法，没有使用多余的数据结构，不用分配额外的空间，所以空间复杂度为O（1）
java实现
public void insertionSort(int[]a)
{
for(int i=0;i<a.length-1;i++)
{
int currentItem=a[i+1];
for(int j=i;j>=0;j--)
{
if(currentItem<a[j])
{
a[j+1]=a[j];
a[j]=currrentItem;
}
else
{
a[j+1]=currentItem;
break;
}
}
}
}
That's all.
