插入排序

目录

执行过程

insertion_sort_1.png

图1  执行过程图

python

#!/usr/bin/env python
#coding=utf8
a=[3,2,4,3,5]

def insertSort(a):
    for j in range(1,len(a)):
        key = a[j]
        i = j - 1
        while i>=0 and a[i] > key:
            a[i+1] = a[i]
            i = i-1
        a[i+1]=key
    return a
print insertSort(a)

算法想想好像很简单,但是如何证明这个算法的正确性呢?

目录