直接插入排序

直接插入排序，它是一种依次将无序区的元素在有序区内找到合适位置依次插入的算法。

基本思想：

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序，直到无序表内所有元素插入为止。 
首先在当前有序区R[0..i-1]中查找R[i]的正确插入位置 k(0≤k≤i-1)； 
然后将R[k．．i-1]中的记录均后移一个位置，腾出 k 位置上的空间插入R[i]。

void insertSort(vector<int> array)
{
    int n = array.size();
    for(int i = 1; i < n; i++)
    {
        int j = i - 1;
        int tmp = array[i];
        while(j >= 0 && tmp < array[j])//比插入元素大的元素进行后移操作
        {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = tmp;//插入要插入的元素
    }
    
}