实现插入排序 题目描述：给定一个整数数组，使用插入排序算法将其按升序排列。插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 解题过程： 基本思路 插入排序将数组分为两部分：左侧已排序部分和右侧未排序部分。初始时已排序部分只包含第一个元素，然后依次将未排序部分的元素插入到已排序部分的正确位置。 具体步骤 从第二个元素开始（索引1），将其作为当前需要插入的元素 将当前元素与已排序部分的元素从后往前比较 如果当前元素小于比较的元素，则将比较的元素向后移动一位 重复此过程直到找到合适的位置，将当前元素插入 示例演示 以数组 [ 5, 2, 4, 6, 1, 3 ] 为例： 第一轮：已排序[ 5 ]，当前元素2 2 < 5，5向右移动 → [ 5, 5, 4, 6, 1, 3 ] 插入2到位置0 → [ 2, 5, 4, 6, 1, 3 ] 第二轮：已排序[ 2,5 ]，当前元素4 4 < 5，5向右移动 → [ 2,5,5,6,1,3 ] 4 > 2，插入4到位置1 → [ 2,4,5,6,1,3 ] 第三轮：已排序[ 2,4,5 ]，当前元素6 6 > 5，直接保留 → [ 2,4,5,6,1,3 ] 第四轮：已排序[ 2,4,5,6 ]，当前元素1 1 < 6，6右移 → [ 2,4,5,6,6,3 ] 1 < 5，5右移 → [ 2,4,5,5,6,3 ] 1 < 4，4右移 → [ 2,4,4,5,6,3 ] 1 < 2，2右移 → [ 2,2,4,5,6,3 ] 插入1到位置0 → [ 1,2,4,5,6,3 ] 第五轮：已排序[ 1,2,4,5,6 ]，当前元素3 3 < 6，6右移 → [ 1,2,4,5,6,6 ] 3 < 5，5右移 → [ 1,2,4,5,5,6 ] 3 < 4，4右移 → [ 1,2,4,4,5,6 ] 3 > 2，插入3到位置2 → [ 1,2,3,4,5,6 ] 算法实现要点 使用双重循环：外层循环遍历未排序元素，内层循环在已排序部分寻找插入位置 在移动元素时，需要从后往前依次后移 时间复杂度：最好情况O(n)（已排序），最坏情况O(n²)，平均O(n²) 空间复杂度：O(1)，是原地排序算法