在 选择排序 中我们举了一个学生排队的例子。

上体育课了，老师要排队：

A老师扫了一眼参差不齐的队伍，然后拨拉着同学们的脑袋，队伍就排好了。

B老师发现队伍很长，拨拉脑袋不好排，就先找出各自最低的同学，让站到一边，然后不断地找他认为个子最低的同学，让排在那个同学身后，这样就重新排了个队伍。

这个例子稍微改动下就是我们今天要看的插入排序了。

如果队伍有10个人，分别是 A、B、C、D、E、F、G、H、I、G 。我们要讲这10个同学按照从左到右，从小到大的顺序排列。

那么可以按照下面的步骤排序：

1. 让A站在最左侧，然后，B、C、D、E、F、G、H、I、G 依次排在右边。
2. 将B同学和A比较，如果A大于B，则将B放到A的位置，A就成了B的下一个人。如果A小于B，直接将B放在A后面即可（这个操作相当于把B放到了A右边，原来的顺序并没有改变）
3. 接下来将C分别依次和B，A比较（注意：前面已经排好序的人需要从右往左比较。），比较出结果后，仍然按照步骤2 中的红色字进行处理。
4. 依次类推。最后的队伍就全部排好序了。

参考图片：

代码如下，老韩的代码都尽量地给出详细注释，如果有疑问，记得留言交流：

#include <iostream>
using namespace std;

/**
* 定义一个插入排序的函数，传入数组的数组的长度
**/
void insectionSort(int arr[], int n)
{
    for (int i=1; i<n-1; i++) { // 从1开始循环，认为第一个元素是已经按序排列好的，i是待排序序列的下标，初始值是数组的第二个元素
        int tmp = arr[i]; // 拿到待排序序列的第一个值，后面会用这个值循环和已经排好序的序列中的各个值进行比较
        for(int j = i-1; j >= 0;j--) { // j是已经按序排列好的序列下标，循环与上一行的值进行比较
            if(arr[j] > tmp){ // 已经排序的某个值如果大于临时值，则需要用临时值取代这个值，将这个值往后移动一位。
                arr[j+1] = arr[j]; // 将这个值往后移动一位
                arr[j] = tmp; // 将这个位置腾出来给临时值
            }
        }
    }
}
int main()
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};  // 要排序的一维数组
    int n = sizeof(arr) / sizeof(arr[0]);  // 获取数组的长度，sizeof用来获取当前对象在内存中占用的大小
    cout << "排序前的数组为: ";
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    insectionSort(arr, n);   // 调用排序函数
    cout << "\n 排序后的数组为: ";
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    return 0;
}