• 比对复杂度是O(n^2)
  • 假设数列第一个元素为已排序数列，剩余数列为未排序将待排序元素挨个插入到已排序数列中每次插入都必须保证数列是有序的，即通过比较和移动有序数列中的元素，将元素插入到合适的位置
  • 思路：如同玩扑克牌一样，每次摸牌都将它与手中的牌比较，始终将牌放在比它大的牌前面，比它小的牌后面。这样当牌全部摸到手上后，就是一个有序的序列。从后往前找合适的位置。 
def insertSort(alist):
    for index in range(1,len(alist)):
        currentvalue = alist[index]
        position = index
        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position - 1]         
            position = position - 1
        alist[position] = currentvalue