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

推荐答案

-- -------------------- ---- -------
-------- ------------------ -
    --- ---- - - -- - - ----------- ---- -
        --- --- - -------
        --- - - - - --
        ----- -- -- - -- ------ - ---- -
            ----- - -- - -------
            - - - - --
        -
        ----- - -- - ----
    -
    ------ ----
-

本题详细解读

插入排序的基本思想

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

代码解析

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

时间复杂度

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

空间复杂度

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

适用场景

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