插入排序基本思想是通過構建有序序列，對于未排序的數(shù)據(jù)，在已排序的數(shù)據(jù)中從后往前進行掃描，找到相應的位置插入。

時間復雜度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--;
               }
          }
    }
}