写一个方法实现“插入排序算法”，并解释下时间复杂度和空间复杂度

插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

以下是一个使用JavaScript实现的插入排序算法：

function insertionSort(arr) {
    let n = arr.length;
    for (let i = 1; i < n; i++) {
        // 选择一个待插入的数据
        let value = arr[i];
        // 从已排序序列中从后向前扫描
        let j = i - 1;
        while (j >= 0) {
            if (arr[j] > value) {
                // 如果该元素（已排序）大于新元素，将该元素移到下一位置
                arr[j + 1] = arr[j];
            } else {
                // 找到已排序的元素小于或者等于新元素的位置，即找到了插入位置
                break;
            }
            j--;
        }
        // 插入新元素
        arr[j + 1] = value;
    }
    return arr;
}

时间复杂度：

• 最好情况：输入数组已经是升序排列了，那么此时的时间复杂度是O(n)，因为此时内层循环（while语句）将不会执行。
• 最坏情况：输入数组是降序排列，那么此时的时间复杂度是O(n^2)。因为此时内层循环（while语句）每次都会执行，将每个元素都移动到其应该在的位置。
• 平均情况：时间复杂度也是O(n^{2)。因此，虽然插入排序在处理部分已排序的数据时可能效率较高，但在平均情况下，其性能并不优于其他O(n}2)的排序算法。

空间复杂度：

• 插入排序的空间复杂度是O(1)。这是因为它是一种原地排序算法，只需要一个额外的存储空间来暂存待插入的元素。也就是说，这个算法只需要常量级的额外空间，与输入数组的大小无关。