数据结构——直接插入排序

一、基本知识：

1.排序：默认递增。

2.定义：每一趟把待排序序列的第一个值，插入到前面的已经排序好的序列。

不申请额外的空间，在原序列的基础上进行排序所以就需要避免覆盖的问题。

二、基本原理：将数组分成已排序区间和未排序区间：

1.第一个元素单独作为已排序区间，剩余所有元素是未排序区间；

假设我们现在有一个待排序序列，默认第一个数据就是一个已经排序好的序列，因为我们此时将第一个数据看成一个单独的序列，因为只有一个数据，所以不存在是否有序无序，也就是说它是一个有序序列。

2.依次取出未排序区间的第一个元素，向前插入到已排序区间的合适位置。

以上面序列为例：

①第一趟：

思想：未排序区间第一个元素是18，根据比较得到18<59，又因为默认排序是递增的，所以18应该在59的左边。

操作：此时我们已经知道18应该在0号下标，59应该在1号下标，但是插入排序是在原序列的基础上进行排序，所以在数据移动时，就需要将18提前拷贝下来，避免覆盖，之后让59进行数据移动到1号下标，再让已经拷贝下来的18，移动到0号下标。

此时已排序好的序列就是18 59 从72开始就是未排序序列

②第二趟：

思想：此时72是未排序区间的第一个值，将72和已排序区间59 18进行比较，因为序列是递增的所以我们发现72比59大，所以72应该放在59的后面。

操作：我们将待排序序列的第一个值拷贝下来因为计算机开始不知道这个待排序数据应该在那个下标，所以我们还是要先将待排序的数据进行拷贝避免后续可能会出现的数据覆盖。将72和已经排序好的序列进行比较，59<72，所以72应该放置在59的后面。

所以此时 18 59 72 是已经排序好的序列，从85开始是未排序好的序列。

③第三趟：

思想：此时85是未排序序列的第一个元素，将85和已排序好的序列18 59 72进行排序，因为序列是递增的，所以我们发现85比72小应该放在72的后面。

操作：将待排序序列的第一个元素85拷贝下来和已经排序好的序列进行数据比较，72<85，85就放到72的后面

④后续雷同............

三、代码实现

void Insert_Sort(int arr[], int len) { for (int i = 1;i < len;i++)//控制的是趟数 { int temp = arr[i]; int j = i - 1; for (;j <=0;i--)//控制的是对已经排好的序列从右至左依次遍历 { if (temp>arr[j])//如果比我取出来的temp大，向后挪动 { arr[j + 1] = arr[j]; } else { break; //情况1：遇到了不大于我的值，停下来，把值放回去。 } } //情况2：越界了，停下来，把值放回去 arr[j + 1] = temp; } }