插入排序

raw/articles/2026/05/插入排序.md

一句话总结

插入排序是基于选择排序的优化，将 nums[sortedIndex] 插入到左侧有序数组中，对有序度较高的数组效率较高，是稳定排序。

核心要点

1. 核心思想：反向思维

传统选择排序在右侧未排序部分找最小值插入左侧，插入排序反过来：在左侧已排序数组 [0, sortedIndex) 中找到 nums[sortedIndex] 应该插入的位置。

类比：打扑克牌时，将新抓到的牌插入到手中已经排好序的牌中。

2. 算法特性

特性	值
时间复杂度	O(n²)，但有序度高时可接近 O(n)
空间复杂度	O(1)，原地排序
稳定性	✅ 稳定（只有 nums[i] < nums[i-1] 才交换）
综合性能	高于冒泡排序

3. 有序度对效率的影响

• 已排序数组：内层 for 循环几乎不执行交换，接近 O(n)
• 完全逆序：每次都要遍历并交换左侧所有元素，接近 O(n²)
• 综合性能：插入排序操作数 < n²/2，优于冒泡排序的 n²/2

基本原理

算法过程

维护 [0, sortedIndex) 为有序数组，每次将 nums[sortedIndex] 插入到正确位置：

// 插入排序
void sort(int[] nums) {
    int n = nums.length;
    // 维护 [0, sortedIndex) 是有序数组
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // 将 nums[sortedIndex] 插入到有序数组 [0, sortedIndex) 中
        for (int i = sortedIndex; i > 0; i--) {
            if (nums[i] < nums[i - 1]) {
                // swap(nums[i], nums[i - 1])
                int tmp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = tmp;
            } else {
                break;
            }
        }
        sortedIndex++;
    }
}

与冒泡排序的对比

维度	插入排序	冒泡排序
遍历方向	左侧有序部分 [0, sortedIndex)	右侧未排序部分 [sortedIndex..]
操作次数	< n²/2	≈ n²/2
综合性能	更高	较低

时间复杂度

操作	时间复杂度	说明
最好情况（已排序）	O(n)	内层循环几乎不执行
最坏情况（逆序）	O(n²)	每次都要交换左侧所有元素
平均情况	O(n²)	等差数列求和 ≈ n²/2

代码实现

关键代码片段

// 插入排序完整实现
void sort(int[] nums) {
    int n = nums.length;
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // 向前遍历，找到插入位置
        for (int i = sortedIndex; i > 0; i--) {
            if (nums[i] < nums[i - 1]) {
                // 交换相邻元素
                int tmp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = tmp;
            } else {
                break; // 找到正确位置，终止内层循环
            }
        }
        sortedIndex++;
    }
}

实现要点

• 外层 while 循环维护 sortedIndex，表示已排序部分的右边界
• 内层 for 循环从 sortedIndex 向左遍历，通过交换将元素插入正确位置
• 遇到 nums[i] >= nums[i-1] 时 break，提前终止（利用有序性）

对比分析

维度	插入排序	选择排序	冒泡排序
时间复杂度	O(n²)	O(n²)	O(n²)
空间复杂度	O(1)	O(1)	O(1)
稳定性	✅ 稳定	❌ 不稳定	✅ 稳定
提前终止	✅ 支持	❌ 不支持	✅ 支持
有序度利用	✅ 高效	❌ 不利用	⚠️ 利用但效率低

应用场景

• 小数组排序（n ≤ 50 时效率高）
• 近乎有序的数组排序
• 作为高级排序算法（如 TimSort）的子过程
• 在线排序（数据逐步到达的场景）

验证方法

• 可通过 LeetCode 912「排序数组」验证（会超时，但验证正确性）
• 测试有序数组、逆序数组、随机数组的排序结果

相关题目

平台	题目	难度
LeetCode	912. Sort an Array	Medium
力扣	912. 排序数组	中等

相关概念

• 排序算法：评估指标与分类
• 选择排序：插入排序的优化起点
• 冒泡排序：同为稳定排序，插入排序性能更优
• 稳定排序：相同元素相对位置不变
• 原地排序：空间复杂度 O(1)
• 有序度：（仅1篇来源，暂不创建独立页）

相关实体

• labuladong：本文作者，算法学习平台
• leetcode：算法题目验证平台

总结

插入排序通过"将元素插入左侧有序数组"的反向思维优化选择排序，是稳定且原地排序的 O(n²) 算法。对于有序度高的数组，其效率可接近 O(n)，综合性能优于冒泡排序。虽然仍会超时 LeetCode 912，但为后续更高效的排序算法（如希尔排序、快速排序）奠定基础。