Python实现插入排序
1、打开Python开发工具IDLE,新建‘插入.py’并写代码如下：
#插入
def charu(list1):
n = len(list1)
for i in range(1,0,-1):
if list1[i]<list1[i-1]:
list1[i],list1[i-1]=list1[i-1],list1[i]
if __name__=='__main__':
list1 = [2,1,9,0]
charu(list1)
print (list1)
2、F5运行程序，会发现列表的第1位和第0位数交换了，这是因为插入排序事先认为已经是一个排好的序列，每次从后向前一旦发现前面的数大于后面的数，就进行交换，直到前面的数小于后面的数
打印出内容如下：
[1, 2, 9, 0]
3、继续编写代码，套一个外层循环，目的是取数，内层循环负责比较，代码如下：
#插入
def charu(list1):
n = len(list1)
for j in range(n-1):
for i in range(j+1,0,-1):
if list1[i]<list1[i-1]:
list1[i],list1[i-1]=list1[i-1],list1[i]
if __name__=='__main__':
list1 = [2,1,9,0]
charu(list1)
print (list1)
4、F5运行程序，列表被正确排序了
[0, 1, 2, 9]
5、优化一下插入函数，因为默认是已经排好序的列表，当后面的值大于前面的值，那就一定大于前面所有值。内层循环提前结束，代码如下：
#插入
def charu(list1):
n = len(list1)
for j in range(n-1):
for i in range(j+1,0,-1):
if list1[i]<list1[i-1]:
list1[i],list1[i-1]=list1[i-1],list1[i]
else:
break
if __name__=='__main__':
list1 = [2,1,9,0]
charu(list1)
print (list1)
6、F5运行程序，列表被正确排序了
[0, 1, 2, 9]
这就是完善的插入排序算法
