数据结构笔记：插入排序
原文地址
分类目录——数据结构笔记
前一部分有序序列，有一部分无序序列
与选择排序的不同是
选择排序是从无序序列中选一个最小值 插入排序是拿无需部分的第一个往有序部分插入，插入到合适位置实现
def insertsort(alist):
n = len(alist)
for i in range(1, n):
for j in range(i, 0, -1):
if alist[j]<alist[j-1]:
alist[j], alist[j-1] = alist[j-1], alist[j]
else:
break # 这么做可以省一些步数，因为前一部分已经是有序的了，一旦发现比前面大了，就没必要再往前比较了
测试
if __name__ == '__main__':
ll = [3,6,2,4,7,5,8,1,0]
print(ll)
insertsort(ll)
print(ll)
时间复杂度
最优时间复杂度：O(n) （升序排列，序列已经处于升序状态） 最坏时间复杂度：O(n^2) 稳定性：稳定作者：BBJG_001
相关文章
Xena
2020-07-03
Eirene
2020-12-09
Gella
2023-07-20
Emily
2023-07-20
Grizelda
2023-07-20
Gella
2023-07-20
Janna
2023-07-20
Ophelia
2023-07-21
Crystal
2023-07-21
Laila
2023-07-21
Aine
2023-07-21
Bliss
2023-07-21
Lillian
2023-07-21
Tertia
2023-07-21
Olive
2023-07-21
Angie
2023-07-21
Nora
2023-07-24
