数据结构之插入排序

插入排序

一种思想我们所在指向位是需要进行插入的数据
我们锁指向位置前的数据是被插入的数据组
我们根据与前面的数据元素一个个比较来确定插入位置的排序
比如现在的76比前面的97小，97进行一个右移，就是赋值给data[4]（我这里猜测是76应该是赋给一个变量了），然后在与65比较比65大
所以76插入到65和97中间
关于最后的49，只把比关键值大的值右移一位
所以最开始在7位置上的49最后应该在4位置

算法实现

一般是这种

带哨兵模式

就是把temp变为data[0]实际元素从data[1]开始存储

效率分析

空间复杂度 O(1)

时间复杂度
主要是来自对比关键字和移动元素导致的时间复杂度

最好的情况
最坏的情况（一般就写这个）

优化-折半插入排序

就是之前的对比
用的顺序查找，但是其实我们指向元素前的元素
已经是一个有序的数列了，所以可以使用折半查找进行对比

把[low，i-1]元素右移
然后[low]=[0] （哨兵模式下）

相等的情况-不会停止查找

在右半区间查找使low=mid+1

和之前处理一样low右边右移
[mid]=[0]

小结

代码实现

总结