1.伪代码
'''INSERTION-SORT(A)'''
for j = 2 to A.length
key = A[j]
//Insert A[j] into the sorted sequence A[1..j-1]
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[I]
i = i - 1
A[i+1] = key
算法流程图示
2.Python代码
def insertion_sort(A):
for j in range(1, len(A)):
key = A[j]
# Insert A[j] into the sorted sequence A[1..j-1]
i = j - 1
while i >= 0 and A[i] > key:
A[i+1] = A[I]
i = i - 1
A[i+1] = key
return A
result:
Before:
[29, 76, 65, 27, 75, 81, 1, 44, 77, 61]
After:
[1, 27, 29, 44, 61, 65, 75, 76, 77, 81]
循环不变性:
- 初始化: 循环的第一次迭代之前,他为真.
- 保持: 如果循环的某次迭代之前为真, 下次迭代之前仍为真
- 终止: 循环终止时,不变式提供一个有用的性质证明算法的正确性
对于插入排序算法:
- 初始化: 循环之前,排序好的数组即原数组第一个数字,为单个元素A[1]
- 保持: 每次循环,排序好的数组中比要插入的数大的右移,循环结束,插入数字,对于下一次循环来说子数组仍是有序的
- 终止: 导致终止的条件是 j > A.length, 终止后,原数组的数字都已插入字数组,且是有序的,所以算法正确
欢迎关注我的博客Vagitus – Pythonista
