1.5 插入排序

---

1. 插入排序算法思想

插入排序（Insertion Sort）基本思想：

将数组分为有序区间和无序区间，每次从无序区间取出一个元素插入到有序区间的正确位置。

插入排序通过逐步构建有序序列来实现排序，每次插入后有序区间保持有序。

2. 插入排序算法步骤

假设数组长度为 $n$，算法步骤如下：

1. 初始化：有序区间为 $[0, 0]$，无序区间为 $[1, n - 1]$
2. 第 $i$ 趟插入（$i$ 从 $1$ 到 $n - 1$）：
   • 取出无序区间第一个元素 $nums[i]$
   • 从右到左遍历有序区间，将大于 $nums[i]$ 的元素右移一位
   • 找到合适位置后插入 $nums[i]$
   • 有序区间扩展为 $[0, i]$，无序区间变为 $[i + 1, n - 1]$

以数组 $[5, 2, 3, 6, 1, 4]$ 为例，演示一下插入排序的算法步骤。

插入排序的算法步骤

3. 插入排序代码实现

class Solution:
    def insertionSort(self, nums: [int]) -> [int]:
        # 遍历无序区间
        for i in range(1, len(nums)):
            temp = nums[i]
            j = i
            # 从右至左遍历有序区间
            while j > 0 and nums[j - 1] > temp:
                # 将大于temp的元素右移
                nums[j] = nums[j - 1]
                j -= 1
            # 插入到正确位置
            nums[j] = temp
        return nums

    def sortArray(self, nums: [int]) -> [int]:
        return self.insertionSort(nums)

4. 插入排序算法分析

指标	复杂度	说明
最佳时间复杂度	$O(n)$	数组已有序，每个元素只需比较一次
最坏时间复杂度	$O(n^2)$	数组逆序，每个元素需要比较 $i-1$ 次
平均时间复杂度	$O(n^2)$	一般情况下的复杂度
空间复杂度	$O(1)$	原地排序，只使用常数空间
稳定性	✅ 稳定	相等元素相对位置不变

适用场景：

• 数据量较小（$n < 50$）
• 数据基本有序
• 在线排序（数据逐个到达）

5. 总结

插入排序是一种简单直观的排序算法，通过逐步构建有序序列实现排序。

优点：实现简单，稳定排序，空间复杂度低，对基本有序数据效率高
缺点：时间复杂度高，不适合大规模数据

练习题目

• 0912. 排序数组（插入排序会超时，仅作练习）

• 排序算法题目列表