插入排序思想：将插入的元素记录，与前面的元素进行比较大小，查询到插入的位置，然后再将比它大的元素向后面移动，空出插入的位置，将元素插入。

剩下的和②步骤一样。。。

代码这里给出了3种，从基础到优化

//1
void InsertSort(int* a, int n)
{
    for (int i = 1; i < n; ++i)
    {
        if (a[i] < a[i - 1])
        {
            int temp = a[i];
            for (int j = 0; j < i; ++j)
            {
                if (temp < a[j])
                {
                    for (int k = i; k > j; k--)
                        a[k] = a[k - 1];
                    a[j] = temp;
                    break;
                }
            }
        }
    }
}

//2
void InsertSort(int* a, int n)
{
    int i, j;
    for ( i = 1; i < n; i++)
    {
        if (a[i] < a[i - 1])
        {
            int temp = a[i];
            for (j = i; j >= 0 && a[j-1] > temp; j--)
            {
                a[j] = a[j - 1];
            }
            a[j] = temp;
        }
    }
}

//3
void InsertSort(int* a, int n)
{
    int temp;
    for (int i = 1; i < n; i++)
    {
         int low = 0, high = i - 1;
         temp = a[i];
         while (low <= high)
         {
             int mid = (low + high) / 2;
             if (temp < a[mid])
                 high = mid - 1;
             else
                 low = mid + 1;
         }
         for (int j = i; j > low; --j)
         {
             a[j] = a[j - 1];
         }
         a[low] = temp;
    }
}

主方法：

int main()
{
    int arr[] = { 9,2,3,1,5,4,7,8,6 };
    int n = sizeof(arr) / sizeof(int);

    InsertSort(arr, n); //插入排序

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}