（笔记）插入排序

插入排序

插入排序是一种简单且常见的排序算法，它通过重复将一个元素插入到已经排好序的一组元素中，来达到排序的目的。在插入排序算法中，将待排序序列分为已排序和未排序两个部分。初始时，已排序部分只包含一个记录，即待排序序列的第一个记录。然后，逐个将未排序部分的记录插入到已排序部分的适当位置，直到所有记录都插入到已排序部分为止。由于插入排序算法的思路简单，实现也容易，因此它在实际应用中被广泛使用。

代码实现

以下是插入排序的Java代码实现：

public static void insertionSort(int[] arr) {if (arr == null || arr.length <= 1) {return;}int n = arr.length;for (int i = 1; i < n; i++) {int value = arr[i];int j = i - 1;for (; j >= 0; j--) {if (arr[j] > value) {arr[j + 1] = arr[j];} else {break;}}arr[j + 1] = value;}
}

时间复杂度

插入排序的时间复杂度为$O(n^2)，其中n为待排序序列的长度。虽然插入排序的时间复杂度比一些高级排序算法要高，但是在实际应用中，插入排序仍然是一种非常实用的算法，因为它对于小规模的数据排序效率非常高。同时，当待排序序列已经有序或基本有序时，插入排序的时间复杂度可以降低到$O(n)，这也是插入排序具有优势的地方之一。

使用场景

插入排序适用于待排序序列较短的情况，特别是当待排序序列已经基本有序时，插入排序的效率非常高。在排序小规模数据时，插入排序是一个不错的选择。同时，由于插入排序的实现较为简单，因此适合用作其他排序算法的子过程。除此之外，在一些高级排序算法中，插入排序也被用来对小规模数据进行排序。例如，快速排序算法在排序过程中，当待排序序列的规模小于某个值时，会采用插入排序算法进行排序。