经典排序算法1:插入排序（经典排序算法1:插入排序规则）

插入排序是一种简单的排序算法，其基本思想是将一个序列分为 已排序 和 未排序 两部分，逐步将未排序元素插入到已排序部分的正确位置，直到所有元素都被排序为止。

• 具体步骤

步骤1： 从第一个元素开始，该元素可以被认为已排序。

步骤2： 取出下一个元素，在已排序部分从后向前进行比较。

步骤3： 如果已排序元素大于新元素，则将已排序元素向后移动一位。

步骤4： 重复步骤 3，直到找到已排序元素小于或等于新元素的位置。

步骤5： 将新元素插入到找到的位置。

步骤6： 重复步骤 2~5，直到所有元素都被插入到正确的位置。

• 动画演示

下面将用动画演示这些步骤，例如将 36, 9, 50, 41, 49, 18, 9, 19, 49, 2 这一组元素用插入排序算法进行升序。

• 代码实现(Java版)

输出结果如下：

9, 36, 50, 41, 49, 18, 9, 19, 49, 2,

9, 36, 50, 41, 49, 18, 9, 19, 49, 2,

9, 36, 41, 50, 49, 18, 9, 19, 49, 2,

9, 36, 41, 49, 50, 18, 9, 19, 49, 2,

9, 18, 36, 41, 49, 50, 9, 19, 49, 2,

9, 9, 18, 36, 41, 49, 50, 19, 49, 2,

9, 9, 18, 19, 36, 41, 49, 50, 49, 2,

9, 9, 18, 19, 36, 41, 49, 49, 50, 2,

2, 9, 9, 18, 19, 36, 41, 49, 49, 50,

• 算法优化

对于上述插入排序的算法代码，在寻找合适的插入位置时，需要与前面的元素逐个比较大小来确定插入位置。由于插入排序是将待排序元素插入到一个有序序列中，因此我们可以使用二分搜索来确定插入位置，这样可以有效减少比较次数。

输出结果如下：

9, 36, 50, 41, 49, 18, 9, 19, 49, 2,

9, 36, 50, 41, 49, 18, 9, 19, 49, 2,

9, 36, 41, 50, 49, 18, 9, 19, 49, 2,

9, 36, 41, 49, 50, 18, 9, 19, 49, 2,

9, 18, 36, 41, 49, 50, 9, 19, 49, 2,

9, 9, 18, 36, 41, 49, 50, 19, 49, 2,

9, 9, 18, 19, 36, 41, 49, 50, 49, 2,

9, 9, 18, 19, 36, 41, 49, 49, 50, 2,

2, 9, 9, 18, 19, 36, 41, 49, 49, 50,