【408数据结构与算法】—直接插入排序（十五）

【408数据结构与算法】—直接插入排序（十五）

一、插入排序基本思想

• 每步将一个待排序的对象，按其关键码大小，插入到前面已经拍好序的一组对象的适当位置上，直到对象全部插入为止。
• 在有序序列中插入一个元素，保持序列有序，有序长度不断增加
• 起初，a【0】是长度为1的子序列，然后，逐一将a[1]至a[n-1]插入到有序子序列中
  简化版：插入排序的原理就是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入与我们玩纸牌游戏一样
  
  

二、有序插入方法

1. 在插入a[i]前，数组a的前半段a[0]_{a[i-1]是有序段，后半段a[i]}a[n-1]是停留于输入次序的无序段。
2. 插入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)

要提高查找速度

• 减少元素的比较次数
• 减少元素的移动次数

📢📢总结