算法思想：

image.png
简而言之：插入排序就是将一个待排序元素插入到前面已经排好序的序列之中。

代码实现

实现一：

image.png

实现二（带哨兵）：

image.png
将带排序的元素放在索引为0地方，如果遍历至0处则退出第二个for循环，就不用判断索引小于0的情况。

算法效率分析：

image.png
image.png

插入排序的优化问题：

图解：

由于待排序元素前面一定是有序的，且使用的存储结构是顺序存储时，则可以使用折半查找来查找数据的插入位置。
image.png
image.png
image.png
image.png
如上，要将low指向的数据至i-1的数据依次向后移动一位，将i插入到low处
image.png
image.png
待排序的元素（60）和mid指向的元素相同，此时不停止查找，而是在其右半区间继续搜索
image.png
image.png
要将low指向的数据至i-1的数据依次向后移动一位，将i插入到low处
image.png
……(省略很多步骤)
image.png
low>i-1不移动
image.png
……(省略很多步骤)
image.png
要将low指向的数据至i-1的数据依次向后移动一位，将i插入到low处

代码实现：

image.png

对链表使用插入排序：

:::info 链表不适用折半查找 ::: image.png

总结：

image.png