排序算法之插入排序详细解读（附带Java代码解读）
插入排序（Insertion Sort）是一种简单直观的排序算法，通常用于少量数据的排序。它的工作方式与我们整理扑克牌类似：每次将一张牌插入到已经排好序的牌堆中。
算法思想
- 开始排序：假设第一个元素已经排好序。
- 逐步插入：从第二个元素开始，依次将每个元素插入到前面已经排好序的部分，使得插入后依然有序。
- 重复步骤2：直到数组的最后一个元素。
过程示例
假设有一个待排序的数组：[12, 11, 13, 5, 6]
初始状态:
数组：[12, 11, 13, 5, 6]
第1轮插入（将11插入到已排序部分）:
- 选择数组的第二个元素11。
- 将11与前面的12进行比较，11小于12。
- 将12向后移一位，将11插入到第一位。
- 数组变为：[11, 12, 13, 5, 6]。
第2轮插入（将13插入到已排序部分）:
- 选择数组的第三个元素13。
- 13与12比较，13大于12，因此13无需移动。
- 数组保持不变：[11, 12, 13, 5, 6]。
第3轮插入（将5插入到已排序部分）:
- 选择数组的第四个元素5。
- 5依次与13、12、11进行比较，5小于它们。
- 依次将13、12、11向后移一位，将5插入到第一位。
- 数组变为：[5, 11, 12, 13, 6]。
第4轮插入（将6插入到已排序部分）:
- 选择数组的第五个元素6。
- 6与13、12、11进行比较，6小于13、12，但大于11。
- 将13、12向后移一位，将6插入到11后面。
- 数组变为：[5, 6, 11, 12, 13]。
经过上述4轮插入操作，数组已经完全有序。
算法复杂度
-
时间复杂度:
- 最坏情况: O(n^2)
- 平均情况: O(n^2)
- 最佳情况: O(n)（当数组已经有序时，插入排序只需进行一次比较）
-
空间复杂度: O(1) 插入排序是原地排序算法，不需要额外的存储空间。
优点
- 简单易实现：插入排序的思想直观易懂，代码实现也非常简单。
- 适用于小规模数据：在小规模数据或部分有序的数据中，插入排序表现良好。
- 稳定性：插入排序是一个稳定的排序算法，相同的元素在排序后相对位置不变。
缺点
- 时间复杂度较高：在大规模数据的排序中，插入排序的时间复杂度较高，不适合用在效率要求较高的场景中。
- 移动次数较多：在最坏情况下（逆序数组），插入排序需要大量的元素移动。
插入排序的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;// 向前扫描已排序部分，找到合适的位置插入keywhile (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j]; // 向后移动元素j = j - 1;}arr[j + 1] = key; // 插入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 + " ");}System.out.println();insertionSort(arr);System.out.println("排序后的数组:");for (int num : arr) {System.out.print(num + " ");}}
}
代码说明
-
insertionSort方法:
- 从数组的第二个元素开始，将每个元素插入到前面的已排序部分。
- 内层循环将当前元素
key插入到合适的位置。扫描已排序部分，如果当前元素小于扫描的元素，则将扫描元素后移，直到找到合适的位置。
-
main方法:
- 创建一个待排序的数组
arr。 - 调用
insertionSort方法对数组进行排序。 - 输出排序前和排序后的数组。
- 创建一个待排序的数组