目录Python全系列 教程
3567个小节阅读：5929.5k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理与手动整理一副牌的过程非常相似
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第1个元素开始，该元素可以认为已经被排序；
取出下1个元素，在已经排序的元素序列中从后向前扫描；
如果该元素大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
xxxxxxxxxxdef insertion_sort(nums:list[int]) ->None: for i in range(1,len(nums)): # 把要比较的数据存储下来 value = nums[i] # 获取要和哪个索引位置上的数据比较 j = i - 1 # 如果还数据，并且需要交换数据 while j>=0 and value < nums[j]: # 数据的位移 nums[j+1] = nums[j] # 继续比较前面一个位置上的数据 j -= 1 nums[j+1] = value时间复杂度 $ O(n^2) $、自适应排序：在最差情况下，每次插入操作分别需要循环 n−1、n−2、…、2、1 次，求和得到$ \frac {(n-1)n} {2} $ ，因此时间复杂度为 $ O(n^2) $ 。在遇到有序数据时，插入操作会提前终止。当输入数组完全有序时，插入排序达到最佳时间复杂度 $ O(n) $
空间复杂度 $ O (1) $、原地排序：指针 i 和 j 使用常数大小的额外空间
稳定排序：在插入操作过程中，我们会将元素插入到相等元素的右侧，不会改变它们的顺序
实时效果反馈
1. 关于插入排序算法，说法正确的是？
A 插入排序需要反复比较相邻的元素
B 插入排序需要俩俩比较的元素
C 插入排序只能从小到大排序
D 插入排序只能从大到小排序
答案
1=>B