插入排序基本思想是通过构建有序序列，对于未排序的数据，在已排序的数据中从后往前进行扫描，找到相应的位置插入。
时间复杂度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--;
}
}
}
}
