插入排序

插入排序的核心思想是逐步构建有序序列，通过将未排序的元素插入到已排序部分的适当位置来实现排序。

步骤

1. 初始化：从数组的第二个元素开始，将其作为第一个未排序的元素。

2. 插入过程：

   • 将当前元素与已排序部分的元素从右到左依次比较。
   • 如果已排序部分的元素比当前元素大，则将已排序元素向右移动一位。
   • 重复上述步骤，直到找到一个不大于当前元素的元素或到达已排序部分的最左端。
   • 将当前元素插入到适当的位置。

3. 重复：对数组中的每一个未排序元素重复上述步骤，直到整个数组变得有序。

即假定一侧有序，然后将无序元素插入适当位置。

复杂度分析

平均情况

• 插入排序的平均时间复杂度为O(n^2)，因为对于每个元素，都可能需要与已排序部分的所有元素进行比较和移动。

最坏情况

• 最坏情况下，数组是反序的，即每个元素都需要与之前的所有元素比较，时间复杂度仍为O(n^2)。

最好情况

• 最好情况下，数组已经有序，只需O(n)的时间，即每个元素只需与前一个元素进行一次比较。

特性

• 稳定性：插入排序是稳定的排序算法，不会改变相同元素的相对顺序。

• 原地排序：插入排序是原地排序，不需要额外的存储空间，空间复杂度为O(1)。

• 适用性：适用于小规模数组或部分已排序的数组，在处理小规模或几乎有序的数据时，插入排序的效率甚至可能高于一些复杂度更低的排序算法。

总结

插入排序通过逐步构建有序序列来完成排序，虽然时间复杂度为O(n^2)，但在小规模或部分有序的数据下表现良好。此外，它是一个稳定的排序算法，能够保持相同元素的相对顺序。