导语： 插入排序是一种简单而常用的排序算法，它的基本思想是将待排序的元素逐个插入到已排序序列中的正确位置，从而得到一个有序序列。本文将深入剖析选择插入算法的原理、步骤以及时间复杂度分析，并加于图形示例帮助读者全面理解这一经典算法。
概要
插入排序是一种简单且高效的排序算法，它通过将元素逐步插入到已排序序列的正确位置来构建有序序列。
基本思想
从第二个元素开始，将每个元素插入到已排序序列的正确位置。已排序序列始终保持在前，未排序元素逐个插入到正确位置。通过比较和移动元素，直到整个数组有序。
步骤剖析
我们以数组 [5, 1, 3, 2, 4] 为例来详细解释插入排序的步骤。
初始状态：待排序数组为 [5, 1, 3, 2, 4]，可以将其分为两个部分：已排序部分和未排序部分。一开始，已排序部分只包含第一个元素 5，而其余元素都属于未排序部分。
步骤1：从第二个元素开始，也就是 1，将其作为待插入元素。此时，已排序部分只有一个元素 5，未排序部分为 [1, 3, 2, 4]。
步骤2：将待插入元素 1 与已排序部分中的元素 5 进行比较。由于 1 小于 5，我们需要将 5 向右移动一个位置，为待插入元素 1 腾出正确的位置。此时，已排序部分变为 [1, 5]，未排序部分为 [3, 2, 4]。
步骤3：继续比较待插入元素 3 与已排序部分中的最后一个元素 5 。由于 3 小于 5，我们再次将 5 向右移动一个位置。此时，已排序部分变为 [1, 5, 5]，未排序部分为 [3, 2, 4]。
步骤4：继续比较待插入元素 3 与已排序部分中的下一个元素 1。这一次，我们发现 3 不再小于 1，意味着我们已经找到了待插入元素 3 的正确位置。此时，已排序部分变为 [1, 3, 5]，未排序部分为 [ 2, 4]。
步骤5：我们继续处理下一个待插入元素 2。将其与已排序部分中的元素进行比较。通过依次比较，我们找到了 2 的正确位置，并将其插入。此时，已排序部分变为 [1, 2, 3, 5]，未排序部分为 [ 4]。
步骤6：最后，我们处理最后一个待插入元素 4。将其与已排序部分中的元素进行比较，并将其插入到正确的位置。此时，已排序部分变为 [1, 2, 3, 4, 5]，未排序部分为空。
最终，我们完成了整个插入排序过程，得到了有序数组 [1, 2, 3, 4, 5]。
通过这个例子，我们可以清楚地看到插入排序算法的每个步骤是如何将待排序元素逐个插入到已排序序列中的正确位置的。重复这个过程，直到所有元素都被插入到正确的位置，我们就得到了一个有序序列。
时间复杂度分析
插入排序的时间复杂度分析是衡量算法效率的重要指标，下面对插入排序的时间复杂度进行分析：
最好情况：如果待排序的数组已经是有序的，插入排序只需要进行 n-1 次比较，无需进行元素的移动操作，时间复杂度为 O(n)。最坏情况：如果待排序的数组是逆序的，每个元素都需要与已排序序列中的所有元素进行比较，并进行元素的移动操作，时间复杂度为 O(n^2)。平均情况：在平均情况下，插入排序每次遍历需要比较 i 次，其中 i 表示已排序的元素个数。因此，插入排序的平均时间复杂度为 O(n^2)。
插入排序的时间复杂度为 O(n^2)，其中 n 表示待排序数组的长度。尽管其时间复杂度较高，但对于小规模的数据排序，插入排序仍然具有一定的实用性。
性能分析
稳定性：插入排序是一种稳定的排序算法，即在排序过程中不会改变相等元素的相对顺序。空间复杂度：插入排序的空间复杂度为 O(1)，它只需要使用固定的额外空间来存储已排序元素。适应性：插入排序适用于小型数组和近乎有序的数组。实现简单：插入排序的思想简单，代码实现容易理解。
代码实现
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
System.out.println("原始数组：");
for (int num : arr) {
System.out.print(num + " ");
}
insertionSort(arr);
System.out.println("\n 排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
图形示范
总结
插入排序是一种简单直观的排序算法，通过将元素逐步插入到已排序序列中来构建有序序列。它的时间复杂度为 O(n^2)，空间复杂度为 O(1)，是一种稳定的排序算法。对于小型数组和近乎有序的数组，插入排序表现良好。在实际应用中，可根据具体情况选择适合的排序算法。希望这篇文章能帮助你理解插入排序的原理和实现。
相关链接
发表评论