回头看 之 插入排序

原理:在给定的序列里构造子序列，将插入的元素与子序列的元素倒序比较，如果插入元素小于子序列最后一个元素，则插入，否则待插入元素索引减一，重复执行

def insertionSort(arr):

    for i in range(1, len(arr)):

        key = arr[i]

        j = i-1

        while j >=0 and key < arr[j] :

                arr[j+1] = arr[j]

                j -= 1

        arr[j+1] = key

arr = [12, 11, 13, 5, 6]

insertionSort(arr)

print ("排序后的数组:")

for i in range(len(arr)):

    print ("%d" %arr[i])