插入排序算法,平均时间复杂度 O(n²)

python 实现:

import random

A=[x for x in range(10000)]
random.shuffle(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
print A