算法：插入排序（InsertSort）

1. 基本原理

每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

2. 动画展示

3. 代码示例

4. 特性分析

• 时间复杂度：最好（O(n)）、平均（O(n^2)）、最差（O(n^2)）；
• 空间复杂度：~O(1)；
• 算法稳定性：稳定；

注意，与选择排序相比：

• 最坏情况下，选择排序、插入排序的时间复杂度都是O(n^2)；
• 当数组基本有序时，插入排序更好一点；
• 选择排序在任何条件下，最多移动 O(n) 次元素；插入排序最差可能移动 O(n^2)次；

划个水 ~