插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理类似于我们整理扑克牌的过程，从左到右逐步扩大已排序的部分，将当前元素插入到已排序部分的适当位置，直到整个序列有序。

算法原理

1. 初始状态：已排序部分只有第一个元素。
2. 从第二个元素开始：逐一取出元素，将其插入到已排序部分的适当位置。
3. 重复步骤2：直到所有元素均插入到已排序部分。

插入排序的优缺点

优点：

• 算法简单，易于理解和实现。
• 对于少量元素的数组或几乎已经排好序的数组，插入排序非常高效。
• 是稳定排序算法，保证相等元素的相对位置不变。

缺点：

• 对于大规模数组，插入排序的效率较低，时间复杂度为O(n^2)。

插入排序的步骤示例

初始状态：

[5, 2, 9, 1, 5, 6]

• 已排序部分：[5]

• 第二个元素2：

  • 将2插入到已排序部分 [5] 之前。

[2, 5, 9, 1, 5, 6]

• 已排序部分：[2, 5]

• 第三个元素9：

  • 将9插入到已排序部分 [2, 5] 之后。

[2, 5, 9, 1, 5, 6]

• 已排序部分：[2, 5, 9]

• 第四个元素1：

  • 将1插入到已排序部分 [2, 5, 9] 之前。

[1, 2, 5, 9, 5, 6]

• 已排序部分：[1, 2, 5, 9]

• 第五个元素5：

  • 将5插入到已排序部分 [1, 2, 5, 9] 的适当位置。

[1, 2, 5, 5, 9, 6]

• 已排序部分：[1, 2, 5, 5, 9]

• 第六个元素6：

  • 将6插入到已排序部分 [1, 2, 5, 5, 9] 的适当位置。

[1, 2, 5, 5, 6, 9]