# coding: utf-8

"""
插入排序

假如现在有一个序列 [54, 26, 93, 17, 77, 31, 44, 55, 20]
插入排序的规则就是按顺序取出数据，与前边的所有元素进行比较，如果比前边的小就交换位置
知道比前边的大为止

从第一个开始，前边没有元素，不用比较
取出第二个元素 26，与前边的 54 比较，小，交换位置 [26, 54, 93, 17, 77, 31, 44, 55, 20]

取出第三个元素 93，与前边的 54 比较，大，不交换位置

取出第四个元素 17，与前边的 93 比较，小，交换位置 [26, 54, 17, 93, 77, 31, 44, 55, 20]
	17 继续和前边的 54 比较，小，交换位置 [26, 17, 54, 93, 77, 31, 44, 55, 20]
	17 继续和前边的 26 比较，小，交换位置 [17, 26, 54, 93, 77, 31, 44, 55, 20]
	此时前边没有元素了，不再比较

取出第五个元素 77，与前边的 93 比较，小，交换位置 [17, 26, 54, 77, 93, 31, 44, 55, 20]
	77 继续和前边的 54 比较，大，不交换位置，不再比较

。。。

不算第一个，共取 n-1 次

"""


def insert_sort(alist):
	# 再做外层循环，共取n-1次
	for j in range(1, len(alist)):
		# 先做内层，做交换，起始索引为 1，第一个不考虑
		i = j
		# 交换到前边没有元素时退出
		while i > 0:
			# 如果取出的元素比前边的小，交换位置，让i-1，继续和前边的比较，比前边大时退出while循环
			if alist[i] < alist[i-1]:
				alist[i], alist[i-1] = alist[i-1], alist[i]
				i -= 1
			else:
				break

if __name__ == '__main__':
	alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
	insert_sort(alist)
	print(alist)
