参考链接: Python中的插入排序insertion sort
基本算法之插入排序(Insertion Sort)
基本算法—02、插入排序(Insertion Sort)算法 冒泡排序已经发布,大家快去看看啊! 后面几天会把选择排序,归并排序,快速排序等等都发布的!欢迎大家批评指正!
文章目录
基本算法之插入排序(Insertion Sort)0、前言1、插入排序算法是什么?2、算法过程图解3、代码实现4、评判算法
0、前言
评判一个算法的好坏的标准:
时间复杂度空间复杂度
1、插入排序算法是什么?
有一个已经有序的数据序列,要求这个已经排好的数据序列中插入一个数,但是要求插入之后数据序列依旧有序,这时候就要用到一种排序方法------插入排序法(insertion Sort)。 插入排序的基本操作就是把数据插入到排序好的数据数列中,从而得到一个新的,个数加一的有序数列,适合少量数据的排序。是一种稳定的排序算法。
2、算法过程图解
3、代码实现
代码如下(示例01):
"""
Insertion Sort 插入排序
时间复杂度:O(N^2)
"""
def insertion_sort(alist):
for i in range(1,len(alist)):
# 循环子序列的时候,就要反着来!
for j in range(i,0,-1):
# 如果后面一个数,大于前面的一个数,就交换位置
if alist[j]<alist[j-1]:
alist[j],alist[j-1]=alist[j-1],alist[j]
if __name__ == '__main__':
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(f'原列表的顺序:{alist}')
insertion_sort(alist)
print(f'选择排序之后的列表的顺序:{alist}')
注意一哈,比较的时候,取数据的是是倒着取出的!
4、评判算法
最坏时间复杂度:O(N^2)最好时间复杂度:O(n)平均时间复杂度:O(N^2)空间复杂度:O(1)算法稳定性:稳定的排序