插入排序通过将每个元素插入到其前面的有序部分来逐步排序数组。
（启动排序后点击下面的步骤可以显示详情）
暂无步骤，请点击上面的“开始排序”按钮
1. 初始化：将第一个元素视为已排序部分，其他元素为未排序部分。
2. 遍历未排序部分：从未排序部分取出一个元素，称为“当前元素”。
3. 插入过程：从已排序部分的末尾开始，逐步向前比较“当前元素”与已排序部分的元素。如果已排序元素大于“当前元素”，则将已排序元素向后移动一位。
4. 放置当前元素：找到合适的位置后，将“当前元素”放入这个位置。
5. 重复：重复步骤2至4，直到未排序部分为空。
最坏情况：O(n²)，当数组是逆序时。
最好情况：O(n)，当数组已经是正序时。
平均情况：O(n²)。
空间复杂度：O(1)，由于是原地排序，不需要额外的存储空间。
插入排序是稳定的排序算法，即相同元素的相对顺序不会改变。
