插入排序 Java 实现 + 思路详解

一、核心思想

插入排序把数组分成两部分：左侧已排序区间、右侧未排序区间

1. 默认第 0 个元素天然有序，已排序区间：[0]；
2. 依次取出未排序区间第一个元素（记为待插入元素）；
3. 向前遍历有序区间，比待插入元素大的元素统一向后挪动一位；
4. 找到合适空位，将待插入元素放入；
5. 循环直到所有元素完成插入。

算法特性（面试重点）

• 时间复杂度： 最坏 / 平均 \(O(n^2)\)；最好情况 (数组已有序) \(O(n)\)
• 稳定排序
• 适合小规模数据、接近有序的数据

二、完整代码（升序）

java

运行

public class InsertSort { public static void main(String[] args) { int[] arr = {5, 2, 9, 3, 7, 6, 1}; System.out.println("排序前："); printArr(arr); insertSort(arr); System.out.println("排序后："); printArr(arr); } /** * 插入排序 升序 */ public static void insertSort(int[] arr) { int len = arr.length; // i从1开始：arr[0]默认有序，从第二个元素开始处理 for (int i = 1; i < len; i++) { // 当前要插入的元素 int temp = arr[i]; // j指向有序区间末尾 int j = i - 1; // 向前遍历有序区间：大于temp的元素后移 while (j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } // j+1 就是temp插入的位置 arr[j + 1] = temp; } } // 打印数组 public static void printArr(int[] arr) { for (int num : arr) { System.out.print(num + " "); } System.out.println(); } }

三、简单推演示例

数组：[5,2,9,3]

1. i=1，temp=2 j=0，arr[0]=5>2 → arr[1]=5，j=-1 arr[0]=2 →[2,5,9,3]
2. i=2，temp=9 arr [1]=5 < 9，不用移动，直接原位放置
3. i=3，temp=3 j=2:9>3 → arr [3]=9，j=1 j=1:5>3 → arr [2]=5，j=0 j=0:2<3，停止；arr [1]=3 最终：[2,3,5,9]

四、冒泡 / 选择 / 插入 快速区分

1. 冒泡排序：相邻比较，边比较边交换，大数逐步往后浮
2. 选择排序：一轮找到最值下标，一轮最多交换 1 次
3. 插入排序：逐个拿元素，向前找位置、元素后移，插入空位