一、什么是插入排序
插入排序是一种最简单的排序方法，其基本思想是将一个记录插入到已经排好序的有序表中，从而形成一个新的、记录数增1的有序表。其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素进行遍历，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动
二、插入排序算法步骤
- 将第一个元素视为已经排序好的序列。
- 从第二个元素开始，逐个将待排序元素插入到已排序序列的合适位置，以保持已排序序列的有序性。
- 重复上述过程，直到所有元素都被插入到正确的位置，得到完整的有序序列。
三、插入排序的使用场景主要包括
- 数据量不大，数据局部有序或者整体有序的情况。因为在这种情况下，插入排序的效率较高，时间复杂度为O(n^2)。
- 算法稳定性要求高的情况。插入排序是一种稳定的排序方式，对于有相同元素的情况，插入排序能够保持它们的相对顺序不变。
- 对数据的插入操作频繁，需要经常进行插入排序的情况。插入排序的实现方式比较简单，适合于频繁进行插入和删除操作的场景。
- 数据规模较小，时间复杂度要求不高的情况。
四、什么时候会用到插入排序
- 小规模数据：由于插入排序的简单性和稳定性，适用于小规模数据的排序。
- 部分有序数据：当数据集合部分有序时，插入排序的表现较好，时间复杂度较低。
- 在线性表中插入元素时：如果需要在一个线性表中不断插入新元素并保持有序性，插入排序是个不错的选择
五、插入排序的知识点
- 稳定性：插入排序是一种稳定的排序算法，相同元素的相对位置在排序前后不会改变。
- 时间复杂度：平均情况下，插入排序的时间复杂度为 O(n^2)，最好情况下为 O(n)，最坏情况下为 O(n^2)。
- 空间复杂度：插入排序是一种原地排序算法，只需要常数级别的额外空间，空间复杂度为 O(1)。
- 高效性：在小规模数据或者部分有序数据的情况下，插入排序效率较高。
- 基本思想：将每个元素插入到已排序的部分的正确位置。
- 时间复杂度：最好情况下为，即数组已经有序；最坏情况下为，即数组逆序。
- 空间复杂度：为，因为它只使用了固定的额外空间。
- 稳定性：插入排序是一种稳定的排序算法，即相同的元素在排序前后的相对顺序保持不变。
六、Java语言实现插入排序
以下是在Java中实现插入排序的示例代码：
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--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
System.out.println("排序前：" + Arrays.toString(arr));
insertionSort(arr);
System.out.println("排序后：" + Arrays.toString(arr));
}
}初始化变量 n 为数组的长度。
遍历数组，从第二个元素开始（i = 1），因为第一个元素默认是已排序的。
对于每个元素 arr[i]，我们将其值保存在变量 key 中，以便于后面的比较和插入操作。
使用变量 j 来指向当前元素的前一个元素，即 arr[i-1]。
执行一个 while 循环，条件是 j 大于等于0，并且 arr[j]（即当前元素的前一个元素）大于 key。这个循环的目的是找到 key 应该插入的位置。
在循环内部，将 arr[j] 的值移动到 arr[j+1] 的位置，为 key 腾出空间。
j 递减，继续向前比较，直到找到 key 应该插入的位置或者 j 变为负数（即没有更多的元素需要比较）。
当 while 循环结束时，j + 1 就是 key 应该插入的位置。因此，将 key 插入到 arr[j + 1]。
当所有元素都遍历完毕，数组也就完成了排序。
public static void insertionSort(int[] arr) {
int n = arr.length; // 获取数组的长度
// 从数组的第二个元素开始遍历（因为第一个元素默认是有序的）
for (int i = 1; i < n; i++) {
// 当前要处理的元素，初始时我们假设它是未排序的
int key = arr[i];
// j用于指示已排序部分的最后一个元素的索引
int j = i - 1;
// 当j有效（非负）且已排序部分的元素大于key时，执行循环
while (j >= 0 && arr[j] > key) {
// 将已排序部分的元素后移，为key腾出空间
arr[j + 1] = arr[j];
// 将j向前移动一位，继续比较前一个元素
j--;
}
// 当循环结束时，j+1就是key应该插入的位置
// 将key插入到正确的位置
arr[j + 1] = key;
}
}