Java插入排序详解（手把手教你掌握插入排序算法）

插入排序的核心思想

• 将数组分为“已排序”和“未排序”两部分。
• 初始时，第一个元素视为“已排序”。
• 从未排序部分取出第一个元素，在已排序部分从后往前比较，找到合适位置插入。
• 重复上述过程，直到所有元素都被处理。

Java实现插入排序

下面是一个完整的Java插入排序代码示例：

public class InsertionSort {    public static void insertionSort(int[] arr) {        // 从第二个元素开始遍历（索引为1）        for (int i = 1; i < arr.length; 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[] numbers = {12, 11, 13, 5, 6};        System.out.println("排序前：");        printArray(numbers);        insertionSort(numbers);        System.out.println("排序后：");        printArray(numbers);    }    public static void printArray(int[] arr) {        for (int value : arr) {            System.out.print(value + " ");        }        System.out.println();    }}

代码解析

让我们逐行解释这段代码：

• i = 1：因为第一个元素默认是“已排序”的，所以从第二个元素开始处理。
• key = arr[i]：保存当前要插入的值。
• while 循环：从已排序部分的末尾向前扫描，只要遇到比 key 大的元素，就将其向后移动一位。
• arr[j + 1] = key：当找到合适位置后，将 key 插入。

时间与空间复杂度

适用场景

虽然插入排序算法的时间复杂度较高，但它有以下优点：

• 实现简单，代码量少。
• 对小规模数据或基本有序的数据效率很高。
• 是稳定的排序算法（相等元素的相对位置不变）。
• 常用于更复杂算法（如快速排序）的优化子程序。

总结

通过本篇Java排序教程，你应该已经掌握了插入排序的基本原理和实现方法。作为初学者Java排序的入门算法，插入排序不仅帮助你理解排序逻辑，也为学习更高级算法打下基础。

动手试试吧！修改数组内容，观察排序过程，加深理解。编程之路，从理解每一个基础算法开始！