数组插入排序

插入排序是一个相对复杂一点的排序算法，但是效率要比我们以前接触过的排序算法快一些，他的思想是将数组分为两组数据（第一次分的时候就是数组第一个元素为一组，后面的所有元素为一组），然后从后面一组数据中抽取第一个元素与前面一组数据依次做对比，按需求将大的或者小的值插入到前面的一组数据中，最终后面一组数据全部插入完毕后，前面一组数据就是有序状态了。

如果这样说比较枯燥，我们可以做一个小案例。有下面这样一组数据。

10 2 7 6 1 4 3

我们先将其分两组，一组是

10          2 7 6 1 4 3

然后抽取出 2 这个数据，记录到临时变量中，此时 2 这个数据的位置就空下来了，让临时数据与前面的数据依次对比（目前只有一个数据，如果超过1个数据就要依次对比）比 2 大的就向后移动一个位置，如果比 2 小，那么 2 就插入到移动后空闲出来的位置。上面这个分组经过第一次插入排序后，结果是这样的。

2 10       7 6 1 4 3

继续上面的操作

2 7 10      6 1 4 3

2 6 7 10      1 4 3

1 2 6 7 10      4 3

1 2 4 6 7 10     3

1 2 3 4 6 7 10

这种排序的图形表示法如下（摘自 传智播客 教师课件，图片下载下来放大看）：

【代码实现】

void insert_sort(int* arr, int len)
{
// 用来记录空位的下标
int tmp = 0;
// 用来记录抽取出去的值
int value = 0;
for (int i = 1; i < len; i++)
{
// 让 tmp 记录当前 i 的下标
tmp = i;
// 把下标为 i 位置的值存放到 value 中，此时下标为 i 的位置已经是空位
value = arr[i];
// 让 j 从 i - 1 的位置到 >=0 的位置递减遍历
// 并且 arr[j] 的值要大于 value 的值才进入循环
for (int j = i - 1; j >= 0 && arr[j] > value; j–)
{
// 如果以上条件符合，将当前下标为 j 的值移动到空位上
arr[tmp] = arr[j];
// 这样 j 的位置就空下来了，让 tmp 重新记录空位的位置
tmp = j;
}
// 最后将最初记录 i 的值存放到多次移动的空位上
arr[tmp] = value;
}
}