插入排序（Insertion sort）

原理：
每插入一个数都要将它和之前的已经完成排序的序列进行重新排序，也就是将新插入的数对应原序列中的位置那么也就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序，时间复杂程度同样为O（n2）。这种排序算法是稳定的算法。

插入排序有点冒泡的感觉，他是从最后往前边一点一点的插入。

def insertion_sort(nums):
    for i in range(1, len(nums)):
        for j in range(i, 0, -1):
            if nums[j] < nums[j-1]:
                nums[j], nums[j-1] = nums[j-1], nums[j]


if __name__ == '__main__':
    nums = [5, 6, 8, 45, 52, 21, 37, 98]
    insertion_sort(nums)
    print(nums)