简介

插入排序也是一种思想很简单的排序方法，它通过比较当前元素和其之前已排好序的元素的大小，找到合适的位置插入，并把插入位置后的元素往后移动。

复杂度

时间复杂度

1.最好的情况就是已经排好序的数组，这样一次都不用交换
2.最坏的情况就是完全逆序的数组，这样每个元素都要挪动，每次都要交换，次数为1+2+3+…+n-1=n(n-1)/2，时间复杂度为O（n²）（即n的平方）
3.平均时间复杂度为O（n²），是一种稳定的排序方法

空间复杂度

插入排序和冒泡排序一样是时间换空间的排序方法，没有使用多余的数据结构，不用分配额外的空间，所以空间复杂度为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.