插入排序（Insertion Sort）

插入排序（Insertion Sort）是一种简单直观的排序算法，适合于少量数据的排序场景。它的核心思想是将数据逐一插入到一个有序序列中，从而最终使整个序列有序。

算法原理

插入排序的基本思路如下：

1. 初始状态：将第一个元素视为一个有序序列，其余元素为待排序的无序序列。
2. 逐步插入：依次将无序序列中的元素插入到有序序列的正确位置。
3. 结束条件：当所有元素都被插入到有序序列中时，排序完成。

插入排序的核心操作是：
对每个待插入元素，从有序序列的末尾向前扫描，找到合适的位置插入。

算法步骤

假设有一个数组 arr，长度为 n，插入排序的流程如下：

1. 从第二个元素 arr[1] 开始，依次取出每个元素。
2. 与前面的有序部分逐一比较，找到合适位置插入。
3. 重复此过程，直到所有元素排序完成。

伪代码

for i 从 1 到 n-1:
    取出 arr[i] 作为待插入元素
    j = i - 1
    while j >= 0 且 arr[j] > 待插入元素:
        将 arr[j] 向后移动一位
        j = j - 1
    将待插入元素放入 arr[j + 1]

动态演示示例

我们用数组 [5, 3, 4, 1, 2] 来详细演示插入排序的整个过程。

初始状态

数组为 [5, 3, 4, 1, 2]。第一个元素 5 已视为有序。

第一步：插入 3

• 待插入元素是 3，与有序部分 [5] 比较。
• 3 < 5，将 5 向后移动一位。
• 插入 3，数组变为 [3, 5, 4, 1, 2]。

第二步：插入 4

• 待插入元素是 4，与有序部分 [3, 5] 比较。
• 4 < 5，将 5 向后移动一位。
• 4 > 3，插入 4，数组变为 [3, 4, 5, 1, 2]。

第三步：插入 1

• 待插入元素是 1，与有序部分 [3, 4, 5] 比较。
• 1 < 5，将 5 向后移动一位。
• 1 < 4，将 4 向后移动一位。
• 1 < 3，将 3 向后移动一位。
• 插入 1，数组变为 [1, 3, 4, 5, 2].

第四步：插入 2

• 待插入元素是 2，与有序部分 [1, 3, 4, 5] 比较。
• 2 < 5，将 5 向后移动一位。
• 2 < 4，将 4 向后移动一位。
• 2 < 3，将 3 向后移动一位。
• 2 > 1，插入 2，数组变为 [1, 2, 3, 4, 5]。

最终结果

排序完成，数组为 [1, 2, 3, 4, 5]。

时间复杂度分析

• 最优时间复杂度：当数组已基本有序时，每次插入只需比较一次，时间复杂度为 O(n)。
• 最差时间复杂度：当数组为逆序时，每次插入需要比较并移动所有已有元素，时间复杂度为 O(n^2)。
• 平均时间复杂度：O(n^2)。

空间复杂度

插入排序是原地排序算法，仅需常数级的额外空间，因此空间复杂度为 O(1)。

代码实现

以下是插入排序的 Python 实现：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # 向左寻找插入位置
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 将元素右移
            j -= 1
        arr[j + 1] = key  # 插入元素
    return arr

# 示例
arr = [5, 3, 4, 1, 2]
sorted_arr = insertion_sort(arr)
print("排序后的数组:", sorted_arr)

运行结果：

排序后的数组: [1, 2, 3, 4, 5]

优缺点总结

优点

1. 简单易懂：实现逻辑直观，代码简洁。
2. 适合小规模数据：对于小型数据集，效率较高。
3. 稳定性：插入排序是稳定排序算法，相同元素的相对位置不会改变。

缺点

1. 效率低：当数据量较大时，效率不如高级排序算法（如快速排序、归并排序）。
2. 不适合大型数据集：时间复杂度为 O(n^2)。

总结

插入排序是学习排序算法的良好起点，其简单性和稳定性使其适合于小规模数据或几乎有序的数组。虽然效率较低，但通过分析和实现，我们可以更好地理解排序的核心思想，为学习更复杂的排序算法打下基础。

PS：可以点击打开“插入排序算法演示”页面亲自体验一下 😊