1. 图解

2. 代码

from typing import List


class Solution:
    # 插入排序
    def insert_sort(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(1, n):
            if nums[i - 1] > nums[i]:
                # 将这个值取出
                temp = nums[i]
                # 保存下标
                index = i
                for j in range(i - 1, -1, -1):
                    if nums[j] > temp:
                        nums[j + 1] = nums[j]
                        index = j
                    else:
                        break
                nums[index] = temp
        return nums


if __name__ == "__main__":
    s = Solution()
    nums = [3,4,2,1,3,4,5,67,19]
    a = s.insert_sort(nums)
    print(a)