Python全系列 教程
3567个小节阅读:5931.8k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本,未来主流的版本
人工智能 教程
顺势而为,AI创新未来
大厂算法 教程
算法,程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理与手动整理一副牌的过程非常相似
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
从第1个元素开始,该元素可以认为已经被排序;
取出下1个元素,在已经排序的元素序列中从后向前扫描;
如果该元素大于新元素,将该元素移到下一位置;
重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
将新元素插入到该位置后;
重复步骤2~5。
xxxxxxxxxx
def 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