如何实现插入排序? 时间和空间复杂度是多少？

插入排序是一种简单直观的排序算法，其基本思想是将待排序的元素插入到已经有序的子序列中，使之成为一个新的有序序列。

以下是 Python 代码实现插入排序算法：

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

时间复杂度：插入排序的时间复杂度与输入数据的初始状态有关，最好情况下为 $O(N)$，此时待排序的数组已经有序，不需要进行任何移动；最坏情况下为 $O(N^2)$，此时待排序的数组是倒序排列的，每个元素都要移动，所以时间复杂度较高。平均情况下，时间复杂度为 $O(N^2)$。

空间复杂度：插入排序算法的空间复杂度为 $O(1)$，因为它是在原始的数组中进行排序，不需要额外占用空间。