【408数据结构与算法】—直接插入排序（十五）
一、插入排序基本思想
- 每步将一个待排序的对象，按其关键码大小，插入到前面已经拍好序的一组对象的适当位置上，直到对象全部插入为止。
- 在有序序列中插入一个元素，保持序列有序，有序长度不断增加
- 起初，a【0】是长度为1的子序列，然后，逐一将a[1]至a[n-1]插入到有序子序列中
简化版：插入排序的原理就是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入与我们玩纸牌游戏一样
二、有序插入方法
- 在插入a[i]前，数组a的前半段a[0]a[i-1]是有序段，后半段a[i]a[n-1]是停留于输入次序的无序段。
- 插入a[i]使a[0]~a[i-1]有序，也就是要为a[i]找到有序位置j（0<=j<=i），将a[i]插入到a[j]的位置上
三、插入位置图示
❤️ 插在中间
❤️❤️插在最前面
❤️❤️❤️插在最后面
四、插入排序的种类
直接插入排序
直接插入排序—采用顺序查找的方法查找插入的位置
直接排序插入算法
五、直接插入排序—性能分析
实现排序的基本操作有两个
- 比较序列中两个关键字的大小
- 移动记录
最好的情况（关键字在记录中顺序有序）
最坏的情况（关键字在记录序列中逆序有序）
时间复杂度结论：
- 原始数据越接近有序，排序速度越快
- 最坏的情况(输入的数据是逆序有序） Tw(n)=O(n^2)
- 平均情况,耗时差不多是最坏情况的瘀斑 Te(n)=O(n^2)
要提高查找速度
- 减少元素的比较次数
- 减少元素的移动次数
📢📢总结
