插入排序学习笔记

插入排序，是一种简单的排序算法。它的基本思想是将未排序的元素一个个地插入到已排序区间的适当位置上，直到全部元素都插入完毕。

算法步骤

1. 将待排序数组分为已排序区间和未排序区间
2. 取出未排序区间中的第一个元素
3. 将该元素与已排序区间中的元素从后往前比较，找到合适的位置进行插入
4. 重复步骤2-3，直到未排序区间为空

实例演示

假设我们有一个待排序数组 [5, 2, 8, 11, 3, 6]，我们可以使用插入排序来对它进行排序。

首先，将数组分为已排序区间和未排序区间，初始时已排序区间只包含一个元素 [5]，未排序区间包含剩下的元素 [2, 8, 11, 3, 6]。

取出未排序区间中的第一个元素 2，将它与已排序区间中的元素 5 比较，发现 2 < 5，因此将 2 插入到 5 的前面，得到已排序区间 [2, 5]，未排序区间 [8, 11, 3, 6]。

重复上述步骤，取出 8 并将它插入到已排序区间 [2, 5] 的适当位置上，得到已排序区间 [2, 5, 8]，未排序区间 [11, 3, 6]。

再次重复，取出 11 并将它插入到已排序区间 [2, 5, 8] 的适当位置上，得到已排序区间 [2, 5, 8, 11]，未排序区间 [3, 6]。

继续进行插入操作，最终得到已排序数组 [2, 3, 5, 6, 8, 11]，排序完成。

复杂度分析

插入排序的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。如果待排序数组本就是有序的，那么时间复杂度可以达到 $O(n)$。因此插入排序适用于小规模数据的排序。