插入排序

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

1. 默认序列中的第0个元素是有序的（因为只有一个元素a[0]嘛，自然是有序的）；
2. 从下标为1（下标0没啥好插的）的元素开始，取当前下标i位置处的元素a[i]保存到一个临时变量waitInsert里；
3. waitInsert与对前半部分有序序列的循环遍历比较，直到遇到第一个比waitInsert大的元素（这里默认是从小到大排序），此时的下标为j，然后将其插入到j的位置即可；
4. 因为前面的插入，导致后面元素向后推移一个位置，没关系，把原来下标i的元素弹出即可；
5. 重复进行第2步到第4步，直到乱序序列中的元素被全部插入到有序序列中；
6. 经过以上5个步骤之后，整体序列必然有序，排序完成。

# 直接插入排序
def insertSort(relist):
    len_ = len(relist)
    for i in range(1,len_):  
        for j in range(i):
            if relist[i] < relist[j]:
                relist.insert(j,relist[i])  # 首先碰到第一个比自己大的数字，赶紧刹车，停在那，所以选择insert
                relist.pop(i+1)  # 因为前面的insert操作，所以后面位数+1，这个位置的数已经insert到前面去了，所以pop弹出
                break
    return relist

print insertSort([1,5,2,6,9,3])