插入排序的时间复杂度是多少？

插入排序的时间复杂度取决于排序的情况，最好情况下的时间复杂度为O(n)，最坏情况下的时间复杂度为O(n^2)，平均情况下的时间复杂度也为O(n^2)。其中，最好情况指的是已经排好序的情况，此时只需要比较一次就可以确定元素的位置；最坏情况指的是待排序列是逆序的情况，此时每次插入都需要移动已排序序列中的所有元素才能确定元素的位置。但是，实际使用时，插入排序的性能较好，因为它是一个简单的算法，适用于小数据集或部分已经排好序的数据。
- 以下是一个python的插入排序的改进代码，可以通过减少元素交换来提高效率 [^1]

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr