排序算法3——直接插入排序以及折半（二分）插入排序
一、直接插入的基本思想
将待排序的一组序列分为已排好序和未排好序的两个部分
初始状态时，已排好序序列仅包含第一个元素，未排好序的序列元素为除去第一个以外的n-1个元素
然后，将未排好序序列中的元素逐一插入到已排好序的序列中
如此往复，经过n-1次插入后，未排序序列中的元素个数变为0，排序完成。如下图所示
代码及上下界如图
从代码可以看出，空间复杂度上，简单插入排序仅需要常数个额外空间
在时间复杂度上，函数中有两个嵌套的循环，每个循环进行O（N）次比较和交换，故时间复杂度为O（N^2）
此外，简单插入排序是稳定的排序，
可以在下面的具体过程中看到，数值相同的两个记录不会发生相对位置上的改变
具体过程
后面就不列出了