插入排序——Python

1. 算法步骤
   将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
   从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

2. 代码

#!/usr/bin/python

list = [10,6,4,8,2,9,1] 
def insertionSorted(list):
    for i in range(1, len(list)):
        preIndex = i-1  #前一个是有序序列
        current = list[i]   #从第一个到最后一个是待排序序列
        while preIndex >= 0 and list[preIndex] > current:   #当第i比i-1小时
            list[preIndex+1] = list[preIndex]   
            preIndex-=1
        list[preIndex+1] = current
                
    return list

print(insertionSorted(list))