1.插入排序
插入排序是对少量元素进行排序的有效算法。
插入排序属于原地排序(sorted in place),即在排序时,仅仅需要常数个数存储在原数组以外。
代码如下:
#INSERTION-sort(A)
A = [5,2,4,6,1,3]
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 -= 1
A[i + 1] = key
print(A)
插入排序的时间复杂度为O(n的平方),插入排序是稳定排序