插入排序基本思想是通过构建有序序列，对于未排序的数据，在已排序的数据中从后往前进行扫描，找到相应的位置插入。

时间复杂度O(n*n),空间复杂度O(1).

具体代码如下：

class Solution
{
    void InsertSort(vector<int> & array)  
    {
          int num = array.size();
          for(int i = 1; i < num; ++i)  //注意插入排序下标从1开始
          {
               int j = i;
               while (j > 0 && array[j] > array[j-1])
               {
                    swap(array[j], array[j-1]);
                    j--;
               }
          }
    }
}