#插入排序法：
原理：是通过构建有序序列，对于未排序数据，在已排序序列中 从后向前 扫描，找到相应位置并插入。
#插入排序法一：有小到大排序
def insertSort(arr):
n=len(arr) #获取数列的元素个数
for i in range(1,n):
key=arr[i] #从数列的第二个元素开始，依次取出,与它的前面的元素值作比较
j=i-1 #获取key前面的值的索引下标
while j>=0 and key < arr[j]:#判断key与它前面的元素相比较,如果前面的值大于key
arr[j+1]=arr[j] #则把前面的值后移到key值的位置
j-=1 #获取再前面的值的索引下标，实现key值与其前面的值的循环比较
arr[j+1]=key
#测试
arr=[12,11,13,5,6]
insertSort(arr)
for i in range(len(arr)):
print("%d" %arr[i])
#插入排序法二：有大到小排序
def insertSort(arr):
n=len(arr) #获取数列的元素个数
for i in range(1,n):
key=arr[i] #从数列的第二个元素开始，依次取出,与它的前面的元素值作比较
j=i-1 #获取key前面的值的索引下标
while j>=0 and key > arr[j]:#判断key与它前面的元素相比较,如果前面的值大于key
arr[j+1]=arr[j] #则把前面的值后移到key值的位置
j-=1 #获取再前面的值的索引下标，实现key值与其前面的值的循环比较
arr[j+1]=key
#测试
arr=[12,11,13,5,6]
insertSort(arr)
for i in range(len(arr)):
print("%d" %arr[i])
