插入排序

• 时间复杂度$O(N^2)$，空间复杂度$O(1)$

Attention

插入排序的时间复杂度受到输入数据尺寸的影响，有可能只看到一次就完成了排序，也有可能需要从头看到尾才能完成排序

• 思路：逐步保证 0~i 位置上有序。从 i 开始向前走，两两比较，把较小的数字换到前面；随后 i++，重复上述步骤。

• 演示：

• 伪代码：

for i in range(0, N):
	if i == 1: continue
	for j in range(i, 0, -1): # 注意 python 含左不含右
		if arr[j] < arr[j-1]:
			swap(arr[i-j], arr[i-j-1])
		else:
			break # 注意这里可以及时break出来！

• 实际代码

def insertSort(nums: List[int]) -> List[int]:
    N = len(nums)
    for i in range(0, N):
        if i == 0: continue
        # 注意 range 里的取值
        for j in range(i, 0,-1): 
	        # 有 j-1 注意 j 的取值不要让他越界
            if nums[j] < nums[j-1]: 
                temp = nums[j]
                nums[j]=nums[j-1]
                nums[j-1]=temp
            else:
                break
    return nums