编写一个函数，实现插入排序

推荐答案

// www.javascriptcn.com code example
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    return arr;
}

本题详细解读

插入排序的基本思想

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码解析

1. 外层循环：从数组的第二个元素开始遍历（i = 1），因为第一个元素默认是已排序的。
2. 内层循环：从当前元素的前一个元素开始向前遍历（j = i - 1），如果当前元素比前一个元素小，则将前一个元素向后移动一位。
3. 插入操作：当找到合适的位置时，将当前元素插入到该位置。
4. 返回结果：最终返回排序后的数组。

时间复杂度

• 最好情况：当输入数组已经是有序的，插入排序的时间复杂度为 O(n)。
• 最坏情况：当输入数组是逆序的，插入排序的时间复杂度为 O(n^2)。
• 平均情况：插入排序的时间复杂度为 O(n^2)。

空间复杂度

插入排序是原地排序算法，空间复杂度为 O(1)。

适用场景

插入排序适用于小规模数据的排序，或者当输入数据基本有序时，插入排序的效率会比较高。