插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，适用于小规模数据或部分有序的数据集。其核心思想是通过构建有序序列，逐步将未排序的元素插入到已排序部分的适当位置，最终完成排序。

算法原理

插入排序的工作方式类似于整理扑克牌：每次从无序部分取出一张牌，并将其插入到有序部分的正确位置。具体步骤如下：

1. 将数组分为已排序和未排序两部分，初始时已排序部分仅包含第一个元素。 2. 从未排序部分取出第一个元素，记为key。 3. 将key与已排序部分的元素从后向前比较，找到合适的插入位置。 4. 插入key后，已排序部分长度增加1，未排序部分减少1。 5. 重复上述过程，直到未排序部分为空。

时间复杂度分析

最坏情况（逆序数组）： $O (n^{2})$
最好情况（已排序数组）： $O (n)$
平均情况： $O (n^{2})$

代码实现

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

def insertion_sort(arr):
    # 遍历数组从第二个元素开始（索引1）
    for i in range(1, len(arr)):
        key = arr[i]  # 当前待插入元素
        j = i - 1      # 已排序部分的最后一个元素索引
        
        # 将大于key的元素向后移动
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # 插入key到正确位置
        arr[j + 1] = key

# 示例用法
if __name__ == "__main__":
    data = [12, 11, 13, 5, 6]
    print("排序前:", data)
    insertion_sort(data)
    print("排序后:", data)

输出结果：

排序前: [12, 11, 13, 5, 6]
排序后: [5, 6, 11, 12, 13]

可视化过程

以下展示对数组[5, 2, 4, 6, 1, 3]的排序过程：

实际应用场景

插入排序在以下场景中表现优异： 1. 小规模数据：当数据量较小时（如n ≤ 10），其常数因子小，实际性能可能优于 $O (n \log n)$ 的算法。 2. 部分有序数据：如日志文件按时间近乎有序时，插入排序只需 $O (n)$ 时间。 3. 在线算法：适合数据流式输入场景，可以逐个处理新元素。

优化技巧

二分查找优化：用二分查找确定插入位置，减少比较次数（但仍需移动元素，时间复杂度仍为 $O (n^{2})$ ）
希尔排序：通过分组插入排序实现改进，平均复杂度可达 $O (n^{1.25})$

与其他排序算法对比

算法	平均时间复杂度	空间复杂度	稳定性	适用场景
插入排序	$O (n^{2})$	$O (1)$	稳定	小规模/部分有序数据
快速排序	$O (n \log n)$	$O (\log n)$	不稳定	通用大规模数据
归并排序	$O (n \log n)$	$O (n)$	稳定	需要稳定排序时

练习题目

1. 实现一个降序排列的插入排序版本 2. 对链表结构实现插入排序（注意指针操作） 3. 分析插入排序在最好/最坏情况下的元素比较次数

总结

插入排序作为基础排序算法，虽然在大数据量时效率不高，但其实现简单、空间效率高（原地排序），在特定场景下仍具有实用价值。理解插入排序有助于学习更高级的算法设计技巧，如希尔排序和自适应排序算法。