python 排序算法——插入排序

# 数据结构与算法
# 排序算法 -- 插入排序

# 插入排序的适用场景：一个新元素需要插入到一组已经是有序的数组
# 中，或者是一组基本有序的数组排序。
#
# 比较性：排序时元素之间需要比较，所以为比较排序
#
# 稳定性：从代码我们可以看出只有比较元素大于当前元素，比较元素
# 才会往后移动，所以相同元素是不会改变相对顺序
#
# 时间复杂度：插入排序同样需要两次循坏一个一个比较，故时间复杂
# 度也为O(n^2)
#
# 空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)
#
# 记忆方法：想象成在书架中插书：先找到相应位置，将后面的书往后推，
# 再将书插入

def insert_sort(alist):
	for i in range(1,len(alist)):
		for j in range(i,0,-1):
			if alist[j] < alist[j-1]:
				alist[j-1], alist[j] = alist[j], alist[j-1]
			else:	
				break	
				
lis = [3,2,5,7,2,8,8,3,44,75,3]
insert_sort(lis)
print(lis)