插入排序
插入排序是一种简单直观的排序算法，类似于我们整理扑克牌的方式。它的工作原理是将数组分为已排序和未排序两部分，依次将未排序元素插入到已排序部分的正确位置。
算法原理
插入排序的基本思想是：假设第一个元素已经有序，从第二个元素开始，将每个元素插入到前面已排序部分的正确位置。对于每个元素，从后向前比较，找到合适的位置插入。这个过程重复进行，直到所有元素都排好序。
算法步骤
- 将数组分为已排序部分（初始包含第一个元素）和未排序部分
- 从第二个元素开始，依次处理未排序部分的每个元素
- 对于当前元素，从后向前与已排序部分的元素比较
- 找到合适的位置，将当前元素插入到该位置
- 重复上述步骤，直到所有元素都排好序
时间复杂度
- 最坏情况：O(n²) - 当列表是逆序时
- 平均情况：O(n²)
- 最好情况：O(n) - 当列表已经有序时
空间复杂度
O(1) - 插入排序是原地排序算法，只需要常数级别的额外空间。
稳定性
插入排序是稳定的排序算法，相等元素的相对顺序不会改变。
适用场景
- 数据规模较小的排序任务
- 几乎已经有序的数据
- 在线排序（数据逐步到达的情况）
优缺点
- 优点：算法简单，易于实现；对小规模数据效率高；稳定；对几乎有序的数据效率很高
- 缺点：时间复杂度高，不适合大规模数据；需要频繁移动元素