插入排序演示

算法步骤

1. 将第一个元素视为已排序部分，其他元素为未排序部分。
2. 从未排序部分取出一个元素，称为"当前元素"。
3. 从已排序部分的末尾开始，逐步向前比较当前元素与已排序元素。
4. 如果已排序元素大于当前元素，则将已排序元素向后移动一位。
5. 找到合适的位置后，将当前元素放入。
6. 重复步骤 2-5，直到未排序部分为空。

时间复杂度

最坏情况: O(n²) - 当数组是逆序时

最好情况: O(n) - 当数组已经是正序时

平均情况: O(n²)

空间复杂度

O(1) - 原地排序，不需要额外的额外空间

稳定性

插入排序是稳定的排序算法，相同元素的相对顺序不会改变。