插入排序

###1. 算法思想

  1. 对少量元素进行排序的有效算法，类似于打牌
  2. 每次摸起一张牌，找到这张牌的正确位置，将它与手中已有的牌从右到左进行比较。
    • 从右到左比较的原因是方便对元素进行右移，进而找到合适的位置。
  3. 输入的数字原地排序。

###2. 代码实现

class Solution:
    def insert_sort(self, nums:List[int]) -> List[int]:
        for i in range(1, len(nums)):
            key = nums[i]
            j = i -1 # 排好序的最右端元素
            while j >= 0 and nums[j] > key: # 若元素大于key,则将元素右移，直至找到合适的位置
                nums[j + 1] = nums[j]
                j -= 1
            nums[j + 1] = key # 将元素插入到合适位置，j在前面多减了一次1，加上1
        return nums