Java插入排序算法原理与代码实现详解

宋时安

发布时间：2026-10-13| 2人浏览过

原创

插入排序是基础且高效的排序算法之一，特别适用于小规模数据或部分有序的数据集。通过将待排序元素逐个插入到已排序序列的正确位置，它能在最佳情况下达到O(n)的时间复杂度。

插入排序的核心概念

插入排序的基本思想类似于整理手中的扑克牌。每次从无序序列中取出一个元素，将其与已排序序列中的元素从后向前进行比较，找到合适的位置并将该元素插入。

适用场景：数据量较小或数据已基本有序的情况。
时间复杂度：
- 最好情况（数据已有序）：O(n)，只需进行一次比较。
- 平均与最坏情况（数据逆序）：O(n^2)，需要进行大量的比较和移动操作。
空间复杂度：O(1)，属于原地排序（In-place），不需要额外的存储空间。
稳定性：稳定排序。相等元素的相对顺序在排序后不会改变。

算法执行步骤

插入排序将数组划分为两个部分：左边的已排序部分和右边的未排序部分。具体操作流程如下：

第1步：初始化假设

默认数组的第一个元素已经是有序的。即从索引 1 开始进行遍历处理。

第2步：取出下一个待插入元素

从未排序部分的第一个元素（即当前索引 out）取出暂存，通常保存在临时变量 temp 中。

第3步：向前扫描与移位

从已排序部分的最后一个元素开始，从后向前扫描：

如果已排序位置的元素大于 temp，将该元素向后移动一位（复制）。这是为了给 temp 腾出空间。
继续向前比较，直到找到一个小于或等于 temp 的元素，或者到达已排序部分的起始位置。

第4步：插入元素

当扫描结束或找到合适位置时，将 temp 赋值给当前空出的位置。in 指针此时指向的就是 temp 应该放置的索引。

第5步：重复过程

增加外层循环索引，重复上述步骤，直到所有元素都被处理完毕。

Java代码实现

以下是标准的插入排序Java实现。代码中包含了对复制次数和比较次数的统计，便于理解算法的运行开销。

public void insertionSort() {
    // out: 表示已排序区间的边界，同时也指向下一个待插入元素
    // in: 表示在已排序区间内寻找插入位置的指针
    int out, in;
    int count1 = 0; // 记录数据复制（移位）次数
    int count2 = 0; // 记录元素比较次数

    // 从第二个元素开始遍历
    for (out = 1; out < nElems; out++) {
        long temp = a[out]; // 暂存当前待插入元素
        in = out;           // in 初始指向当前元素位置

        // 标志位：判断是否需要继续前移
        boolean flag = in > 0 && a[in - 1] >= temp;

        while (flag) {
            if (a[in - 1] >= temp) {
                if (in > 0) {
                    a[in] = a[in - 1]; // 将较大的元素后移一位
                    count1++;          // 记录一次复制
                    --in;              // 指针前移
                }
            }
            count2++;                  // 记录一次比较
            // 更新判断条件：是否还有前驱元素且前驱元素更大
            flag = in > 0 && a[in - 1] >= temp;
        }
        a[in] = temp; // 将暂存的元素插入到正确位置
    }
    System.out.println("复制次数为：" + count1 + " 比较次数为：" + count2);
}