插入排序

基本思想

将元素依次插入到已排好的序列中。（将nums[0]看做已排好的序列）

具体实现

def insertion_sort(nums: List):
    length = len(nums)
    for i in range(1, length):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j+1] = nums[j]
            j -= 1
        nums[j+1] = key

性能分析

平均时间复杂度：

• 计算数组长度length：
• 两次循环：
• 总计：

因为插入排序隐含的常数因子非常小，所以在数组不大的情况下（如小于20）通常选择插入排序

空间复杂度：