插入排序算法主要是将待排序数组依次插入有序数组中，时间复杂度是O(logn^2)，空间复杂度为O(1)；

下面是代码实现步骤：

1.先假定数组左边第一个元素是有序的

void Sorts::insert(vector<int>& nums)
{
    if (nums.size() <= 1)
        return;
    ......
}

2.依次遍历待排数组的右边第二个元素到最后一个元素

void Sorts::insert(vector<int>& nums)
{
    if (nums.size() <= 1)
        return;
    
    for (int i = 1; i < nums.size(); i++) // 先对待排序数组进行遍历
    {
        ......
    }
}

3.待排数组每个元素跟左边有序数组进行插入比较，找到合适的位置；我的实现代码是从左到右遍历有序数组，当找到第一个大于待排序数组的元素时，则插入该位置，否则不插入，即原位置是正确的；

void Sorts::insert(vector<int>& nums)
{
    if (nums.size() <= 1)
        return;
    
    for (int i = 1; i < nums.size(); i++) // 先对待排序数组进行遍历
    {
        int tmp = nums[i];
        for (int j = 0; j < i; ++j) // 从左到右遍历有序数组，找到第一个大于tmp的数，插入该位置
        {
            if (tmp < nums[j]) // 在有序数组中，找到第一个大于tmp数，将该位置数据依次右移一位（待排序数组不需要移位）；假如没找到说明该位置正确，不需要移位和交换
            {
                for (int k = i; k > j; --k) // j本身以及后面数字依次往右移动一位到i位置截止
                {
                    nums[k] = nums[k - 1];
                }
                nums[j] = tmp;
                break; // 注意插入位置后需要中断当次循环，继续排列下一个待排元素      
            }
        }
    }
}

注意下面代码是数组nums的[ j，i ]区间，从第j元素开始到第i - 1元素位置，依次向右移动一位，到第i元素位置截止；并且将tmp值赋给nums[j]。

for (int k = i; k > j; --k) // j本身以及后面数字依次往右移动一位到i位置截止
{
    nums[k] = nums[k - 1];
}
nums[j] = tmp;

4.当一个待排数组插入到合适位置后，需要中断遍历有序数组循环，否则会出现莫名其妙数据

下面是遍历有序数组循环代码：

for (int j = 0; j < i; ++j) // 从左到右遍历有序数组，找到第一个大于tmp的数，插入该位置
{
    if (tmp < nums[j]) // 在有序数组中，找到第一个大于tmp数，将该位置数据依次右移一位（待排序数组不需要移位）；假如没找到说明该位置正确，不需要移位和交换
    {
        for (int k = i; k > j; --k) // j本身以及后面数字依次往右移动一位到i位置截止
        {
            nums[k] = nums[k - 1];
        }
        nums[j] = tmp;
        break; // 注意插入位置后需要中断当次循环，继续排列下一个待排元素      
    }
}

5.完整的程序代码如下所示

Sorts.h

#pragma once

#include <iostream>
#include <vector>

using namespace std;

struct Sorts {    
    void insert(vector<int>& nums);    
    void print(vector<int>& nums);
};

Sorts.cpp

#include "Sorts.h"

void Sorts::insert(vector<int>& nums)
{
    if (nums.size() <= 1)
        return;
    
    for (int i = 1; i < nums.size(); i++) // 先对待排序数组进行遍历
    {
        int tmp = nums[i];
        for (int j = 0; j < i; ++j) // 从左到右遍历有序数组，找到第一个大于tmp的数，插入该位置
        {
            if (tmp < nums[j]) // 在有序数组中，找到第一个大于tmp数，将该位置数据依次右移一位（待排序数组不需要移位）；假如没找到说明该位置正确，不需要移位和交换
            {
                for (int k = i; k > j; --k) // j本身以及后面数字依次往右移动一位到i位置截止
                {
                    nums[k] = nums[k - 1];
                }
                nums[j] = tmp;
                break; // 注意插入位置后需要中断当次循环，继续排列下一个待排元素      
            }
        }
    }
}

void Sorts::print(vector<int>& nums)
{
    for (const auto& it : nums)
        cout << it << ",";
    cout << endl;
}

main.cpp

 #include <vector>
#include "Sorts.h"

using namespace std;

int main()
{
    vector<int> nums = { 2,0,1,6,8,10,5,99,87,333,2,0,1 };
    Sorts sorts;
    sorts.print(nums);
    sorts.insert(nums);
    sorts.print(nums);
   
	return 1;
}

输出结果：