数据结构与算法 / 系统课时

插入排序

插入排序

插入排序通过不断扩展数组左侧的有序区完成排序。本课将把“取出当前元素、右移更大元素、插入空位”落实为 Java 代码,并用循环不变式说明算法为什么始终正确。

学习目标

  • 描述插入排序每一轮如何扩展有序前缀。
  • 编写稳定、原地且可运行的插入排序实现。
  • 使用循环不变式证明正确性并分析时间、空间复杂度。

算法思路与正确性

插入排序把数组划分为左侧有序区和右侧未处理区。第 i 轮开始时,区间 0..i-1 已经有序;算法暂存 array[i],将有序区中比它大的元素依次右移,再把它写入空出的正确位置。

插入排序逐轮扩展有序区

循环不变式

在每次外层循环开始时,子数组 array[0..i-1] 已按非递减顺序排列,并且包含原数组前 i 个元素的同一多重集合。

  1. 初始化:非空输入的首元素本身有序。空数组不进入循环,已经满足输出要求。
  2. 保持:右移所有大于 key 的元素后,把 key 放入空位,新的 array[0..i] 仍然有序,元素也没有增加或丢失。
  3. 终止:当 i == array.length 时,有序前缀覆盖整个数组,因此数组整体有序。

判断条件必须使用 array[j] > key。若改成 array[j] >= key,相等元素也会被越过,算法将失去稳定性。

复杂度

情况 比较与移动特征 时间复杂度
已有序 每轮只比较一次,不发生右移 O(n)O(n)
逆序 第 i 轮右移 i 个元素 O(n2)O(n^2)
一般输入 每个逆序对对应一次右移 Θ(n+I)\Theta(n+I),I 为逆序对数(n≥1)

排序核心只保存 key、i、j 等常数个变量。若启用逐轮打印,格式化整张表在每轮都会消耗线性时间和临时字符串空间,即使原输入已有序也会有平方级输出工作。它是原地、稳定、在线的比较排序,适合规模较小或接近有序的数据。

完整实现

将代码保存为 InsertionSortDemo.java。程序在每轮结束后输出数组状态,便于核对有序区是否按预期扩大。

java
import java.util.Arrays;

public class InsertionSortDemo {

    public static void main(String[] args) {
        int[] values = {7, 3, 5, 2, 9, 1};

        System.out.println("原始数组: " + Arrays.toString(values));
        insertionSort(values, true);
        System.out.println("排序结果: " + Arrays.toString(values));
    }

    private static void insertionSort(int[] array, boolean trace) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;

            // 为 key 腾出位置,只右移严格大于 key 的元素。
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }

            array[j + 1] = key;
            if (trace) {
                System.out.println("第 " + i + " 轮: " + Arrays.toString(array));
            }
        }
    }
}

编译并运行:

bash
javac -encoding UTF-8 InsertionSortDemo.java
java InsertionSortDemo

预期输出

text
原始数组: [7, 3, 5, 2, 9, 1]
第 1 轮: [3, 7, 5, 2, 9, 1]
第 2 轮: [3, 5, 7, 2, 9, 1]
第 3 轮: [2, 3, 5, 7, 9, 1]
第 4 轮: [2, 3, 5, 7, 9, 1]
第 5 轮: [1, 2, 3, 5, 7, 9]
排序结果: [1, 2, 3, 5, 7, 9]

边界、错误与练习

空数组和单元素数组不会进入外层循环,因此无需单独分支。常见错误是把 key 直接留在数组中而不先保存,右移时会覆盖待插入值;另一个错误是在循环结束后写成 array[j] = key,当 j == -1 时会越界,正确位置始终是 j + 1。

练习一:把示例改为降序排序。保持算法稳定,并让每轮输出仍能体现左侧有序区。验收条件是输入 [3, 1, 3, 2] 后得到 [3, 3, 2, 1],给两个键为 3 的记录分别标记 A 和 B,额外验证 A 仍在 B 前。只用整数数组无法区分相同值的记录身份。

练习二:在不改变排序结果的前提下统计比较次数和右移次数,分别测试已有序、逆序和随机数组。验收条件是已有序数组的右移次数为 0,长度为 n、关键字严格降序时,右移次数为 n(n−1)/2。含相等值时,逆序对只计严格大于。

本课总结

  • 插入排序通过把当前元素插入有序前缀来逐步扩大已排序区。
  • 循环不变式同时保证前缀有序和元素集合不变,从而证明最终结果正确。
  • 严格大于判断保证稳定性;算法辅助空间为 O(1)O(1),最坏时间为 O(n2)O(n^2)。

下一课预告

下一阶段将继续比较其他基于关键字比较的排序方法,重点观察它们在移动次数、稳定性和最坏时间复杂度上的不同取舍。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

插入排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通