插入排序

#对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要(N^2)/4次比较以及(N^2)/4次交换。
#最坏情况下需要(N^2)/2次比较以及(N^2)/2次交换。
#最好情况下需要N-1次比较和0次交换。
def chaRu(shuzu):
    N = len(shuzu)#获得数组的长度
    for i in range(1,N):
        j = i
        while j > 0:
            if a[j - 1] > a[j]:
                a[j-1],a[j] = a[j],a[j-1]
            j = j - 1

插入排序

原文：http://my.oschina.net/stevenKelly/blog/390282