<reponame>zlikun-lang/python-data-structure-and-algorithm<filename>sorts/insert.py
# 待排序列表
lst = [27, 12, 36, 12, 24, 45, 68, 59, 91]

# [27, 12, 36, 12, 24, 45, 68, 59, 91]
print(lst)

# 插入排序，参考：
# http://python.jobbole.com/82270/
# https://www.cnblogs.com/AlwinXu/p/5444799.html

# 从1开始遍历，第1个元素为初始有序列表，并将有序列表后的元素(哨兵)依次与有序列表比较，
# 如果哨兵比有序列表中的某个元素小，则该元素及后所有元素向后移动，哨兵则被插入到空缺的位置上
# 按照该思路，一直迭代直到最后一个元素比较完成后，序列将完全有序
# 算法的时间复杂度为O(n^2)，是一种稳定的算法
for i in range(1, len(lst)):
    sentinel = lst[i]
    # 由于要向后移动，所以内层循环倒着循环(从后向前)
    for j in range(i - 1, -1, -1):
        if sentinel < lst[j]:
            # 如果被比较的元素比哨兵大，那么就向后移动，并将哨兵插入到该位置(赋值)
            lst[j + 1], lst[j] = lst[j], sentinel
        else:
            # 如果被比较的元素比哨兵小或相等，那么就停止比较，因为前面的序列是有序的，再向前比较只会更小
            break

# [12, 12, 16, 21, 27, 32, 44, 69, 71]
print(lst)
