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]
循環(huán)不變性:
- 初始化: 循環(huán)的第一次迭代之前,他為真.
- 保持: 如果循環(huán)的某次迭代之前為真, 下次迭代之前仍為真
- 終止: 循環(huán)終止時(shí),不變式提供一個(gè)有用的性質(zhì)證明算法的正確性
對(duì)于插入排序算法:
- 初始化: 循環(huán)之前,排序好的數(shù)組即原數(shù)組第一個(gè)數(shù)字,為單個(gè)元素A[1]
- 保持: 每次循環(huán),排序好的數(shù)組中比要插入的數(shù)大的右移,循環(huán)結(jié)束,插入數(shù)字,對(duì)于下一次循環(huán)來說子數(shù)組仍是有序的
- 終止: 導(dǎo)致終止的條件是 j > A.length, 終止后,原數(shù)組的數(shù)字都已插入字?jǐn)?shù)組,且是有序的,所以算法正確
歡迎關(guān)注我的博客Vagitus – Pythonista
