插入排序可理解为推箱子问题,前面有4个箱子，且都从小到大排好序，现在第5个箱子来了

需要将第5个箱子推到指定位置。

思路：先把第五个箱子放到旁边，现在有5个位置，比较第4个和第5个，若第4个大，则将其

推到位置5，再比较第3个与第5个，若第3个大，则将其推到位置4，假设第2个箱子比第5个小

则将第5个箱子推到位置2，结束。

代码也很简单：

 

1 void insertSort(vector
     
       &a){ 2     int j,temp; 3     for(int i=1;i
      
       =1&&temp
      
     

 

时间复杂度：

　　最差：O(n²)

　　平均：O(n²)

空间复杂度：

　　O(1)