1.3.1 插入排序的原理

插入排序算法也是一种常见的排序算法，其基本思想是：将需要排序的数据分为有序和无序两部分，排序的每一步将无序部分的数据插入前面已经排好序的有序部分，直到插完所有数据元素为止。

在实现插入排序算法时，每次从无序部分中取出一个元素与有序部分中的元素从后向前依次进行比较，并找到合适的位置将该元素插到有序部分。

假设6个要排序的数据元素为2、3、5、9、4和7。下面以该排序过程中的其中一个步骤为例，说明插入排序算法的具体实现过程。在插入排序过程中，6个数据元素中的有序部分为（2、3、5、9），无序部分为（4,7），需要将无序部分的数据元素4插入有序部分，具体过程如下。

（1）原始的数组元素排列顺序如下：

其中，带有阴影的数据元素表示有序部分，不带阴影的数据元素表示无序部分。

（2）在无序部分挑出要插入有序部分的数据元素4，将要插入的数据元素4与该数据元素左边最近的有序部分的元素进行比较。由于4 < 9，因此数据元素9向后移动，而数据元素4向前移动：

（3）将要插入的数据元素4与该数据元素左边最近的有序部分的数据元素5进行比较。由于4 < 5，因此数据元素5向后移动，而数据元素4继续向前移动：

（4）将要插入的数据元素4与该数据元素左边最近的有序部分的数据元素3进行比较。由于4 > 3，因此不需要再向前比较，将数据元素4插入当前位置：

此时，有序部分的数据元素由开始的（2、3、5、9）变成了（2、3、4、5、9）。