Java 插入排序算法详解：核心原理、完整代码与步骤演示

什么是插入排序？

插入排序是一种简单直观的排序算法，适合小规模或近乎有序的数据集。每次迭代取出一个元素，与已排序部分的元素从后向前比较，找到合适位置插入。

插入排序最坏/平均 O(n²)，最好 O(n)（已有序）。它是原地、稳定排序，仅需常数额外空间。

插入排序算法流程图解

插入排序算法流程演示

Java 程序示例：使用插入排序对数组排序

package com.guru99;

public class InsertionSortExample {
    public static void main(String a[]) {
        int[] myArray = {860, 8, 200, 9};
        System.out.println("插入排序前");
        printArray(myArray);
        insertionSort(myArray);
        System.out.println("插入排序后");
        printArray(myArray);
    }

    public static void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            System.out.println("第 " + i + " 趟排序");
            int key = arr[i];
            int j = i - 1;
            while ((j > -1) && (arr[j] > key)) {
                System.out.println("比较 " + key + " 和 " + arr[j]);
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
            System.out.println("插入元素: 插入后数组");
            printArray(arr);
        }
    }

    static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

代码运行输出

插入排序前
860 8 200 9
第 1 趟排序
比较 8 和 860
插入元素: 插入后数组
8 860 200 9
第 2 趟排序
比较 200 和 860
插入元素: 插入后数组
8 200 860 9
第 3 趟排序
比较 9 和 860
比较 9 和 200
插入元素: 插入后数组
8 9 200 860
插入排序后
8 9 200 860

算法特性总结

• 时间复杂度：最好 O(n)、平均/最差 O(n²)。
• 空间复杂度：O(1)。
• 稳定性：稳定。
• 适用场景：小规模数据、近乎有序数据、在线排序（数据流到达即排序）。

对比：插入排序 vs 冒泡排序 vs 选择排序