简介插入排序是一种简单直观的排序算法。它的工作原理是：通过构造一个有序序列，对于未排序的数据，在已排序序列中从后往前扫描，找到对应的位置插入。算法实现步骤从第一个元素开始，可以认为是排序好的；取出下一个元素，在排序好的元素序列中从后往前扫描；如果元素（已排序）大于新元素，则元素移动到下一个位置；重复步骤3，直到找到排序元素小于等于新元素的位置；在此位置插入新元素；重复步骤2~5。Python代码实现#insertion_sort代码实现fromtypingimportListdefinsertion_sort(arr:List[int]):"""Insertionsort:paramarr:待排序List:return:插入排序是就地排序（in-place）"""length=len(arr)iflength<=1:returnforiinrange(1,length):value=arr[i]j=i-1whilej>=0andarr[j]>value:arr[j+1]=arr[j]j-=1arr[j+1]=value#测试数据if__name__=='__main__':importrandomrandom.seed(54)arr=[random.randint(0,100)for_inrange(10)]print("原始数据：",arr)insertion_sort(arr)print("插入排序结果：",arr)#输出原始数据：[17,56,71,38,61,62,48,28,57,42]插入排序结果：[17,28,38,42,48,56,57,61,62,71]动画演示算法分析时间复杂度如果数据最初是顺序的，只有外部循环n-1次，每次比较，不移动元素，即可完成。所需比较次数$C$和记录移动次数$M$均达到最小值：$$C_{\min}=n-1;M_{\min}=0$$所以，最佳时间为插入排序的复杂度是$O\left(n\right)$。如果数据最初是倒序的，则需要进行$n-1$次排序，每次排序要插入的元素都要与$\left[0,i-1\right]$中的$i$个元素进行比较比较$i$个元素向后移动$i$次，每次移动的次数为$i+2$。此时比较和移动的次数达到最大值：$$C_{\max}=1+2+3+\cdots+n-1=\frac{n\left(n-1\right)}{2}=O\left(n^2\right)$$$$M_{\max}=2+3+4+\cdots+n=\frac{\left(n-1\right)\left(n+2\right)}{2}=O\left(n^2\right)$$所以，平均时间复杂度为$O\left(n^2\right)$。空间复杂度空间复杂度是临时变量在交换元素时占用的内存空间，与数据大小无关，空间复杂度为$O\left(1\right)$，在稳定性排序过程中，相对同一元素的位置保持不变，所以插入排序是一种稳定排序。综合评价时间复杂度（平均）时间复杂度（最好）时间复杂度（最差）空间复杂度排序稳定性$O\left(n^2\right)$$O\left(n\right)$$O\left(n^2\right)$$O\left(1\right)$in-placeStable联系我们个人博客网址：http://www.bling2.cn/Github地址：https://github.com/lb971216008/Use-Python-to-Achieve知乎专栏：https://zhuanlan.zhihu.com/Use-Python-to-Achieve小专栏：https://xiaozhuanlan.com/Use-Python-to-Achieve
